C++ 如何使用栈求解中缀、后缀表达式的值

前言

人类习惯写中缀表达式：3 + 5 * (2 - 8) / 4，运算符夹在两个操作数中间，还带括号。计算机更适合后缀表达式（逆波兰式，reverse Polish notation）：3 5 2 8 - * 4 / +，运算符跟在操作数后面，没有括号，也没有优先级——从左到右扫一遍就能算完，而"扫一遍"最自然的数据结构就是栈。

常见的误解是"求中缀表达式的值必须用两个栈"。其实有两种等价路线：一是先把中缀转成后缀，再对后缀求值（两个阶段，各用一个栈）；二是用两个栈（操作数栈 + 运算符栈）一边扫描一边求值。前者结构清晰、便于调试，后者少一次遍历，本质是同一套调度规则。

本文采用"先转后缀、再求值"的两步法：先讲后缀为什么适合栈，再讲中缀转后缀的调度场算法（shunting-yard），最后求值。代码以 C++17 为基准，支持+ - * /、括号与非负整数，并显式处理括号不匹配、除零、操作数不足这些错误。

一、后缀表达式与栈

后缀表达式的求值规则只有两条：

1. 
   
2. 遇到操作数，压栈；
3. 
   
4. 遇到运算符，弹出两个操作数，运算后把结果压回。
5. 
   

以3 5 2 8 - * 4 / +为例，按标准语义推演：

最后栈里只剩一个元素，就是结果。这里有两个关键点：先弹出的是右操作数，后弹出的是左操作数；以及整数除法向零截断，-30 / 4得到-7而不是-8（C++11 起明确规定向零截断）。

后缀表达式不需要括号，是因为运算符的位置已经隐含了结合顺序；也不需要优先级表，因为求值时运算符的先后由它在序列中的位置决定。

二、中缀转后缀：调度场算法

转换需要遵循运算符的优先级与结合性。用一个运算符栈保存"还没轮到输出"的运算符，规则如下：

1. 
   
2. 读到数字，直接输出；
3. 
   
4. 读到(，压栈；
5. 
   
6. 读到)，不断弹出并输出，直到遇到(，然后把(弹出丢弃；若栈空则括号不匹配；
7. 
   
8. 读到运算符op，不断弹出优先级不低于op的栈顶运算符并输出，然后把op压栈；
9. 
   
10. 扫描结束后，把栈中剩余运算符依次弹出输出；若遇到(，说明括号不匹配。
11. 
    

第 4 步的"不低于"（>=）对应左结合：同级运算符先出现的先输出，例如a - b - c会转成a b - c -。如果写成>，同级运算符会留在栈里，结合性就变成右结合，a - b - c会算成a - (b - c)，结果不同。

// 适用于 C++17
#include <cctype>
#include <stdexcept>
#include <string>
#include <vector>

bool is_number(const std::string& t) {
return !t.empty() &&
std::isdigit(static_cast<unsigned char>(t[0])) != 0;
}

bool is_operator(const std::string& t) {
return t.size() == 1 && std::string("+-*/").find(t[0]) != std::string::npos;
}

int precedence(const std::string& op) {
if (op == "+" || op == "-") return 1;
if (op == "*" || op == "/") return 2;
return 0; // '(' 不参与比较
}

分词把输入切成数字串与单字符运算符。多位数必须整体读入，不能一个字符一个字符地压栈：

// 适用于 C++17
std::vector<std::string> tokenize(const std::string& s) {
std::vector<std::string> out;
std::size_t i = 0;
while (i < s.size()) {
unsigned char c = static_cast<unsigned char>(s[i]);
if (std::isspace(c)) {
++i;
} else if (std::isdigit(c)) {
std::size_t j = i;
while (j < s.size() &&
std::isdigit(static_cast<unsigned char>(s[j]))) {
++j;
}
out.push_back(s.substr(i, j - i));
i = j;
} else if (std::string("+-*/()").find(s[i]) != std::string::npos) {
out.push_back(std::string(1, s[i]));
++i;
} else {
throw std::invalid_argument("unexpected character");
}
}
return out;
}

std::vector<std::string> to_postfix(const std::vector<std::string>& tokens) {
std::vector<std::string> output;
std::vector<std::string> ops;

for (const std::string& t : tokens) {
if (is_number(t)) {
output.push_back(t);
} else if (t == "(") {
ops.push_back(t);
} else if (t == ")") {
while (!ops.empty() && ops.back() != "(") {
output.push_back(ops.back());
ops.pop_back();
}
if (ops.empty()) throw std::invalid_argument("unmatched ')'");
ops.pop_back(); // 丢掉 '('
} else if (is_operator(t)) {
while (!ops.empty() && ops.back() != "(" &&
precedence(ops.back()) >= precedence(t)) {
output.push_back(ops.back());
ops.pop_back();
}
ops.push_back(t);
} else {
throw std::invalid_argument("unknown token");
}
}

while (!ops.empty()) {
if (ops.back() == "(") throw std::invalid_argument("unmatched '('");
output.push_back(ops.back());
ops.pop_back();
}
return output;
}

三、对后缀表达式求值

求值阶段只需要一个操作数栈。每次遇到运算符，先检查栈里至少有两个元素，再按"先右后左"的顺序弹出：

// 适用于 C++17
long long eval_postfix(const std::vector<std::string>& post) {
std::vector<long long> st;

for (const std::string& t : post) {
if (is_number(t)) {
st.push_back(std::stoll(t));
continue;
}
if (!is_operator(t)) throw std::invalid_argument("unknown token");
if (st.size() < 2) throw std::invalid_argument("missing operand");

long long rhs = st.back();
st.pop_back();
long long lhs = st.back();
st.pop_back();

long long r = 0;
if (t == "+") {
r = lhs + rhs;
} else if (t == "-") {
r = lhs - rhs;
} else if (t == "*") {
r = lhs * rhs;
} else {
if (rhs == 0) throw std::domain_error("division by zero");
r = lhs / rhs;
}
st.push_back(r);
}

if (st.size() != 1) throw std::invalid_argument("malformed expression");
return st.back();
}

std::stoll在字符串不是合法整数时会抛std::invalid_argument，超出范围会抛std::out_of_range，正好覆盖了分词阶段可能漏掉的异常输入。用long long而不是int，是为了让中间结果有更大的余量；但乘法仍然可能溢出，而有符号整数溢出是未定义行为，生产代码应在乘法前做范围检查。

四、完整流程

// 适用于 C++17
#include <iostream>

int main() {
try {
auto tokens = tokenize("3 + 5 * (2 - 8) / 4");
auto post = to_postfix(tokens);
long long v = eval_postfix(post);
std::cout << v << '\n'; // 按标准语义应当是 -4
} catch (const std::exception& e) {
std::cerr << "error: " << e.what() << '\n';
return 1;
}
}

按标准语义推演：5 * (2 - 8)得 -30，-30 / 4向零截断得 -7，3 + (-7)得 -4。

如果改用"双栈一遍扫描"，只需要把to_postfix的输出动作改成"立即计算"：遇到运算符时先按优先级弹出运算符栈顶并计算，把结果压回操作数栈。两条路线的核心规则完全相同，只是把"输出序列"换成了"当场求值"。

常见坑点

1. 弹栈顺序写反

// ❌ 先弹的当左操作数，减法和除法结果错误
long long a = st.back(); st.pop_back();
long long b = st.back(); st.pop_back();
long long r = a - b;
// ✅ 先弹的是右操作数
long long rhs = st.back(); st.pop_back();
long long lhs = st.back(); st.pop_back();
long long r = lhs - rhs;

2. 多位数被拆成单个字符

// ❌ "42" 变成 '4' 和 '2' 两个操作数
for (char c : s) if (isdigit(c)) out.push_back(std::string(1, c));
// ✅ 连续数字整体读入
while (j < s.size() && isdigit(s[j])) ++j;
out.push_back(s.substr(i, j - i));

3. 括号不匹配没有检查

// ❌ 栈空时继续弹，或残留 '(' 被当成运算符
while (ops.back() != "(") { ... }
// ✅ 每步判空，结束时检查残留
if (ops.empty()) throw std::invalid_argument("unmatched ')'");

4. 同级运算符用了>而不是>=

// ❌ a - b - c 被转成 a b c - -，变成右结合
while (precedence(ops.back()) > precedence(t))
// ✅ 左结合要求弹出同级
while (precedence(ops.back()) >= precedence(t))

5. 除零没有处理

// ❌ 整数除零是未定义行为
r = lhs / rhs;
// ✅ 先检查
if (rhs == 0) throw std::domain_error("division by zero");

6. 结束后不检查栈里是否只剩一个值

// ❌ 表达式非法时返回了中间值
return st.back();
// ✅ 校验元素个数
if (st.size() != 1) throw std::invalid_argument("malformed expression");

7. 一元负号当成二元减号

// ❌ "-3 + 5" 里 '-' 前没有左操作数，弹栈失败
// ✅ 明确支持范围，或在分词阶段识别一元运算符并补 0

8. 用int保存中间结果

// ❌ 乘法中间结果轻易溢出，且溢出是未定义行为
int r = lhs * rhs;
// ✅ 用更宽的类型，并在乘法前做范围检查
long long r = lhs * rhs;

总结

栈在这里的作用不是"存储数据"，而是延迟决策：中缀转后缀时，运算符栈把"还没轮到输出"的运算符暂存起来；后缀求值时，操作数栈把"还没轮到参与运算"的值暂存起来。把这两个"暂存"的时机想清楚，表达式求值就没有神秘之处了。