3.2.3　表达式求值

表达式求值是程序设计语言编译中一个最基本的问题。它的实现也是需要栈的加入。下面的算法是由算符优先法对表达式求值。

表达式是由运算对象、运算符、括号组成的有意义的式子。运算符从运算对象的个数上分，有单目运算符和双目运算符；从运算类型上分，有算术运算、关系运算、逻辑运算。在此仅限于讨论只含二目运算符的算术表达式。

1.中缀表达式求值

中缀表达式：每个二目运算符在两个运算量的中间，假设所讨论的算术运算符包括：＋、－、＊、／、%、＾（乘方）和括号（）。

设运算规则为：

·运算符的优先级为：（）→＾→＊、／、%→＋、－；

·有括号出现时先算括号内的，后算括号外的，多层括号，由内向外进行；

·乘方连续出现时先算最右面的。

表达式作为一个满足表达式语法规则的串存储，如表达式“3＊2＾（4＋2＊2－1＊3）－5”，它的求值过程为：自左向右扫描表达式，当扫描到3＊2时不能马上计算，因为后面可能还有更高的运算。正确的处理过程是：需要两个栈，即对象栈s1和算符栈s2。当自左至右扫描表达式的每一个字符时，若当前字符是运算对象，入对象栈，是运算符时，若这个运算符比栈顶运算符高则入栈，继续向后处理，若这个运算符比栈顶运算符低，则从对象栈出栈两个运算量，从算符栈出栈一个运算符进行运算，并将其运算结果入对象栈，继续处理当前字符，直到遇到结束符。

根据运算规则，左括号“（”在栈外时它的级别最高，而进栈后它的级别则最低了；乘方运算的结合性是自右向左，所以它的栈外级别高于栈内。也就是说，有的运算符栈内栈外的级别是不同的。当遇到右括号“）”时，一直需要对运算符栈出栈，并且作相应的运算，直到遇到栈顶为左括号“（”时，将其出栈，因此右括号“）”级别最低但它是不入栈的。对象栈初始化为空，为了使表达式中的第一个运算符入栈，算符栈中预设一个最低级的运算符“（”。根据以上分析，每个运算符栈内、栈外的级别如下：

中缀表达式表达式“3＊2＾（4＋2＊2－1＊3）－5”求值过程中两个栈的状态情况如表3－1所示。

表3－1 中缀表达式3＊2＾（4＋2＊2－1＊3）－5 的求值过程

为了处理方便，编译程序常把中缀表达式首先转换成等价的后缀表达式，后缀表达式的运算符在运算对象之后。在后缀表达式中，不再引入括号，所有的计算按运算符出现的顺序，严格从左向右进行，而不用再考虑运算规则和级别。中缀表达式“3＊2＾（4＋2＊2－1＊3）－5”的后缀表达式为“32422＊＋13＊－＾＊5－”。

2.后缀表达式求值

计算一个后缀表达式，算法上比计算一个中缀表达式简单得多。这是因为表达式中既无括号又无优先级的约束。具体做法是：只使用一个对象栈，当从左向右扫描表达式时，每遇到一个操作数就送入栈中保存，每遇到一个运算符就从栈中取出两个操作数进行当前的计算，然后把结果再入栈，直到整个表达式结束，这时送入栈顶的值就是结果。

下面是后缀表达式求值的算法，在下面的算法中假设，每个表达式是合乎语法的，并且假设后缀表达式已被存入一个足够大的字符数组A中，且以'＃'为结束字符，为了简化问题，限定运算数的位数仅为一位且忽略了数字字符串与相对应的数据之间的转换的问题。

算法3.6 表达式求值

栈中状态变化情况如表3－2所示。

表3－2 后缀表达式求值过程

3.中缀表达式转换成后缀表达式

将中缀表达式转化为后缀表达式与前述对中缀表达式求值的方法完全类似，但只需要运算符栈，遇到运算对象时直接放后缀表达式的存储区，假设中缀表达式本身合法且在字符数组A中，转换后的后缀表达式存储在字符数组B中。具体做法为：遇到运算对象顺序向存储后缀表达式的B数组中存放，遇到运算符时类似于中缀表达式求值时对运算符的处理过程，但运算符出栈后不是进行相应的运算，而是将其送入B中存放。读者不难写出算法，在此不再赘述。