逆波兰表达式求值：栈上直接算

本文属于「408 算法拓展训练」——考纲内、真题代码题尚未考过的经典题。逆波兰（后缀）表达式求值是「栈的应用」这一考点的另一个代表题，和括号匹配一样直观写法即满分，但真正的坑在弹出顺序上。它是经典训练题，不是真题，也不押题。

题目

给定一个逆波兰表达式（后缀表达式），其中操作数为单个数字字符，运算符为 +、-、*、/ 四种之一，各元素以数组形式给出。求该表达式的值。例如 ["3","4","2","*","+","5","-"] 对应中缀 3 + 4 * 2 - 5，值为 6。

这道题没有「尽可能高效」的要求。按拓展训练导语的分类，它属于「直观即满分」型——直白写法就是最优解，力气花在把弹出顺序和运算细节写准上。

直观解法：一个栈,从左到右扫一遍

后缀表达式的好处是运算顺序已经由书写顺序唯一确定，不需要处理优先级和括号。扫描时遇到操作数就入栈；遇到运算符，说明它要作用在刚刚入栈的那两个操作数上——栈顶正好就是它们，弹出来算完再压回去。

#include <string.h>
#include <stdlib.h>

int evalRPN(char *tokens[], int n) {
    int stack[n];
    int top = -1;

    for (int i = 0; i < n; i++) {
        char *tok = tokens[i];
        if (strcmp(tok, "+") == 0 || strcmp(tok, "-") == 0 ||
            strcmp(tok, "*") == 0 || strcmp(tok, "/") == 0) {
            int right = stack[top--];        // 先弹出的是右操作数
            int left  = stack[top--];        // 后弹出的是左操作数
            int result;
            if (strcmp(tok, "+") == 0)      result = left + right;
            else if (strcmp(tok, "-") == 0) result = left - right;
            else if (strcmp(tok, "*") == 0) result = left * right;
            else                             result = left / right;
            stack[++top] = result;
        } else {
            stack[++top] = atoi(tok);        // 操作数：入栈
        }
    }
    return stack[top];
}

拿 ["3","4","2","*","+","5","-"] 走一遍：3、4、2 依次入栈；遇到 *，弹出 2（右）和 4（左），算 4*2=8，压回；遇到 +，弹出 8（右）和 3（左），算 3+8=11，压回；5 入栈；遇到 -，弹出 5（右）和 11（左），算 11-5=6，压回。扫描结束，栈里只剩这一个值，返回 6。

复杂度：扫描数组一遍，每个元素做常数次栈操作，时间 $O (n)$ ；栈最多存 n/2+1 个操作数，空间 $O (n)$ 。

为什么它就是满分解

用总纲的「找浪费三问」审一遍，三问全部答「没有」：

有没有重复扫描？ 没有。每个 token 只读一次，处理完立刻决定入栈还是参与运算，不回头。
有没有重算已知的东西？ 没有。运算符要用的两个操作数就是栈顶最近入栈的两个值，直接弹出即可，不需要另外查找或重新计算。
有没有放着性质不用？ 没有。后缀表达式的核心性质——运算符紧跟在它的两个操作数之后——正好被栈的 LIFO 结构直接利用。

更根本的一条：求值至少要把每个 token 看一遍——读一遍数组就是 $O (n)$ 的下界，任何正确算法都躲不开。碰到下界，就没有优化空间，直观写法即最优。

真正的难点在弹出顺序和运算细节

分不在优化上,在三处容易翻车的地方：

弹出顺序：先弹出的是右操作数，后弹出的是左操作数。栈是后进先出，4、2 依次入栈后，2 在栈顶——它是后来的那个操作数，也就是运算符右边的那个。对加法、乘法这类满足交换律的运算符，顺序错了结果照样对；但对 - 和 / 这类不满足交换律的运算符，顺序一反，结果就完全错了。例如后缀 5 3 - 应该是 5-3=2，如果左右弹反就变成 3-5=-2。
除法的截断方向。整数除法在操作数有负数时，left / right 在 C 语言里是向零截断（-7 / 2 = -3），如果题目或测试用例隐含向下取整的预期，结果会不一致——写代码前要明确题面对除法语义的约定，不能想当然。
扫描结束时栈里必须恰好剩一个值。这道题默认输入是合法的后缀表达式，所以正常情况下不需要额外校验；但如果要写得严谨一点，可以在返回前断言 top == 0，帮助在调试阶段发现输入不合法或运算符/操作数弹出逻辑写错的情况。

一个栈从左到右扫一遍,看一遍

用 ["3","4","2","*","+","5","-"] 演示——操作数依次入栈，运算符弹出栈顶两个值按「先右后左」的顺序运算，结果压回：

加载可视化中...

演示为 JavaScript 版本，逻辑与上文 C 代码一一对应。

别画蛇添足

这道题结构简单,过度设计的空间不大,但有两个常见的「想复杂了」：

想先转换成中缀表达式再求值。后缀表达式本身已经消除了优先级和括号的问题,栈直接算就是最短路径,没必要多绕一步转换。
想用递归树结构（表达式树）来算。构造表达式树再求值也能得到正确答案,但这是「用栈实现队列」那种题该有的设计感——这里没必要,平添一层构树和释放内存的开销,还容易在构树的递归边界上出错。

下一步

看栈处理表达式求值的交互演示：表达式求值可视化
同属「栈的应用」的拓展题：括号匹配、中缀表达式转后缀
回到方法论源头：「暴力解到最优解」真题专题总纲

逆波兰表达式求值：栈上直接算 ​

题目 ​

直观解法：一个栈,从左到右扫一遍 ​

为什么它就是满分解 ​

真正的难点在弹出顺序和运算细节 ​

一个栈从左到右扫一遍,看一遍 ​

别画蛇添足 ​

下一步 ​