1. 引言
四则运算表达式是我们从小学就开始接触的数学工具，比如3+(4*5-2)/2。对人来说，一眼就能看出先算括号里的4*5，再算20-2，然后除以2，最后加上3。但计算机面对同样的表达式却一头雾水——它不知道运算符的优先级，也不理解括号的嵌套关系。
《大话数据结构》第 4.9 节用栈这一数据结构优雅地解决了四则运算问题。核心思路分两步：先把中缀表达式转成后缀表达式（逆波兰表示法），再对后缀表达式求值。这篇博客给出完整、可处理多位数和括号的 C++ 实现，并对算法细节做了深入剖析。
2. 核心概念：三种表达式
在正式写代码之前，先理清三种表达式的区别：
| 表达式类型 | 示例 | 特点 |
|---|---|---|
| 中缀表达式 | 3 + 4 * 5 | 运算符在两个操作数中间，符合人类习惯，但有优先级和括号问题 |
| 前缀表达式（波兰式） | + 3 * 4 5 | 运算符在操作数前面，无需括号即可表达优先级 |
| 后缀表达式（逆波兰式） | 3 4 5 * + | 运算符在操作数后面，计算机求值最方便，无需括号 |
后缀表达式之所以适合计算机处理，是因为它天然消除了优先级和括号：遇到数字就压栈，遇到运算符就弹出两个操作数计算，结果再压回去。整个过程不需要前瞻或回溯。我们要做的，就是把中缀表达式转换成这种结构。
3. 中缀转后缀算法详解
3.1 算法核心思想
中缀转后缀的核心是用栈管理运算符。遍历中缀表达式的每个字符，按以下规则处理：
- 遇到数字：直接输出到后缀表达式（注意处理多位数）。
- 遇到左括号
(：直接压入运算符栈。 - 遇到右括号
)：不断弹出栈顶运算符并输出，直到遇到左括号为止，最后把左括号弹出丢弃。 - 遇到运算符：和栈顶运算符比较优先级。如果栈顶运算符优先级大于等于当前运算符，就弹出栈顶并输出，直到栈为空或栈顶优先级更低，然后把当前运算符压栈。
- 遍历结束后：把栈中剩余的运算符全部弹出输出。
下面用一个实例走一遍：中缀表达式3+(4*5-2)/2的转换过程。
| 步骤 | 当前字符 | 运算符栈 | 后缀输出 | 说明 |
|---|---|---|---|---|
| 1 | 3 | 空 | 3 | 数字直接输出 |
| 2 | + | + | 3 | 栈空，+直接压栈 |
| 3 | ( | + ( | 3 | 左括号直接压栈 |
| 4 | 4 | + ( | 3 4 | 数字直接输出 |
| 5 | * | + ( * | 3 4 | 栈顶是(，*直接压栈 |
| 6 | 5 | + ( * | 3 4 5 | 数字直接输出 |
| 7 | - | + ( - | 3 4 5 * | -优先级低于*，弹出*后压入- |
| 8 | 2 | + ( - | 3 4 5 * 2 | 数字直接输出 |
| 9 | ) | + | 3 4 5 * 2 - | 弹出-，再弹出(丢弃 |
| 10 | / | + / | 3 4 5 * 2 - | /优先级高于+，直接压栈 |
| 11 | 2 | + / | 3 4 5 * 2 - 2 | 数字直接输出 |
| 12 | 结束 | 空 | 3 4 5 * 2 - 2 / + | 弹出剩余运算符/和+ |
最终后缀表达式为3 4 5 * 2 - 2 / +，这正是我们期望的结果。
3.2 优先级函数
优先级判断是整个算法的基石。乘除的优先级高于加减，括号本身不参与优先级比较：
int priority(char op) { if (op == '+' || op == '-') return 1; if (op == '*' || op == '/') return 2; return 0; // 括号返回 0，保证不会错误弹出 }这里把(的优先级设为 0 是关键设计：当栈顶是左括号时，任何运算符都不会因为优先级比较而被错误弹出，因为左括号的优先级最低。
3.3 完整转换代码
string infixToPostfix(const string& infix) { stack<char> opStack; string postfix; for (size_t i = 0; i < infix.size(); ++i) { char c = infix[i]; if (isdigit(c)) { // 处理多位数：连续读取直到非数字 while (i < infix.size() && isdigit(infix[i])) { postfix += infix[i++]; } postfix += ' '; // 用空格分隔操作数 --i; // 回退，外层 for 会 ++i } else if (c == '(') { opStack.push(c); } else if (c == ')') { // 弹出直到遇到左括号 while (!opStack.empty() && opStack.top() != '(') { postfix += opStack.top(); postfix += ' '; opStack.pop(); } opStack.pop(); // 弹出 '(' 并丢弃 } else if (c == '+' || c == '-' || c == '*' || c == '/') { // 栈顶优先级大于等于当前运算符时弹出 while (!opStack.empty() && priority(opStack.top()) >= priority(c)) { postfix += opStack.top(); postfix += ' '; opStack.pop(); } opStack.push(c); } } // 弹出栈中剩余运算符 while (!opStack.empty()) { postfix += opStack.top(); postfix += ' '; opStack.pop(); } return postfix; }这段代码有两个容易忽略的细节：
- 多位数处理：内层
while循环连续读取数字字符，保证像12、345这样的多位数被完整输出为一个操作数。 - 空格分隔：每个操作数和运算符后面都追加一个空格，这是为了让后缀表达式求值阶段能够用
stringstream按空格切分 token。
4. 后缀表达式求值
4.1 算法思想
拿到后缀表达式后，求值反而简单了——只需要一个操作数栈。遍历后缀表达式中的每个 token：
- 如果是数字，压入操作数栈。
- 如果是运算符，从栈中弹出两个操作数（先弹出的是右操作数
b，后弹出的是左操作数a），计算a op b，把结果压回栈中。
遍历结束后，栈中剩下的唯一元素就是最终结果。
以3 4 5 * 2 - 2 / +为例：
| 步骤 | 当前 token | 操作数栈 | 操作 |
|---|---|---|---|
| 1 | 3 | [3] | 数字入栈 |
| 2 | 4 | [3, 4] | 数字入栈 |
| 3 | 5 | [3, 4, 5] | 数字入栈 |
| 4 | * | [3, 20] | 弹出 5 和 4，计算 4*5=20，压回 |
| 5 | 2 | [3, 20, 2] | 数字入栈 |
| 6 | - | [3, 18] | 弹出 2 和 20，计算 20-2=18，压回 |
| 7 | 2 | [3, 18, 2] | 数字入栈 |
| 8 | / | [3, 9] | 弹出 2 和 18，计算 18/2=9，压回 |
| 9 | + | [12] | 弹出 9 和 3，计算 3+9=12，压回 |
最终栈中只剩12，与预期一致。
4.2 完整求值代码
double evaluatePostfix(const string& postfix) { stack<double> numStack; stringstream ss(postfix); string token; while (ss >> token) { // 判断是否为数字（支持负数如 "-3"） if (isdigit(token[0]) || (token.size() > 1 && token[0] == '-')) { numStack.push(stod(token)); } else { double b = numStack.top(); numStack.pop(); double a = numStack.top(); numStack.pop(); switch (token[0]) { case '+': numStack.push(a + b); break; case '-': numStack.push(a - b); break; case '*': numStack.push(a * b); break; case '/': numStack.push(a / b); break; } } } return numStack.top(); }注意这里用stod(token)将字符串转为double，这样即使表达式中有小数也能正确处理。另外数字判断中加了token.size() > 1 && token[0] == '-'，是为了识别像-3这样的负数 token。
5. 完整可运行代码
把上述两部分拼在一起，加上必要的头文件和测试用例，得到一份完整的可运行程序：
#include <iostream> #include <stack> #include <string> #include <sstream> #include <cctype> using namespace std; int priority(char op) { if (op == '+' || op == '-') return 1; if (op == '*' || op == '/') return 2; return 0; } string infixToPostfix(const string& infix) { stack<char> opStack; string postfix; for (size_t i = 0; i < infix.size(); ++i) { char c = infix[i]; if (isdigit(c)) { while (i < infix.size() && isdigit(infix[i])) { postfix += infix[i++]; } postfix += ' '; --i; } else if (c == '(') { opStack.push(c); } else if (c == ')') { while (!opStack.empty() && opStack.top() != '(') { postfix += opStack.top(); postfix += ' '; opStack.pop(); } opStack.pop(); } else if (c == '+' || c == '-' || c == '*' || c == '/') { while (!opStack.empty() && priority(opStack.top()) >= priority(c)) { postfix += opStack.top(); postfix += ' '; opStack.pop(); } opStack.push(c); } } while (!opStack.empty()) { postfix += opStack.top(); postfix += ' '; opStack.pop(); } return postfix; } double evaluatePostfix(const string& postfix) { stack<double> numStack; stringstream ss(postfix); string token; while (ss >> token) { if (isdigit(token[0]) || (token.size() > 1 && token[0] == '-')) { numStack.push(stod(token)); } else { double b = numStack.top(); numStack.pop(); double a = numStack.top(); numStack.pop(); switch (token[0]) { case '+': numStack.push(a + b); break; case '-': numStack.push(a - b); break; case '*': numStack.push(a * b); break; case '/': numStack.push(a / b); break; } } } return numStack.top(); } int main() { // 测试用例 1 string infix1 = "3+(4*5-2)/2"; string postfix1 = infixToPostfix(infix1); cout << "中缀: " << infix1 << endl; cout << "后缀: " << postfix1 << endl; cout << "结果: " << evaluatePostfix(postfix1) << endl; // 12 cout << "---" << endl; // 测试用例 2：多位数 string infix2 = "12+34*5"; string postfix2 = infixToPostfix(infix2); cout << "中缀: " << infix2 << endl; cout << "后缀: " << postfix2 << endl; cout << "结果: " << evaluatePostfix(postfix2) << endl; // 182 cout << "---" << endl; // 测试用例 3：嵌套括号 string infix3 = "((2+3)*4-(5-2))/3"; string postfix3 = infixToPostfix(infix3); cout << "中缀: " << infix3 << endl; cout << "后缀: " << postfix3 << endl; cout << "结果: " << evaluatePostfix(postfix3) << endl; // 5.66667 return 0; }6. 运行结果与分析
编译运行上述代码，输出如下：
中缀: 3+(4*5-2)/2 后缀: 3 4 5 * 2 - 2 / + 结果: 12 --- 中缀: 12+34*5 后缀: 12 34 5 * + 结果: 182 --- 中缀: ((2+3)*4-(5-2))/3 后缀: 2 3 + 4 * 5 2 - - 3 / 结果: 5.66667三个测试用例覆盖了基础四则运算与括号嵌套、多位数处理、多层嵌套括号三种典型场景，全部输出正确结果。
7. 拓展思考
这套代码已经能正确处理多位数、括号和四则运算优先级。如果想让实现更健壮，以下几个方向值得进一步探索：
- 支持小数：当前代码只处理整数数字，可以在
isdigit判断中加入对小数点.的处理。 - 支持负数：中缀表达式中的一元负号（如
-3+5或3*(-2)）需要特殊处理，因为同一个-符号可能是二元减法也可能是一元取负。 - 支持更多运算符：比如幂运算
^（右结合）或取模%，需要调整优先级函数和结合性规则。 - 错误处理：对非法输入（如不匹配的括号、连续运算符等）给出友好提示。
- 用模板/泛型改写：让求值函数支持
int、long long、double等多种数值类型。
8. 总结
中缀转后缀加后缀求值，是栈的经典应用场景，也是《大话数据结构》第 4 章的高光内容。整个方案的核心就两句话：
- 转后缀靠运算符栈——用优先级比较决定运算符的输出时机，括号用来界定子表达式的边界。
- 求值靠操作数栈——见到数字就压，见到运算符就弹两个算一个再压回去。
理解了这个双栈协作的模式，再去理解编译原理中的表达式解析、甚至是逆波兰计算器的实现，都会轻松很多。建议读者把代码复制到本地跑一遍，然后试着改几个表达式观察后缀输出，手感会更好。
