C++实现波兰表达式求值：递归与栈两种方案详解

刚从一堆乱码似的中缀表达式里调完一个计算器，又遇到需要按前缀方式求值的场景。我第一反应是：这不是数据结构课本上那个“波兰表达式”吗？当年只是背了定义，真到用 C++ 落地时，细节远比想象的多。如果你也在写表达式求值、解释器，或者只是想搞懂递归和栈在这类问题里到底怎么配合，这篇文章就用 C++ 把波兰表达式求值彻底说清楚。

所谓波兰表达式，正式名称是前缀表达式。它的特点是把运算符放在两个操作数之前，比如中缀 (3 + 4) * 2 写成前缀就是 * + 3 4 2。刚看会觉得反直觉，但一旦接受这个设定，你会发现括号和运算符优先级完全消失了，求值过程非常机械化。下面我会从原理讲到两种可落地的 C++ 实现，再给出测试用例和一堆踩坑记录。不想只贴代码让你抄，是想让你做完之后能自信地说“这题我会了”。

1. 波兰表达式是什么：从人类习惯到机器偏好

1.1 中缀、前缀、后缀三种记法的区别

上课的时候老师总喜欢把三种记法摆在一起对比。中缀表达式 3 + 4 * 2 是我们日常看到的，运算符在操作数中间。要做到先乘后加，必须靠优先级规则；如果优先级改变还要加括号，例如 (3 + 4) * 2。这个过程对人来说很自然，但交给程序处理时，你得维护一个优先级表，还要处理括号的嵌套。

前缀表达式则完全不同，它把运算符统一写到操作数前面。+ * 3 4 2 这种写法虽然人眼第一眼看不惯，但程序可以从头到尾线性扫描，不需要回看多个字符去判断优先级。后缀表达式是正好相反，运算符放最后，3 4 + 2 * 就是上面那个中缀式。三种记法其实描述的是同一棵表达式树：中缀是二叉树的中序遍历，前缀是前序遍历，后缀是后序遍历。如果你画过表达式树，马上就能理解为什么前缀表达式的运算符顺序就是树的先根顺序。

1.2 为什么今天还要关注它

有人会问，现在写业务代码谁还手动做表达式求值？但现实是，前缀表达式在一些地方依然活跃。比如 Lisp 家族的 S-表达式，本质上就是前缀加括号；很多编译器的中间表示在存表达式时，也会选择把运算符放在前面，这样对后续遍历更友好；表达式树的序列化、AST 的线性输出，用前缀格式可以做到无歧义且易恢复。

更重要的是，波兰表达式是理解递归下降和栈求值的最佳练习题。一个前缀表达式天然就是递归结构：遇到运算符，后面一定跟两个子表达式；遇到数字，就是一个叶子。递归求值是顺着这个结构直接翻译的；如果不想用递归，又能改成栈来模拟。这两个转换恰好是很多业务系统的核心思路，比如公式引擎、规则引擎、甚至 SQL 查询计划中的表达式计算。所以学这个不是考古，是真能派上用场。

2. 拿到前缀表达式后，我先想的是这两条路

2.1 递归下降：把解析和求值合并

既然是前缀表达式，那递归定义就摆在眼前：

• 表达式要么是一个数字，要么是 运算符 表达式 表达式。

这个定义可以直接映射成 C++ 递归函数。读到运算符 + - * /，就递归往下读两个操作数；读到数字，就转成 double 返回。不需要优先级表，不需要括号匹配，只需要保证 token 的顺序正确。递归调用栈天然充当了“记录当前计算到哪一步”的机制。

用递归的好处是代码和数学定义一一对应，可读性非常高。坏处是如果表达式嵌套特别深，比如几十万层括号嵌套，递归可能直接爆掉系统栈。当然，正常人不会写出这种表达式，但如果你做一个线上服务，输入是来自用户或第三方的，那你就得考虑恶意输入导致栈溢出的可能。这也是我后来坚持把栈版本也写出来的原因。

2.2 显式栈：用空间换栈帧

所有递归都能改成显式栈，前缀求值也不例外。对前缀表达式求值，正确的扫描方向是从右往左。

我从右往左读 token：遇到数字先压到栈里；遇到运算符，从栈里弹出两个数字做运算，再把结果压回去。为什么是从右往左？因为前缀表达式的叶子在最右边，计算必须从叶子开始。栈在这里替我们保管“已经算完的子结果”，等运算符到来时再组合。

这个思路一旦想通，代码基本就是一道波利亚式的练习题。而且用显式栈不会因为表达式嵌套过深而爆栈，最多因内存不足而分配失败，但那已经是很极端的情况了。下面两节会把两条路的完整实现都写出来。

3. C++ 代码实现：两个版本都能跑，但细节差很多

3.1 先把输入变成 token 列表

动手写求值函数之前，我建议先做一层 tokenizer。直接盯着单个字符解析会遇到一个致命问题：-1 到底是数字“负一”还是运算符“减号”加数字“1”？如果输入里用空格分隔所有 token，这个问题就消失了。

我定的输入规范是：整个表达式是一个字符串，每个 token（运算符、数字）之间用空格、制表符或换行分隔。数字可以有符号、小数点，例如 -5、3.14 都合法。运算符只包括 + - * / 四个。这种情况下，- 5 2 是 5 减 2，-5 2 从词法上会被识别成两个数字 token，但如果出现在运算符位置就会在后面的语法检查阶段报错。这样设计简单且不容易产生歧义。

下面是分词和基础错误转换的代码：

cpp复制#include <iostream>
#include <string>
#include <vector>
#include <cctype>
#include <stdexcept>

using std::string;
using std::vector;

class PolishEvaluator {
public:
    explicit PolishEvaluator(string expr) : expr_(std::move(expr)) {}

    // 递归求值入口
    double evaluateRecursive() {
        pos_ = 0;
        double result = parseRecursive();
        skipSpaces();
        if (pos_ != expr_.size())
            throw std::runtime_error("extra tokens after the expression");
        return result;
    }

    // 栈求值入口
    double evaluateStack() {
        vector<string> tokens = tokenize();
        if (tokens.empty())
            throw std::runtime_error("empty expression");

        vector<double> stk;
        // 从右往左扫描
        for (auto it = tokens.rbegin(); it != tokens.rend(); ++it) {
            const string& tok = *it;
            if (isOperator(tok)) {
                if (stk.size() < 2)
                    throw std::runtime_error("not enough operands");
                // 先弹出的作为左操作数
                double left = stk.back();
                stk.pop_back();
                double right = stk.back();
                stk.pop_back();
                stk.push_back(applyOp(tok, left, right));
            } else {
                stk.push_back(parseNumber(tok));
            }
        }
        if (stk.size() != 1)
            throw std::runtime_error("too many operands");
        return stk.front();
    }

private:
    string expr_;
    size_t pos_ = 0;

    void skipSpaces() {
        while (pos_ < expr_.size() &&
               std::isspace(static_cast<unsigned char>(expr_[pos_])))
            ++pos_;
    }

    string nextToken() {
        skipSpaces();
        if (pos_ >= expr_.size())
            throw std::runtime_error("unexpected end of expression");
        size_t start = pos_;
        while (pos_ < expr_.size() &&
               !std::isspace(static_cast<unsigned char>(expr_[pos_])))
            ++pos_;
        return expr_.substr(start, pos_ - start);
    }

    vector<string> tokenize() {
        vector<string> tokens;
        while (true) {
            skipSpaces();
            if (pos_ >= expr_.size())
                break;
            size_t start = pos_;
            while (pos_ < expr_.size() &&
                   !std::isspace(static_cast<unsigned char>(expr_[pos_])))
                ++pos_;
            tokens.push_back(expr_.substr(start, pos_ - start));
        }
        return tokens;
    }

    static bool isOperator(const string& tok) {
        return tok == "+" || tok == "-" || tok == "*" || tok == "/";
    }

    static double parseNumber(const string& tok) {
        try {
            size_t used = 0;
            double val = std::stod(tok, &used);
            if (used != tok.size())
                throw std::runtime_error("invalid number token: " + tok);
            return val;
        } catch (const std::exception& e) {
            throw std::runtime_error("invalid token: " + tok);
        }
    }

    static double applyOp(const string& op, double left, double right) {
        if (op == "+") return left + right;
        if (op == "-") return left - right;
        if (op == "*") return left * right;
        // 除法统一用 double，避免整数截断
        if (right == 0.0)
            throw std::runtime_error("division by zero");
        return left / right;
    }

    double parseRecursive() {
        string tok = nextToken();
        if (isOperator(tok)) {
            double left = parseRecursive();
            double right = parseRecursive();
            return applyOp(tok, left, right);
        }
        return parseNumber(tok);
    }
};

3.2 递归版本代码的心理模型

我在写 parseRecursive 时，脑子里始终有一张表达式树的图。比如 * + 1 2 - 3 4，第一个 token 是 *，它一定是根节点，后面的 + 1 2 是左子树，- 3 4 是右子树。递归函数遇到 * 会连续调用两次自身，第一次读完左子树，第二次读完右子树，返回后相乘。这个顺序完全由 token 流驱动，不需要额外状态。

但这里有个很容易踩的坑：当解析一个数字 token 时，直接返回，但外层递归并不知道这个数字具体占了几个 token。这正是把 tokenize 和递归解析结合的必要性。如果逐字符解析，你得自己维护一个“当前 token 读取到哪”的位置指针，还容易在处理负号时翻车。我上面代码用 nextToken() 一次取一个完整 token，pos_ 只往前移动，递归栈自动记录分支点，逻辑就清爽很多。

3.3 栈版本为什么不容易晕

栈版本代码虽短，但左右操作数的顺序特别容易写错。我从右往左遍历 token，遇到运算符时，栈顶元素肯定是最右侧的操作数子树算出的结果。为了验证，我用一个简单用例：

表达式 - 5 2，从右往左顺序是 2、5、-。扫描时 2 入栈，5 入栈，遇到 - 时栈顶是 5，下面一个是 2。我们想要的是 5 - 2 = 3，所以第一个弹出的 5 是左操作数，第二个弹出的 2 是右操作数。这就是我在代码里注释 left = stk.back() 的原因。

如果换成正统的前缀表达式 + * 2 3 4，过程是：4、3、2 依次入栈，遇到 *，弹出 2 和 3，计算 6 入栈；遇到 +，弹出 6 和 4，计算 10。你可以自己写个中缀式子验证：2 * 3 + 4 = 10。这个方向感建立之后，栈版本基本不会错。

4. 边界情况、错误处理与测试用例

4.1 五类必须处理的坑

第一，空表达式。不管是直接空格字符串还是空字符串，都不能默默返回一个 0，那样会让 bug 潜伏在非常隐蔽的位置。tokenize 返回空向量时，我在栈版本入口立刻抛异常。

第二，除数为零。我记得第一次写时偷懒直接做了 left / right，测试一跑，输入 / 5 0 输出 inf。C++ 浮点除法本身不报错，但这个结果传染到整个表达式之后很难查。所以 applyOp 里必须显式检查 right == 0.0，抛 division by zero。

第三，非法字符。输入 3 # 4 时，分词后 # 既不是运算符，也转不成 double，必须在 parseNumber 里捕获异常并重新抛出带有 token 信息的错误。否则 std::stod 默认会抛 std::invalid_argument，错误信息是英文的 "stod"，排查时根本定位不到。

第四，操作数个数不对。递归版本遇到 + 1 会在第二次递归时发现 token 不够，抛 unexpected end。栈版本会在从右往左扫描到运算符但栈元素不足时抛 not enough operands。还有一种情况是表达式结束后栈里剩了多个数字，比如 1 2 3，说明多余操作数，也要抛 too many operands。

第五，极深的嵌套。递归版本遇到几千层嵌套可能爆栈。如果你要做的系统无法保证输入深度，建议直接用栈版本。我在本地测试过大概几万层的嵌套，递归版本已经堆栈溢出，栈版本还能正常返回。

4.2 测试用例表

拿到一份实现，没有测试用例心里不踏实。我整理了一张测试表，覆盖了正常表达式、负号、小数、除零、非法输入等场景：

其中 + 1 -2 这个例子我特别提一下。输入中有空格分隔，所以 -2 被识别成一个负数 token，而不是减号，结果等于 1 + (-2) = -1。如果去掉空格写成 + 1 -2，由于我们按空白分词，仍然安全；但要是写成 +1-2 就会被拆成三个 token +1、-2，按我们的规则会报错或产生不同结果。这也是为什么我反复强调 token 之间要有空白。

4.3 快速验证的 main 函数

光有表格不够，还得跑起来。下面这个 main 里列出几个典型用例，输出结果并做简单断言。你可以直接放到项目里跑，看到 all tests passed 就说明核心逻辑没问题。

cpp复制void expectExpression(const string& expr, double expected) {
    PolishEvaluator ev(expr);
    double got = ev.evaluateStack();
    if (std::abs(got - expected) > 1e-9)
        std::cerr << "FAIL: " << expr << " got " << got
                  << " expected " << expected << "\n";
    else
        std::cout << "PASS: " << expr << " = " << got << "\n";
}

void expectThrow(const string& expr) {
    try {
        PolishEvaluator ev(expr);
        ev.evaluateStack();
        std::cerr << "FAIL: " << expr << " should throw\n";
    } catch (const std::exception&) {
        std::cout << "PASS: " << expr << " throws as expected\n";
    }
}

int main() {
    expectExpression("3", 3);
    expectExpression("+ 1 2", 3);
    expectExpression("- 5 2", 3);
    expectExpression("* + 1 2 - 3 4", -3);
    expectExpression("/ 10 4", 2.5);
    expectExpression("+ 1 -2", -1);
    expectThrow("");
    expectThrow("/ 5 0");
    expectThrow("+ 1");
    expectThrow("@ 1 2");
    std::cout << "all tests done\n";
    return 0;
}

这段代码需要包含 <cmath>。测试通过后，还能顺手比较一下 evaluateRecursive 和 evaluateStack 的结果是否一致，我建议你在业务里两个都跑一遍做交叉验证，防止修改代码时引入不对称 bug。

4.4 我踩过的两个小坑

第一个坑是递归版本开始时没有检查“多余 token”。比如输入 + 1 2 3，递归版本能正确计算 1+2=3，但后面还挂着一个 3。很多递归求值器会直接忽略它，导致表达式不完整也没人管。我只在入口处加了一个位置检查，确保解析完第一个表达式后所有字符都被消费完，否则抛错。这个简单检查至少能拦住 80% 的畸形输入。

第二个坑在 std::stod 的容错上。std::stod("1abc") 会返回 1，used 为 1，并不会报错。如果我不检查 used == token.size()，那 1abc 会被静默当作 1，后面 abc 又会被当成多余 token 报错，错误提示根本看不出是数字格式问题。把 used 检查加上，错误就能精确到具体 token。

5. 延伸：改三行代码就能变成逆波兰求值

5.1 后缀表达式的核心修改

波兰表达式（前缀）学会了，逆波兰（后缀）其实就是同一件事换个方向。后缀表达式的每个运算符都在它的两个操作数之后，所以表达式 1 2 + 3 * 等价于中缀 (1+2)*3。求值方法是从左往右扫描 token，遇到数字入栈，遇到运算符弹出两个数计算。

在栈代码里，修改点主要有两个：遍历方向从 rbegin() 改成 begin()；弹出操作数时，第一个弹出的其实是右操作数，第二个才是左操作数。因为后缀表达式 1 2 - 表示 1 - 2，从左往右读到减号时，栈里从顶到底依次是 2、1，所以 right = stk.back()，然后 left = stk.back()。理解了这两个交换，你就能在前缀和后缀之间自由切换。

cpp复制double evaluatePostfix(const vector<string>& tokens) {
    vector<double> stk;
    for (const string& tok : tokens) {
        if (isOperator(tok)) {
            double right = stk.back(); stk.pop_back();
            double left = stk.back();  stk.pop_back();
            stk.push_back(applyOp(tok, left, right));
        } else {
            stk.push_back(parseNumber(tok));
        }
    }
    return stk.front();
}

5.2 为什么说它们是一对镜像

前缀和后缀在扫描顺序和操作数顺序上刚好对称：前缀从右往左扫，后缀从左往右扫；前缀先弹左操作数，后缀先弹右操作数。如果你把前缀 token 列表反转，再调用后缀求值，同时把运算符的左右对调，就能得到原始结果。这也是为什么很多编译器内部做表达式转换时会用到栈和方向反转。

千万别小看这个小扩展。从这几十行代码里，你能提炼出一套通用的栈式求值框架：无论表达式是前缀、后缀还是中缀转后缀，核心都是“遇数压栈，遇符弹出计算再压回”。搞懂这一个模式，以后再接触 RPN 计算器、函数式语言的递归求值，思路都会顺利很多。我个人在实际开发里，通常会把这两个版本都保留，一个用于教学调试，一个用于深度恶劣的线上输入，互为主备，测试时交叉校验，心里特别踏实。