栈的应用——四则运算表达式求值(逆波兰式)

逆波兰式也称为后缀表达式，也就是将运算符写在操作数之后。

逆波兰式的作用：

实现逆波兰式的算法，难度并不大，但为什么要将看似简单的中序表达式转换为复杂的逆波兰式？原因就在于这个简单是相对人类的思维结构来说的，对计算机而言中序表达式是非常复杂的结构。相对的，逆波兰式在计算机看来却是比较简单易懂的结构。因为计算机普遍采用的内存结构是栈式结构，它执行先进后出的顺序。

中缀表达式转后缀表达式：

规则：从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分；若是符号，则判断其与栈顶符号的优先级，若是右括号或优先级低于等于栈顶符号(乘除优先级高于加减)则栈顶元素依次出栈并输出，否则栈顶元素不出栈，并将当前符号进栈，一直到最终输出后缀表达式为止。
我们把平时所用的标准四则运算表达式，即“9+(3-1)x3+10÷2”叫做中缀表达式。因为所有的运算符号都在两数字的中间，现在我们来看中缀到后缀的转化。
中缀表达式“9+(3-1)x3÷2”转化为后缀表达式“9 3 1 - 3 * + 10 2 / +”。
1、初始化一空栈，用来对符号进出栈使用。如图 1 的左图所示。

2. 第一个字符是数字 9，输出 9，后面是符号“+”，进栈。如图 1 的右图所示。
3.第三个字符是“(”，依然是符号，因其只是左括号，还未配对，故进栈。如图 2 的左图所示。
4. 第四个字符是数字 3，输出，总表达式为 9 3，接着是“-”，进栈。如图 2 的右图所示。

5、接下来是数字 1，输出，总表达式为 9 3 1，后面是符号“)”，此时我们需要去匹配此前的“(”，所以栈顶依次出栈，并输出，直到“(”出栈为止。此时左括号上方只有“-”，因此输出“-”。总的输出表达式为9 3 1 -。如图 3 的左图所示。
6、接着是数字 3，输出，总的表达式为9 3 1 - 3。紧接着是符号“x”，因为此时的栈顶符号为“+”号，优先级低于“x”，因此不输出，“*”进栈。如图3的右图所示。

7、之后是符号 “+”，此时当前栈顶元素 “*”比这个"+" 的优先级高 ，因此栈中元素出栈并输出。(没有比“+”号更低的优先级，所以全部出栈) ，总输出表达式为9 3 1 - 3 * +。然后将当前这个符号“+”进栈。也就是说，前 6 张图的栈底的“+”是指中缀表达式中开头的 9 后面那个“+”，而图 4 左图中的栈底(也就是栈顶)的“+”是指9+(3-1)x3+中的最后一个“+”。
8、紧接着数字 10，输出，总表达式变为9 3 1 - 3 * + 10。然后是符号“÷”，所以“/”进栈。如图 4 的右图所示。

9、最后一个数字 2，输出，总的表达式为9 3 1 - 3 * + 10 2。如图 5 的左图所示。
10、因已经到最后，所以将栈中符号全部出栈并输出。最终输出的后缀表达式结果为9 3 1 - 3 * + 10 2 / +。如图 5 的右图所示。

后缀表达式的计算

对后缀表达式：9 3 1 - 3 * + 10 2 、 + 进行计算。
规则:从左到右遍历表达式的每个数字和符号，遇到是数字就进栈，遇到是符号，就将处于栈顶的两个数字出栈，进行运算，运算结果进栈，一直到最终获得结果。
1、初始化一个空栈，此栈用来对要运算的数字进出使用。如图 6 的左图所示。
2、后缀表达式中前三个都是数字，所以9、3、1进栈，如图 6 的右图所示。

3、接下来是 “-”，所以将栈中的 1 出栈作为减数，3 出栈作为被减数，并运算3 - 1得到 2，再将 2 进栈，如图 7 的左图所示。
4、接着是数字 3 进栈，如图 7 的右图所示。

5、后面是“*”，也就意味着栈中 3 和 2 出栈， 2 与 3 相乘，得 6，并将 6 进栈，如图 8 的左图所示。
6、下面是“+”，所以栈中 6 和 9 出钱，9 与 6 相加，得到 15，将 15 进栈，如图 8 的右图所示。

7、接着是 10 与 2 两数字进栈，如图 9 的左图所示。
8、接下来是符号 "/"， 因此，栈顶的 2 与 10 出栈， 10 与 2 相除， 得到 5，将 5 进栈，如图 9 的右图所示。

9、最后一个是符号“+”，所以 15 与 5 出栈并相加，得到 20 ，将 20 进栈，如图 10 的左图所示。
10、结果是 20 出栈，栈变为空 ，如图 10 的右图所示。

从上面的推倒我们可以发现，要想让计算机具有处理我们通常的标准(中缀)表达式的能力，最重要的就是两步:
1、将中缀表达式转化为后缀表达式(栈用来进出运算的符号)。
2、将后缀表达式进行运算得出结果(栈用来进出运算的数字)。

参考文献：大话数据结构