栈的应用（表达式求值）

算数表达式由三部分组成：操作数、运算符、界限符（界限符是必不可少的，反映了计算的先后顺序）

三种表达式的形式

首先要分清三种表达式的写法，这是所有计算的基础：
注意：数字出现的左右先后顺序不能改变。

表达式类型	定义	示例（1+2 )和 (3+4)*5）	特点
中缀表达式（Infix）	运算符在两个操作数中间	1 + 2 (3 + 4) * 5	人类习惯，但计算机难处理（需处理括号和优先级）。
后缀表达式（逆波兰，RPN）	运算符在两个操作数之后	1 2 + 3 4 + 5 *	无括号，运算符按出现顺序处理，计算机最爱。较多
前缀表达式（波兰，PN）	运算符在两个操作数之前	+ 1 2 * + 3 4 5	较少使用。

中缀表达式 转 后缀表达式

手算方法

中缀转后缀的手算方法：
①确定中缀表达式中的各个运算符的运算顺序（运算顺序不唯一，因此对应的后缀表达式也不唯一）
②选择下一个运算符，按照【左操作符 右操作符 运算符】的方式组合成一个新的操作数；
③如果还有运算符没被处理，就继续②
“左优先”原则：只要左边的运算符能先计算，就优先算左边的（可保证运算顺序唯一）


后缀表达式的手算方法：
从左往右扫描，每遇到一个运算符，就让运算符前面最近的两个操作数执行对应运算，合体为一个操作数。
注意：两个操作数的左右顺序。

机算

如手算的所示体现出来的特点：
最后出现的操作数先被运算（即后进先出 LIFO）

后缀表达式的计算（机算）
用栈实现后缀表达式的计算：
①从左往右扫描下一个元素，直到处理完所有元素；
②若扫描到操作数则压入栈，并返回到①；否则执行③；
③若扫描到运算符，则弹出两个栈顶元素，执行相应的运算，运算结果回栈（压回栈顶），回到①；

注意：（后缀表达式的机算）先出栈的是“右操作数”

如图所示，A+B运算出结果后，则结果回栈（压回栈顶）。
若表达式合法，则最后栈中只会留下一个元素，其就是最终结果

中缀表达式 转 前缀表达式

手算方法

中缀转前缀的手算方法：
①确定中缀表达式中的各个运算符的运算顺序（运算顺序不唯一，因此对应的后缀表达式也不唯一）
②选择下一个运算符，按照【 运算符 左操作符 右操作符 】的方式组合成一个新的操作数；
③如果还有运算符没被处理，就继续②
“右优先”原则：只要右边的运算符能先计算，就优先算右边的（可保证运算顺序唯一）

机算

前缀表达式的计算（机算）
用栈实现前缀表达式的计算：
①从右往左扫描下一个元素，直到处理完所有元素；
②若扫描到操作数则压入栈，并返回到①；否则执行③；
③若扫描到运算符，则弹出两个栈顶元素，执行相应的运算，运算结果回栈（压回栈顶），回到①；

注意：（前缀表达式的机算）先出栈的是“左操作数”

总结

下图为手算的运算优先原则。
将中缀转后缀时：符号运算左优先，
将后缀转中缀时：从左到右（也可以理解为左优先，但右边是不可行的，因为运算符在右边）
中缀转前缀，前缀转中缀同理。

机算时：

• 后缀：先出栈的为右操作数
• 前缀：先出栈的为左操作数