3.2.3 算术表达式求值

表达式求值是程序设计语言编译中的一个基本问题。在编译系统中，需要把人们便于理解的表达式翻译成计算机理解的表示序列，这就可以利用栈的“后进先出”特性实现表达式的转换。

一个表达式由操作数（Operand）、运算符（Operator）和分界符（Delimiter）组成。一般地，操作数可以是常数，也可以是变量；运算符可以是算术运算符、关系运算符和逻辑运算符；分界符包括左右括号和表达式的结束符等。为了简化问题的描述，我们仅讨论简单算术表达式的求值问题。这种表达式只包含加、减、乘、除等四种运算符和左、右圆括号。

计算机编译系统在计算算术表达式的值时，需要先将中缀表达式转换为后缀表达式，然后求解表达式的值。

1.将中缀表达式转换为后缀表达式

例如，一个算术表达式为：

a-（b+c*d）/e

这种算术表达式中的运算符总是出现在两个操作数之间，这种算术表达式被称为中缀表达式。编译系统在计算一个算术表达式之前，要将中缀表达式转换为后缀表达式，然后对后缀表达式进行计算。在后缀表达式中，算术运算符出现在操作数之后，并且不含括号。

上面的算术表达式对应的后缀表达式为：

abcd*+e/-

中缀表达式与后缀表达式相比，具有以下两个特点：

（1）后缀表达式与中缀表达式的操作数出现顺序相同，只是运算符先后顺序改变了。

（2）后缀表达式不出现括号。

说明：由于后缀表达式具有以上特点，所以，编译系统在处理时不必考虑运算符的优先关系。只要从左到右依次扫描后缀表达式的各个字符，当读到的字符为运算符时，对运算符前面的两个操作数利用该运算符运算，并将运算结果作为新的操作对象替换两个操作数和运算符，继续扫描后缀表达式，直到处理完毕。

综上，表达式的运算分为两个步骤：

（1）将中缀表达式转换为后缀表达式。

（2）依据后缀表达式计算表达式的值。

将一个算术表达式的中缀形式转换为相应的后缀形式前，需要先了解算术四则运算的规则。算术四则运算的规则是：

（1）先计算乘除，后计算加减。

（2）先计算括号内的表达式，后计算括号外的表达式。

（3）同级别的运算从左到右进行计算。

如何将中缀表达式转换为后缀表达式呢？设置一个栈，用于存放运算符。依次读入表达式中的每个字符，如果是操作数，则直接输出；如果是运算符，则比较栈顶元素符与当前运算符的优先级，然后进行处理，直到整个表达式处理完毕。这里，约定‘#’作为后缀表达式的结束标志，假设栈顶运算符为ө₁，当前扫描的运算符为ө₂。

中缀表达式转换为后缀表达式的算法如下：

（1）初始化栈，将‘#’入栈。

（2）如果当前读入的字符是操作数，则将该操作数输出，并读入下一个字符。

（3）如果当前字符是运算符，记作ө₂，则将ө₂与栈顶的运算符ө₁比较。如果栈顶的运算符ө₁的优先级小于当前运算符ө₂，则将当前运算符ө₂进栈；如果栈顶的运算符ө₁的优先级大于当前运算符 ө₂，则将栈顶运算符 ө₁出栈并将其作为后缀表达式输出。然后继续比较新的栈顶运算符ө₁与当前运算符ө₂的优先级，如果栈顶运算符ө₁的优先级与当前运算符ө₂相等，且ө₁为‘（’，ө₂为‘）’，则将ө₁出栈，继续读入下一个字符。

（4）如果当前运算符 ө₂的优先级与栈顶运算符 ө₁相等，且 ө₁和 ө₂都为‘#’，将 ө₁出栈，栈为空。则中缀表达式转换为后缀表达式，算法结束。

运算符优先关系表如表3.1所示。

中缀表达式a-（b+c*d）/e转换为后缀表达式的输出过程如表3.2所示。

2.后缀表达式的计算

计算后缀表达式的值需要设置一个operator栈，用于存放操作数和中间运算结果。依次读入后缀表达式中的每个字符，如果是操作数，则将操作数进入operand栈；如果是运算符，则将操作数出栈两次，然后对操作数进行当前操作符的运算，直到整个表达式处理完毕。

后缀表达式的求值算法如下（假设栈顶运算符为ө₁，当前扫描的运算符为ө₂）：

（1）初始化operand栈。

（2）如果当前读入的字符是操作数，则将该操作数进入operand栈。

（3）如果当前字符是运算符 ө，则将operand栈退栈两次，分别得到操作数x和y，对x和y进行ө运算，即yөx，得到中间结果z，将z进入operand栈。

（4）重复执行步骤（2）和（3），直到operand栈空为止。

3.表达式的运算举例

【例3.2】 利用栈将中缀表达式（5*（12-3）+4）/2转换为后缀表达式，并计算后缀表达式的值。

【分析】设置两个字符数组str和exp，str用来存放中缀表达式的字符串，exp用来存放后缀表达式的字符串。将中缀表达式转换为后缀表达式的方法是：依次扫描中缀表达式，如果遇到数字则将其存入数组exp中。如果遇到运算符，则将栈顶运算符与当前运算符比较，如果当前运算符的优先级大于栈顶运算符的优先级，则将当前运算符进栈；如果栈顶运算符的优先级大于当前运算符的优先级，则将栈顶运算符出栈，并保存到数组exp中。

为了处理方便，在遇到数字字符时，需要在其后补一个空格，作为分隔符。在计算后缀表达式的值时，需要对两位数以上的字符进行处理，将处理后的数字然后入栈。

中缀表达式转换为后缀表达式的算法如下。

计算后缀表达式的值的算法如下：

测试程序如下：

程序运行结果如图3.9所示。