[科普中国]-表达式计算

概述

高级程序设计语言允许多种类型的表达式：算术表达式、关系表达式和逻辑表达式等。

表达式由操作数、运算符和括号组成。表达式习惯的书写形式是一个双目运算符(binary operator)位于两个操作数之间，如a+b，这类表达式称为中缀表达式(infix expression)。除了双目运算符外，还有单目运算符(unary operator)，如I++和一a。条件运算符是C语言中唯一的三目运算符(ternary operator)。为正确计算表达式的值，任何程序设计语言都明确规定了运算符的优先级。在C语言中，当使用括号时，从最内层括号开始计算；对于相邻的两个运算符，优先级高的先计算；如果两个运算符的优先级相同，运算次序由结合方向决定。例如，*与/是自左向右结合的，因此，a*b/c的运算次序是先乘后除。1

在中缀表达式中，运算符具有不同的优先级，并且还可以使用括号改变运算的次序，因此运算规律比较复杂，不适于计算机求解表达式。与中缀表达式相对应的还有后缀表达式和前缀表达式。

运算符在操作数之后的表达式称为后缀表达式。

后缀表达式的特点如下：

1、后缀表达式的操作数与中缀表达式的操作数先后次序相同，而运算符的先后次序不同；

2、后缀表达式中没有括号，而且运算符没有优先级；

3、后缀表达式计算过程严格按照从左到右的顺序进行。

从以上特点可以看出，后缀表达式比较适合计算机求解。求解后缀表达式的过程为：从左到有依次扫描后缀表达式，若遇到运算符，则对该运算符前面的连续两个操作数用该运算符进行运算。

运算符在操作数之前的表达式称为前缀表达式。

前缀表达式的特点与后缀表达式的特点相同，只是求解过程不同，其求解过程为：从右到左依次扫描前缀表达式，若遇到运算符，则对该运算符后面的连续两个操作数用该运算符进行运算。

综上所述，利用计算机求解表达式分为两个步骤：

1、把中缀表达式转换为后缀表达式或前缀表达式；

2、按照后缀表达式或前缀表达式的运算过程计算表达式的值。2

中缀表达式转换为后缀表达式由后缀表达式的特点可以知道，后缀表达式的操作数与中缀表达式的操作数先后次序相同，只是运算符的先后次序不同，因此，可以利用栈来保存运算符，具体转换过程如下：

1、设置一个存放运算符的栈(运算符栈)，并置栈顶元素为“#”。“#”作为标识表达式开始的标志，另外在表达式的尾部添加一个“#”，把它作为标识表达式结束的标志。

2、从左到右依次扫描表达式，每次取出一个字符(操作数、运算符和括号均看作一个字符)。

3、若字符是操作数，则直接输出到后缀表达式中。

4、若字符是运算符，则与栈顶运算符进行比较。如果它的优先级比栈顶运算符优先级高，则直接入栈；如果它的优先级比栈顶运算符优先级低或相等，则栈顶运算符出栈并输出到后缀表达式中。

5、若字符是“(”，则直接入栈。

6、若字符是“)”，则判断栈顶运算符是否为“(”。若不是，则栈顶运算符出栈，并输出到后缀表达式中，依次进行，直至栈顶运算符为“(”，抛弃“(”和“)”。、

7、若字符是“#”，则栈顶运算符依次出栈，并输出到后缀表达式中，直至栈顶运算符为“#”，抛弃“#”。

8、重复步骤2～7，直至表达式结束。2

求后缀表达式的值由于后缀表达式不需考虑运算符的优先级，因此计算较简单。计算过程为：从左到右依次扫描后缀表达式，遇到运算符，则与运算符前边连续两个操作数做运算。

由于遇到操作数时，不能立即进行计算，因此设立一个栈(操作数栈)，用于存放操作数。具体运算过程如下：

1、从左到右依次扫捕后缀表达式，每次取出一个字符；

2、若字符是操作数，则入栈；

3、若字符是运算符，则连续出栈两个操作数，计算它们的值，然后把运算结果入栈；

4、重复步骤1～3，直至表达式结束，栈中最后一个元素即是后缀表达式的值。2