《数据结构》栈在表达式值中的应用

表达式求值是程序设计语言编译中一个最基本的问题，它的实现是栈应用的一个典型范例。

中缀表达式转为后缀表达式

我们遵循以下规则，顺序扫描中缀表达式中的每一项，将中缀表达式转为后缀表达式：

1.若遇到数字：直接将其输出

2.若遇到非数字（即遇到运算符号）：
　　2.1 若栈为空，直接入栈

　　2.2 若栈非空：

　　　　2.2.1 若栈顶元素为左括号，直接入栈

　　　　2.2.2 若入栈元素为左括号，直接入栈

　　　　2.2.3 若栈顶元素运算优先级大于或者等于该运算符号，则持续出栈，直到栈顶元素优先级小于即将入栈的运算符的优先级，将该元素入栈
　　　　2.2.4 若入栈元素为右括号，则持续出栈，直至左括号出栈

3.若遇到输入的末尾，将栈中所有元素依次弹出

后缀表达式求值

顺序扫描后缀表达式的每一项，根据它的类型做如下相应操作：

• 如果该项是操作数，则将其压入栈中
• 如果该项是操作符 op，则连续从栈中弹出两个操作数 Y 和 X，形成运算指令 X op Y，并将计算结果重新压入栈中。

当表达式中的所有项都扫描并处理完后，栈顶存放的就是最后的计算结果