表达式求值问题
表达式的表示方法
根据表示方法的不同，表达式的一般有三种：前缀（波兰）表达式 (Polish Notation)、中缀表达式以及后缀（逆波兰）表达式 (Reverse Polish Notation, RPN)。
前缀表达式：操作符置于操作数的前面，如
+ 3 4表示 “三加四”。如果操作符的元数（所需参数或算子的数量）是固定的，则语法上不需要括号也能被无歧义地解析，例如，前缀表达式* - 5 6 7，即 “五和六的差再乘以七”，由于简单的算术运算符都是二元的，因此该表达式无需括号，也无歧义。中缀表达式：操作符以中缀形式位于操作数的中间，如
3 + 4表示 “三加四”。中缀表达式符合我们日常的习惯，但是不容易被电脑解析。后缀表达式：操作符置于操作数的后面，如
3 4 +表示 “三加四”、3 2 + 5 *表示 “三加上二的结果再乘以五”。后缀表示法也不需要括号来标示操作符的优先级。后缀表达式的解析过程是基于堆栈的，其解析过程一般是：操作数入栈；遇到操作符时，操作数出栈，求值，将结果入栈；不断迭代，最终栈顶就是表达式的值。
简单算术的前缀表达式主要用于学术研究方面，而商业计算器几乎不使用这种表达式；中缀表达式是最符合人们思维方式的表达式，也是我们日常书写和输入表达式的方式；后缀表达式的求值过程对于计算机来说是很容易实现，是最符合计算机的处理方式。
这里主要讨论算术中缀和后缀表达式的求值以及二者间的转换问题。
中缀表达式直接求值
中缀表达式的直接求值，最常见的方法是使用两个堆栈：一个用于保存操作数，另一个用于保存操作符。
首先考虑只有加、减、乘、除四则运算的简单算术表达式：
\[ 3 + 2 \times 5 \]
在手动计算这个表达式时，由于我们事先知道乘法的优先级高于加法，因此我们会先计算 \(2 \times 5 = 10\)，再计算 \(3 + 10 = 13\) 得到最终的结果。
对于计算机来说，由于使用堆栈来计算和保存结果，就需要专门设计入栈和出栈规则。因为四则运算的运算符都是二元运算符，即需要两个操作数才能完成计算，但是由于操作符位于操作数的中间，所以当一个操作符进操作符栈时，该操作符的两个操作数并没有都进入到操作数栈中。因此，只有在后面一个操作符进操作符栈时，前面的一个操作符所作用的两个操作数才会全部进栈。我们来看操作数栈和操作符栈的变化过程：
| 序号 | 操作数栈 | 操作符栈 |
|---|---|---|
| 1 | \(3\) | 空 |
| 2 | \(3\) | \(+\) |
| 3 | \(3,\ 2\) | \(+\) |
此时，遇到操作符 \(\times\)，如果弹出 \(3\)、\(2\) 以及 \(+\) 进行计算，则原表达式就变成了 \((3 + 2) \times 5\)，得到错误的结果。由于当前操作符优先级高于操作符栈栈顶元素的优先级，故需要将当前操作赋压入操作符栈，并将当前操作符的操作数也压入栈。
| 序号 | 操作数栈 | 操作符栈 |
|---|---|---|
| 4 | \(3,\ 2\) | \(+,\ \times\) |
| 5 | \(3,\ 2,\ 5\) | \(+,\ \times\) |
此时，到了表达式的结尾，依次弹出操作数栈顶部的两个元素，再弹出操作符栈顶的元素，进行计算，将计算后的结果压入操作数栈，并不断重复这个过程，直到操作符栈为空，且操作数栈只有一个元素，即表达式的最终结果。
| 序号 | 操作数栈 | 操作符栈 |
|---|---|---|
| 6 | \(3,\ 10\) | \(+\) |
| 7 | \(13\) | 空 |
对于带有括号的等更复杂的表达式，其计算过程与上面类似：遇到 \((\) 则直接压入操作符栈；遇到 \()\) 则一直弹出操作符和对应的操作数，将计算结果再压入操作数栈，重复这个过程直到将 \((\) 也弹出。
中缀表达式的直接求值有一条原则：当前操作符的优先级高于操作符栈栈顶操作符的优先级时，将当前操作符压入操作符栈；否则，弹出操作符以及对应的操作数进行计算直至栈顶操作符的优先级低于当前操作符，然后将当前操作符压栈。当所有的操作符处理完毕（即操作符栈为空时），操作数栈中剩下的唯一一个元素就是最终表达式的值。
对于常用的算术运算符，\(+\) 与 \(-\) 的优先级相同；\(\times\) 与 \(\div\) 的优先级相同，且高于\(+\)、\(-\) 的优先级；而 \(()\) 的优先级最高。此外，还需要根据情况区分 \(-\) 是表示负号还是减号：
- 若前面为 \((\) 或其他运算符，则表示负号
- 若前面为 \()\) 或数字，则表示减号
- 若前面没有字符，即 \(-\) 是表达式的开始，则表示负号
后缀表达式直接求值
后缀表达式不需要括号来标示操作符的优先级，因此可以直接利用栈来模拟计算：遇到操作数就将其直接压入操作数栈；遇到操作符则弹出操作数栈顶的两个元素进行计算，再将计算结果压入操作数栈；如此循环，直到表达式结尾，操作数栈中唯一的元素就是表达式的结果。
中缀表达式转换为后缀表达式
利用二叉树转换
利用二叉树的性质，可以方便地将中缀表达式转换为后缀表达式。首先利用二叉树表示中缀表达式：用叶子节点存储操作数，其他节点存储操作符；再对二叉树进行遍历即可得到后缀表达式。以表达式
\[ 3 \times 5 + 5 \div 2 + (3 + 5) \times 2 \]
为例，将其表示成二叉树形式，如下图所示。
将中缀表达式表示为二叉树形式的过程如下：
- 找出表达式中最后进行运算的操作符，即优先级最低的操作符，作为根节点
- 在步骤 1 找出的操作符的左侧部分找出最后进行运算的操作符，作为步骤 1 根节点的左子节点；右侧部分进行同样的操作
- 若步骤 1 找出的操作符左侧或右侧部分只含有操作数，不含有操作符，则将该操作数作为对应的叶子节点。
- 不断重复上述过程直到二叉树包含表达式的所有操作数和操作符
建立完毕表达式的二叉树，从叶子节点开始对二叉树进行后序遍历（左子树->右子树->根节点），即可得到中缀表达式对应的后缀表达式。
利用栈转换
利用栈将中缀表达式转换为后缀表达式的过程与计算中缀表达式的过程类似，使用一个栈保存操作符，一个数组用于保存转换得到的后缀表达式。其过程如下：
- 从头到尾扫描表达式，若遇到操作符，则与操作符栈的栈顶元素比较优先级：如果当前操作符优先级高于栈顶元素的优先级，则压入操作符栈；否则不断弹出操作符栈顶元素添加到结果数组的末尾，直到栈顶元素的优先级低于当前操作符的优先级，将当前操作符压入操作符栈
- 若遇到操作数，则直接添加到结果数组的末尾
- 若遇到左括号，则压入操作符栈
- 若遇到右括号，则依次弹出操作符栈顶元素添加到结果数组的末尾，直到遇到左括号，将左括号弹出操作符栈
手动转换
通过对表达式的每一部分添加括号，再将操作符移动到对应括号的后面，也可以方便地将中缀表达式转换为后缀表达式。例如中缀表达式
\[ (3 + 5 \times 2) - 2 \times 3 \]
转换过程如下：
- 首先对每一部分添加括号，则有 \(((3 + (5 \times 2)) - (2 \times 3))\)
- 将操作符移动到对应括号的后面：\(((3\ (5\ 2)\times) + (2\ 3)\times)-\)
- 最后去掉所有括号，可得对应的后缀表达式 \(3\ 5\ 2 \times +\ 2\ 3 \times -\)