在严蔚敏教授的《数据结构》（人民邮电出版社，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 是操作数栈）：

【算法步骤】

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; //将连续的数字字符转换成对应的数值存放到 d
                while(*postexp >= '0' && *postexp <= '9'){
                    d = 10 * d + *postexp - '0';
                    postexp++;
                }
                Push(Opnd, d);
                break;
        }
        postexp++;
    }
    GetTop(Opnd, e);
    DestroyStack(Opnd);
    return e;
}

由上可知：

1. 栈自动记录中间结果，容易对任意复杂的表达式求值。
2. 后缀表达式中不需要括号，只需按照表达式顺序求值，让栈自动记录中间结果；也不需要指定操作符的优先级。
3. 机器状态永远是一个栈状态，栈里是需要运算的操作数，栈内不会有操作符。

2. 理解教材的案例

严蔚敏教授在《数据结构》（人民邮电出版社，2015年2月第2版）案例 3.3 中，给出了一个运算符优先关系表，如下表所示：

表中显示了运算符之间的三种关系：

• ${\theta }_1<{\theta }_2$ ，${\theta }_1$ 的优先权低于 ${\theta }_2$ ，例如：${}^{\prime }{+}^{\prime }{<}^{\prime }{\ast }^{\prime };{}^{\prime }{+}^{\prime }{<}^{\prime }{/}^{\prime };$ 即“先乘除、后加减”的运算规则。
• ${\theta }_1={\theta }_2$ ，${\theta }_1$ 的优先权等于 ${\theta }_2$ 。注意：先出现的运算符优先级高，所以有：${}^{\prime }{+}^{\prime }{>}^{\prime }{+}^{\prime };{}^{\prime }{-}^{\prime }{>}^{\prime }{-}^{\prime };$ 等。
• ${\theta }_1>{\theta }_2$ ，${\theta }_1$优先权高于 ${\theta }_2$ ，括号内的优先级高，+、-、*、/ 为 ${\theta }_1$ 时的优先性均低于 ( ，但高于 ) 。
• 表中的“( = )”表示当左右括号相遇时，括号内的运算已经完成。
• 为了便于实现，假设每个表达式均以 # 开始，以 # 结束。所以 # = # 表示整个表达式求值完毕。
• 表中空白的部分，即 ) 与 ( 、# 与 ) 、以及 ( 与 # 之间无优先关系，这是因为表达式中不允许它们相继出现，一旦遇到这种情况，则可以认为出现了语法错误。

为了实现上述算符优先算法，设置两个栈：

• 寄存运算符的栈，命名为 Optr ；
• 寄存操作数或运算结果的栈，命名为 Opnd 。

【算法步骤】

1. 初始化 Optr 栈和 Opnd ，将表达式起始符 # 压入 Optr 栈。
2. 扫描表达式，读入第一个字符 ch，如果表达式没有扫描完毕至 # 或 Optr 的栈顶元素不为 # 时，则循环执行以下操作：
   • 若 ch 不是运算符，则压入 Opnd 栈，读入下一字符 ch；
   • 若 ch 是运算符，则根据 Optr 的栈顶元素和 ch 的优先级比较结果，做不同的处理：
     • 若是小于，则 ch 压入 Optr 栈，读入下一字符 ch；
     • 若是大于，则弹出 Optr 栈顶的运算符，从 Opnd 栈弹出两个数，进行相应运算，结果压入 Opnd 栈；
     • 若是等于，则 Optr 的栈顶元素是 ( 且 ch 是 )，这时弹出 Optr 栈顶的 ( ，相当于括号匹配成功，然后读入下一字符 ch 。
3. 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; //读入下一字符 ch
                    break;
                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; //读入下一字符 ch
                    break;
        }
    }
    return GetTop(OPND); //Opnd 栈顶元素即为表达式求值结果
}

上述算法描述中使用到了三个函数：

• 第 9 行出现的函数 In() ，用于判定读入的字符 ch 是否为运算符；
• 第 13 行出现的函数 Precede() ，用于判定运算符栈的栈顶元素与读入的运算符之间优先关系；
• 第 22 行出现的函数 Operate() 用于进行二元运算。

【算法分析】

• 时间复杂度：$O(n)$ ；
• 空间复杂度：$O(n)$ 。