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 / +
计算规则：从左到有遍历表达式的每个数字和符号，遇到是数字就进栈，遇到是符号，就将处于栈顶的两个数字出栈，进行计算，再将运算结果进栈，一直到最终获得结果。
- 初始化一个空栈。此栈用来对要运算的数字进出使用。
- 后缀表达式中前三个都是数字，所以
9、3、1进栈
- 后缀表达式中前三个都是数字，所以
- 接下来是
-所以将占中的1出栈作为减数，3作为被减数，并将运算3-1得到的2 再进栈
- 接下来是
- 接下来是数字
3进栈
- 接下来是数字
- 后面是
*也就意味着栈中的3和2出栈， 2*3 = 6，将6进栈
- 后面是
- 下面是
+所以6和9出栈 9+6=15，将15进栈
- 下面是
- 接下来是
10与2两个数字进栈
- 接下来是
- 接下来是符号
/栈顶的2与10出栈，10/2 = 5,再进栈
- 接下来是符号
- 最后一个是符号
+所以15与5出栈 5+15 = 20
- 最后一个是符号
- 结果是20出栈，栈变为空
利用后缀表达法可以很顺利解决计算的问题，那么问题来了
9+(3-1)*3+10/2是如何转化为9 3 1 - 3 * + 10 2 / +,请往下看
- 结果是20出栈，栈变为空
2.2 中缀表达式转后缀表达式
我们把平时所用的标准四则运算表达式，即9+(3-1)*3+10/2叫做中缀表达式。因为所有的运算符号都在两数字的中间，现在的问题就是中缀转后缀了
中缀表达式 `9+(3-1)*3+10/2` 转化为后缀表达式 `9 3 1 - 3 * + 10 2 / + `
从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分；若是符号，则判断其与栈顶符号的优先级，是右括号或优先级低于栈顶符号（乘除优于加减）则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止
- 初始化一空栈，用来对符号进出栈使用
- 第一个字符是数字
9， 输出9，后面是符号+，进栈
- 第一个字符是数字
- 第三个是字符
(,依然是符号，因其只是左括号，还未配对，故进栈
- 第三个是字符
- 第四个是数字
3, 输出， 表达式为9 3,接着是-,进栈
- 第四个是数字
- 接下来是数字
1，输出，表达式为9 3 1,后面是符号),此时，我们需要去匹配此前的(,所以栈顶依次出栈，并输出，直到(出栈为止。
此时括号上方只有-,因此输出，表达式变为9 3 1 -
- 接下来是数字
- 接着是数字
3,输出，总的表达式为9 3 1 - 3. 紧接着是符号*，因为此时的栈顶符号为+,优先级低于*,所以不输出，*进栈
- 接着是数字
- 之后是符号
+此时当前栈顶元素*比这个+的优先级高，因此栈中元素出栈并输出（没有比 '+' 号更低的优先级，所以全部出栈），总表达式为9 3 1 - 3 * +. 然后将当前这个符号+进栈。 请注意此处的+是中缀式子中的最后一个+。因为此前的都清空了
- 之后是符号
- 紧接着是数字
10,输出。 表达式变为9 3 1 - 3 * + 10，后是符号/,所以进栈
- 紧接着是数字
- 最后一个是数字
2，输出，总的表达式为9 3 1 - 3 * + 10 2
- 最后一个是数字
- 因已到最后，所以将占中符号全部出栈并输出最终输出的结果为
9 3 1 - 3 * + 10 2 / +
- 因已到最后，所以将占中符号全部出栈并输出最终输出的结果为
3 总结
从刚才的推导中你会发现，要想计算机具有我们常规的处理逻辑
最重要的就两步：
1. 将中缀表达式转化为后缀表达式（栈用来进出运算的符号）
2. 将后缀表达式进行运算得出结果（栈用来进出运算的数字)
