在严蔚敏教授的《数据结构》（人民邮电出版社，2015年2月第2版）案例 3.3：表达式求值（第78页）中，对后缀表达式求值有详细叙述，但其内容令部分基础不足够好的学习者费解，为此，本节先以简单的形式对后缀表达式求值方法给予介绍，而后解释书中的难点。
1. 初步理解
后缀表达式的求值过程是：从左到右扫描后缀表达式 postexp：
- 若读取的是一个操作数，将它压入操作数栈；
- 若读取的是一个运算符
op，从操作数栈中连续出栈两个操作数，假设为a（第 1个出栈元素）和b（第 2 个出栈元素），计算b op a的值，并将计算结果进操作数栈。 - 当整个后缀表达式扫描结束时，操作数栈中的栈顶元素就是表达式的计算结果。
以中缀表达式 (56 - 20) / (4 + 2) 为例，它对应的后缀表达式为 56 20 - 4 2 + / ，如果利用栈，扫描这个后缀表达式 56 20 - 4 2 + / ，求值过程如下（Opnd 是操作数栈）：
| 操作 | Opnd 栈（栈底→栈顶） |
|---|---|
| 遇到 56，将其进栈 | 56 |
| 遇到 20，将其进栈 | 56, 20 |
| 遇到 -，依次将 20、56 出栈，计算 56-20=36，将结果 36 进栈 | 36 |
| 遇到 4，将其进栈 | 36, 4 |
| 遇到 2，将其进栈 | 36, 4, 2 |
| 遇到 +，依次将 2、4 出栈，计算 4+2=6，将结果 6 进栈 | 36, 6 |
| 遇到 /，依次将 6, 36 出栈，计算 36/6=6，将结果 6 进栈 | 6 |
| postexp 扫描完毕，算法结束，栈顶数值 6 即为所求。 |
【算法步骤】
while(从 postexp 读取字符 ch，ch ！= '\0'){ch 为 + : 从 Opnd 中出栈两个数值 a 和 b，计算 b+a=c; 将 c 进栈;ch 为 - : 从 Opnd 中出栈两个数值 a 和 b，计算 b-a=c; 将 c 进栈;ch 为 * : 从 Opnd 中出栈两个数值 a 和 b，计算 b*a=c; 将 c 进栈;ch 为 / : 从 Opnd 中出栈两个数值 a 和 b，若 a 不为零，计算 b/a=c; 将 c 进栈;ch 为数字字符 : 将连续的数字串转换成整数 d，将 d 进栈;
}
【算法描述】
double comp_value(char * postexp){double d, a, b, c, e;SqStack * Opnd; //操作数栈，顺序栈InitStack(Opnd); while(*postexp != '\0'){//postexp字符未扫描完毕，循环switch(*postexp){case '+':Pop(Opnd, a);Pop(Opnd, b);c = b + a;Push(Opnd, c);break;case '-':Pop(Opnd, a);Pop(Opnd, b);c = b - a;Push(Opnd, c);break;case '*':Pop(Opnd, a);Pop(Opnd, b);c = b * a;Push(Opnd, c);break;case '/':Pop(Opnd, a);Pop(Opnd, b);if(a != 0){c = b / a;Push(Opnd, c);break;} else {printf("\n\t零不能做分母\n");exit(0);}break;default:d = 0; //将连续的数字字符转换成对应的数值存放到 dwhile(*postexp >= '0' && *postexp <= '9'){d = 10 * d + *postexp - '0';postexp++;}Push(Opnd, d);break;}postexp++;}GetTop(Opnd, e);DestroyStack(Opnd);return e;
}
由上可知：
- 栈自动记录中间结果，容易对任意复杂的表达式求值。
- 后缀表达式中不需要括号，只需按照表达式顺序求值，让栈自动记录中间结果；也不需要指定操作符的优先级。
- 机器状态永远是一个栈状态，栈里是需要运算的操作数，栈内不会有操作符。
2. 理解教材的案例
严蔚敏教授在《数据结构》（人民邮电出版社，2015年2月第2版）案例 3.3 中，给出了一个运算符优先关系表，如下表所示：
表中显示了运算符之间的三种关系：
- θ 1 < θ 2 \theta_1\lt\theta_2 θ1<θ2 ， θ 1 \theta_1 θ1 的优先权低于 θ 2 \theta_2 θ2 ，例如： ′ + ′ < ′ ∗ ′ ; ′ + ′ < ′ / ′ ; '+'\lt'*';~'+'\lt'/';~ ′+′<′∗′; ′+′<′/′; 即“先乘除、后加减”的运算规则。
- θ 1 = θ 2 \theta_1=\theta_2 θ1=θ2 ， θ 1 \theta_1 θ1 的优先权等于 θ 2 \theta_2 θ2 。注意：先出现的运算符优先级高，所以有： ′ + ′ > ′ + ′ ; ′ − ′ > ′ − ′ ; '+'\gt'+';~'-'\gt'-';~ ′+′>′+′; ′−′>′−′; 等。
- θ 1 > θ 2 \theta_1\gt\theta_2 θ1>θ2 ， θ 1 \theta_1 θ1优先权高于 θ 2 \theta_2 θ2 ，括号内的优先级高，
+、-、*、/为 θ 1 \theta_1 θ1 时的优先性均低于(，但高于)。 - 表中的“
( = )”表示当左右括号相遇时，括号内的运算已经完成。 - 为了便于实现，假设每个表达式均以
#开始，以#结束。所以# = #表示整个表达式求值完毕。 - 表中空白的部分，即
)与(、#与)、以及(与#之间无优先关系，这是因为表达式中不允许它们相继出现，一旦遇到这种情况，则可以认为出现了语法错误。
为了实现上述算符优先算法，设置两个栈：
- 寄存运算符的栈，命名为
Optr； - 寄存操作数或运算结果的栈，命名为
Opnd。
【算法步骤】
- 初始化
Optr栈和Opnd，将表达式起始符#压入Optr栈。 - 扫描表达式，读入第一个字符
ch，如果表达式没有扫描完毕至#或Optr的栈顶元素不为#时，则循环执行以下操作：- 若
ch不是运算符，则压入Opnd栈，读入下一字符ch； - 若
ch是运算符，则根据Optr的栈顶元素和ch的优先级比较结果，做不同的处理：- 若是小于，则
ch压入Optr栈，读入下一字符ch； - 若是大于，则弹出
Optr栈顶的运算符，从Opnd栈弹出两个数，进行相应运算，结果压入Opnd栈； - 若是等于，则
Optr的栈顶元素是(且 ch 是)，这时弹出Optr栈顶的(，相当于括号匹配成功，然后读入下一字符ch。
- 若是小于，则
- 若
Opnd栈顶元素即为表达式求值结果，返回此元素。
【算法描述】
char EvaluateExpression(){//算术表达式求值的算符优先算法，设 OPTR 和 OPND 分别为运算符栈和操作数栈Initstack(Opnd); //初始化 Opnd 栈Initstack(Optr); //初始化 Optr 栈Push(Optr, '#'); //将表达式起始符 '#' 压入 Optr 栈cin>>ch;while(ch !='#' || GetTop(Optr) !='#'){//表达式没有扫描完毕或 Optr 的栈顶元素不为 '#'if(!In(ch)){ //ch 不是运算符则进 Opnd 栈Push(Opnd, ch);cin>>ch;} else{switch(Precede(GetTop(Optr), ch)) //比较 Optr 的栈顶元素和 ch 的优先级case '<':Push(Optr, ch);//当前字符 ch 压入 Optr 栈，cin>>ch; //读入下一字符 chbreak;case '>':Pop(Optr, theta); //弹出 Optr 栈顶的运算符Pop(Opnd, b); //弹出 Opnd 栈顶的两个操作数Pop(Opnd, a);Push(Opnd, Operate(a, theta, b)); //将运算结果压入 Opnd 栈break;case '=': //Optr 的栈顶元素是 '(' 且 ch 是 ')'Pop(Optr, x); //弹出 Optr 栈顶的 '('cin>>ch; //读入下一字符 chbreak;}}return GetTop(OPND); //Opnd 栈顶元素即为表达式求值结果
}
上述算法描述中使用到了三个函数：
- 第 9 行出现的函数
In()，用于判定读入的字符ch是否为运算符； - 第 13 行出现的函数
Precede()，用于判定运算符栈的栈顶元素与读入的运算符之间优先关系； - 第 22 行出现的函数
Operate()用于进行二元运算。
【算法分析】
- 时间复杂度： O ( n ) O(n) O(n) ；
- 空间复杂度： O ( n ) O(n) O(n) 。
