更新时间：2024-06-19 13:19
表达式计算(expression evaluation)是程序设计语言编译中的一个最基本问题，也是早期计算机语言研究的一项重要成果，它使得高级语言程序员可以使用与数学形式相一致的方式书写表达式，如a*b+c/d-c(x+y)。计算机科学计算语言FORTRAN就因Formula Translator(公式翻译家)而得名。
高级程序设计语言允许多种类型的表达式：算术表达式、关系表达式和逻辑表达式等。
表达式由操作数、运算符和括号组成。表达式习惯的书写形式是一个双目运算符(binary operator)位于两个操作数之间，如a+b，这类表达式称为中缀表达式(infix expression)。除了双目运算符外，还有单目运算符(unary operator)，如I++和一a。条件运算符是C语言中唯一的三目运算符(ternary operator)。为正确计算表达式的值，任何程序设计语言都明确规定了运算符的优先级。在C语言中，当使用括号时，从最内层括号开始计算；对于相邻的两个运算符，优先级高的先计算；如果两个运算符的优先级相同，运算次序由结合方向决定。例如，*与/是自左向右结合的，因此，a*b/c的运算次序是先乘后除。
在中缀表达式中，运算符具有不同的优先级，并且还可以使用括号改变运算的次序，因此运算规律比较复杂，不适于计算机求解表达式。与中缀表达式相对应的还有后缀表达式和前缀表达式。
运算符在操作数之后的表达式称为后缀表达式。
后缀表达式的特点如下：
1、后缀表达式的操作数与中缀表达式的操作数先后次序相同，而运算符的先后次序不同；
2、后缀表达式中没有括号，而且运算符没有优先级；
3、后缀表达式计算过程严格按照从左到右的顺序进行。
从以上特点可以看出，后缀表达式比较适合计算机求解。求解后缀表达式的过程为：从左到有依次扫描后缀表达式，若遇到运算符，则对该运算符前面的连续两个操作数用该运算符进行运算。
运算符在操作数之前的表达式称为前缀表达式。
前缀表达式的特点与后缀表达式的特点相同，只是求解过程不同，其求解过程为：从右到左依次扫描前缀表达式，若遇到运算符，则对该运算符后面的连续两个操作数用该运算符进行运算。
综上所述，利用计算机求解表达式分为两个步骤：
1、把中缀表达式转换为后缀表达式或前缀表达式；
2、按照后缀表达式或前缀表达式的运算过程计算表达式的值。
中缀表达式转换为后缀表达式
由后缀表达式的特点可以知道，后缀表达式的操作数与中缀表达式的操作数先后次序相同，只是运算符的先后次序不同，因此，可以利用栈来保存运算符，具体转换过程如下：
1、设置一个存放运算符的栈(运算符栈)，并置栈顶元素为“#”。“#”作为标识表达式开始的标志，另外在表达式的尾部添加一个“#”，把它作为标识表达式结束的标志。
2、从左到右依次扫描表达式，每次取出一个字符(操作数、运算符和括号均看作一个字符)。
3、若字符是操作数，则直接输出到后缀表达式中。
4、若字符是运算符，则与栈顶运算符进行比较。如果它的优先级比栈顶运算符优先级高，则直接入栈；如果它的优先级比栈顶运算符优先级低或相等，则栈顶运算符出栈并输出到后缀表达式中。
5、若字符是“(”，则直接入栈。
6、若字符是“)”，则判断栈顶运算符是否为“(”。若不是，则栈顶运算符出栈，并输出到后缀表达式中，依次进行，直至栈顶运算符为“(”，抛弃“(”和“)”。、
7、若字符是“#”，则栈顶运算符依次出栈，并输出到后缀表达式中，直至栈顶运算符为“#”，抛弃“#”。
8、重复步骤2～7，直至表达式结束。
求后缀表达式的值
由于后缀表达式不需考虑运算符的优先级，因此计算较简单。计算过程为：从左到右依次扫描后缀表达式，遇到运算符，则与运算符前边连续两个操作数做运算。
由于遇到操作数时，不能立即进行计算，因此设立一个栈(操作数栈)，用于存放操作数。具体运算过程如下：
1、从左到右依次扫捕后缀表达式，每次取出一个字符；
2、若字符是操作数，则入栈；
3、若字符是运算符，则连续出栈两个操作数，计算它们的值，然后把运算结果入栈；
4、重复步骤1～3，直至表达式结束，栈中最后一个元素即是后缀表达式的值。