栈的应用 - 表达式运算
1 前缀、中缀、后缀表达式
前缀表达式：又称波兰表示法（Polish notation，或波兰记法），是一种逻辑、算术和代数表示方法，其特点是操作符置于操作数的前面，因此也称做前缀表示法。
中缀表达式：通常将运算符写在运算量之间，例如a+b，这种表示法称为中缀表示法。
后缀表达式：后缀表示法又称逆波兰表示法，它是波兰逻辑学家卢卡西维奇发明的一种表示表达式的方法。这种表示法把运算量写在前面，把运算符写在后面（后缀），例如a+b写作ab+，a+b*c写作abc*+，（a+b）*c写作ab+c*等等。
2 为什么要把中缀表达式转化为后缀，前缀？
计算机没法计算带有括号，以及区分优先级的表达式，或者说很难计算。使用后缀，前缀，消除了括号和优先级。
3 中缀表达式如何转化为后缀，前缀表达式？
转化为后缀：从左到右遍历中缀表达式，遇到操作数，输出，遇到操作符，当前操作符的优先级大于栈顶操作符优先级，进栈，否则，弹出栈顶优先级大于等于当前操作符的操作符，当前操作符进栈。
转化为前缀：从右到左遍历中缀表达式，遇到操作数，输出，遇到操作符，当前操作符的优先级大于等于栈顶操作符优先级，进栈，否则，弹出栈顶优先级大于当前操作符的操作符，当前操作符进栈。
4 中缀表达式转化为后缀具体实现（逆波兰式的实现）
在逆波兰式的实现中，最大的问题是如何改变运算符的先后顺序，把高优先级的运算符放在低优先级运算符的左侧。比如，有一个中缀表达式2 + 3 × 4，它所对应的逆波兰式应当是2 3 4 × +。
在我们做中缀表达式到逆波兰式转换的时候，必须在不改变操作数顺序的情况下，把高优先级的乘法操作符移动到低优先级的加法运算符的左侧。
很自然的，我们会想到堆栈。堆栈具有后进先出的特点。所以我们可以设计一个符号栈，用于临时存储一个中缀表达式中的全部运算符；设计一个RPN数组，用于存储逆波兰式输出。然后从左向右扫描一个中缀表达式，并循环执行以下步骤：
- 如果扫描到一个运算数，则将其放到RPN数组的末尾
- 如果扫描到一个运算符。首先比较该运算符和符号栈栈顶运算符的优先级。如果符号栈栈顶运算符的优先级比较低，则将新运算符压入符号栈（这样最后将符号出栈时，高优先级符号先出栈）。如果栈顶符号的优先级更高，就把栈顶符号弹出，并放入RPN数组末尾。然后继续比较新扫描到的运算符和栈顶运算符的优先级，直到找到一个优先级比自己低的栈顶元素或者到达堆栈栈底。
- 如果表达式扫描结束。将栈中操作符顺序弹出放到RPN数组中。这样就得到了一个逆波兰表达式。
如下是一个逆波兰式生成过程的实例。
其中绿色部分代表每一步中发生变化的部分。其中特殊之处在于对括弧的处理，括弧的优先级高于所有操作符，但是括弧中所有的操作符优先级又高于括弧。所以当栈顶为括弧的时候，不会将括弧弹出，而是继续压栈。当弹出括弧的时候，也不会把括弧放入逆波兰式中。
原中缀表达式：3 + 4 × （5 - 2）/ 2
逆波兰表达式：3 4 5 2 - × 2 / +
5 计算机如何计算后缀，前缀表达式？
计算后缀：从左到右遍历后缀表达式，遇到操作数，放进栈，遇到操作符，栈顶两个数出栈，进行运算，运算结果放进栈，直到读完后缀表达式。
计算前缀：从左到右遍历前缀表达式，遇到操作符，放进栈，遇到操作数，查看栈顶，栈顶为操作符，放进栈，栈顶为操作数，取出栈顶操作数和操作符，进行运算，运算后继续判断栈顶的情况。
6 计算机计算后缀表达式伪代码
while有输入符号
读入下一个符号
IF是一个操作数
入栈
ELSE IF是一个操作符
有一个先验的表格给出该操作符需要n个参数
IF堆栈中少于n个操作数
（错误） 用户没有输入足够的操作数
Else n个操作数出栈
计算操作符。
将计算所得的值入栈
IF栈内只有一个值
这个值就是整个计算式的结果
ELSE多于一个值
（错误） 用户输入了多余的操作数7 计算后缀表达式例子
中缀表达式 “5 + ((1 + 2) * 4) − 3” 写作后缀表达式 5 1 2 + 4 * + 3 −
下表给出了该逆波兰表达式从左至右求值的过程，堆栈栏给出了中间值，用于跟踪算法。
| 输入 | 操作 | 堆栈 | 注释 |
| 5 | 入栈 | 5 | |
| 1 | 入栈 | 5, 1 | |
| 2 | 入栈 | 5, 1, 2 | |
| + | 加法运算 | 5, 3 | (1, 2)出栈；将结果（3）入栈 |
| 4 | 入栈 | 5, 3, 4 | |
| * | 乘法运算 | 5, 12 | (3, 4)出栈；将结果（12）入栈 |
| + | 加法运算 | 17 | (5, 12)出栈；将结果 (17)入栈 |
| 3 | 入栈 | 17, 3 | |
| − | 减法运算 | 14 | (17, 3)出栈；将结果（14）入栈 |
计算完成时，栈内只有一个操作数，这就是表达式的结果：14