四则运算表达式求值

1.引子

最近做项目的时候，遇到了一个需求，就是随机给出一个数学公式，公式中包含变量，让求出公式最终的结果。譬如这样的：

NSDictionary *dic = @{@"s1":@"3",@"s2":@"6",@"s3":@"2"};
NSString *description = @"s1 + s1 * (s2 + s1 ) * 2 + (s2 / s3)";{

让求出 description = 3 + 3(6+3)2+(6/2) = 60

刚开始一头雾水，计算机怎么去识别计算公式呢，对着公式发呆，越看越熟悉，想起来 原来前段时间在学习数据结构的时候见到过，就翻开了书，一切问题都迎刃而解了。不得不佩服前辈们的机智。

项目地址在这里 好厉害，可惜不是我写的,借鉴这位仁兄的传送门😂😂😂

2.解读

数学表达式求值是借助于栈的实现的，俗称后缀表示法定义，也被称为逆波兰表示。（因为是20世纪50年代 波兰的逻辑学家想到的 一种不需要括号的后缀表达法 所有的符号都是在要运算数字的后面出现） 以下为倒推，皆出自《大话数据结构》，感觉这本书写的太好了

2.1 后缀表达式计算结果

对于9+(3-1)*3+10/2,用后缀表示法 应该是

9 3 1 - 3 * + 10 2 / +

计算规则：从左到有遍历表达式的每个数字和符号，遇到是数字就进栈，遇到是符号，就将处于栈顶的两个数字出栈，进行计算，再将运算结果进栈，一直到最终获得结果。

• 1. 初始化一个空栈。此栈用来对要运算的数字进出使用。
• 2. 后缀表达式中前三个都是数字，所以9、3、1进栈
     
• 3. 接下来是 - 所以将占中的1出栈作为减数，3作为被减数，并将运算3-1得到的2 再进栈
• 4. 接下来是数字3 进栈
     
• 5. 后面是 * 也就意味着栈中的3和2出栈， 2*3 = 6，将6进栈
• 6. 下面是 + 所以6和9出栈 9+6=15，将15进栈
     
• 7. 接下来是10与2两个数字进栈
• 8. 接下来是符号/ 栈顶的2与10出栈，10/2 = 5,再进栈
     
• 9. 最后一个是符号+ 所以15与5出栈 5+15 = 20
• 10. 结果是20出栈，栈变为空
      
      利用后缀表达法可以很顺利解决计算的问题，那么问题来了
      9+(3-1)*3+10/2 是如何转化为 9 3 1 - 3 * + 10 2 / + ,请往下看

2.2 中缀表达式转后缀表达式

我们把平时所用的标准四则运算表达式，即9+(3-1)*3+10/2叫做中缀表达式。因为所有的运算符号都在两数字的中间，现在的问题就是中缀转后缀了

中缀表达式 `9+(3-1)*3+10/2` 转化为后缀表达式 `9 3 1 - 3 * + 10 2 / + ` 

从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分；若是符号，则判断其与栈顶符号的优先级，是右括号或优先级低于栈顶符号（乘除优于加减）则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止

• 1. 初始化一空栈，用来对符号进出栈使用
• 2. 第一个字符是数字9， 输出9，后面是符号 + ，进栈
     
• 3. 第三个是字符 ( ,依然是符号，因其只是左括号，还未配对，故进栈
• 4. 第四个是数字3, 输出， 表达式为 9 3 ,接着是 -,进栈
     
• 5. 接下来是数字1，输出，表达式为 9 3 1,后面是符号),此时，我们需要去匹配此前的(,所以栈顶依次出栈，并输出，直到( 出栈为止。
     此时括号上方只有-,因此输出，表达式变为 9 3 1 -
• 6. 接着是数字3,输出，总的表达式为9 3 1 - 3. 紧接着是符号*，因为此时的栈顶符号为+,优先级低于*,所以不输出，*进栈
     
• 7. 之后是符号+ 此时当前栈顶元素*比这个+的优先级高，因此栈中元素出栈并输出（没有比 '+' 号更低的优先级，所以全部出栈），总表达式为9 3 1 - 3 * +. 然后将当前这个符号+进栈。 请注意此处的+是中缀式子中的最后一个+。因为此前的都清空了
• 8. 紧接着是数字10,输出。 表达式变为 9 3 1 - 3 * + 10，后是符号/,所以进栈
     
• 9. 最后一个是数字2，输出，总的表达式为9 3 1 - 3 * + 10 2
• 10. 因已到最后，所以将占中符号全部出栈并输出最终输出的结果为 9 3 1 - 3 * + 10 2 / +
      

3 总结

从刚才的推导中你会发现，要想计算机具有我们常规的处理逻辑
最重要的就两步：

1. 将中缀表达式转化为后缀表达式（栈用来进出运算的符号）
2. 将后缀表达式进行运算得出结果（栈用来进出运算的数字)