后缀表达式求值：栈原理、中缀转逆波兰表达式完整解析

第一次在洛谷刷到P1449 后缀表达式时我盯着这个名词愣了好一会儿。平时写惯了3*(5-2)7这种中缀式子突然冒出一个把运算符全丢在后面的3.5.2.-*7.第一反应是这玩意儿真的是给人读的吗不过也正是这道题让当时刚学栈的我彻底想明白了一件事——不是计算机理解不了中缀表达式而是栈这个数据结构本身就为后缀表达式而生。这篇文章把我自己啃 P1449 时踩过的坑、补上的原理以及顺带学会的“中缀转后缀”方法完整整理出来。适合刚开始学数据结构、刷算法题入门、或者准备复试机试和面试时被“逆波兰表达式求值”问住的同学。我会把每一步为什么这么做讲透而不是只甩一个能过的代码。1. P1449 到底在考什么从读不懂题到看懂那串怪符号1.1 题面在说什么P1449 的题面很短大意是后缀表达式里不再有括号运算符号放在两个运算对象后面所有计算按运算符出现的顺序严格从左往右推进不用考虑优先级。输入以结束是表达式的结束符号.是操作数的结束符号。举个例子中缀表达式3*(5-2)7对应的后缀表达式就是3.5.2.-*7.我第一次看到这个字符串时完全懵了后来才明白3.表示数字 3 结束5.表示数字 5 结束2.表示数字 2 结束-让 5 和 2 相减*让前面的结果和 3 相乘7.压入 7做加法表示结束。整个过程完全不需要括号也不需要判断谁先算谁后算所有运算顺序都已经被“拍平”在表达式里了。所以这道题考察的东西非常纯粹字符串处理和栈的模拟。难度不高但它是一个非常典型的模型后面我们做计算器、看编译原理里表达式求值都会遇到同一套东西。1.2 为什么计算机更喜欢后缀表达式我们人眼计算3*(5-2)7时会条件反射地先算括号里的减法再算乘法最后算加法。但计算机没有这种“条件反射”它只能按顺序执行指令。如果直接扫描中缀表达式它必须处理两个麻烦运算符优先级和括号匹配。这就意味着需要有额外逻辑来决定“当前这个运算符到底能不能执行”。后缀表达式把这个麻烦转移到了转换阶段。只要表达式已经转成后缀求值阶段就变成了一条极其机械的规则遇到数字就压栈遇到运算符就弹出两个数计算再压回。整一遍扫描线性时间不需要回头看任何字符。这也是为什么早期计算器、JVM 的栈式架构、以及很多编译器的中间表示都愿意用逆波兰风格的原因——求值逻辑简单到不可能出错。如果你刚学到这里不用急着理解 JVM 那么远只需要记住你正在写的东西本质上是在模拟一个“无括号、无优先级”的计算机执行模型。2. 栈求值的完整拆解手把手推演3.5.2.-*7.2.1 核心规则只有两条整个求值过程可以压缩成两句话读到操作数压入栈顶。读到运算符从栈顶弹出两个数先弹出的是右操作数后弹出的是左操作数计算完把结果压回栈顶。为什么是“先弹出右操作数”这要从压栈顺序说起。后缀表达式里一个运算符前面紧挨着的两个数就是它的操作数比如5.2.-中5 先入栈2 后入栈那么栈顶是 2次顶是 5。做减法时应该5 - 2也就是先弹出的作减数后弹出的作被减数。这个顺序是减法、除法最容易翻车的地方。有的教程会把栈写成“从栈顶往下数”我觉得不如直接记一句口诀后缀求值时第一个 pop 的是右边那个第二个 pop 的是左边那个。2.2 完整状态表看每一步我建议你用这张表把整个样例亲手走一遍比看十遍代码都管用读取栈内容栈底 → 栈顶动作说明33读到数字暂存.3数字结束把 3 压栈53, 5暂存 5.3, 5把 5 压栈23, 5, 2暂存 2.3, 5, 2把 2 压栈-3, 3弹出 2右、5左计算 5 - 2 3压回*9弹出 3右、3左计算 3 * 3 9压回79, 7暂存 7.9, 7把 7 压栈16弹出 7右、9左计算 9 7 16压回16结束输出栈顶注意到没有整个过程里栈中元素始终代表“等待参与下一次运算的中间结果”。某个运算符执行后两个操作数合并成一个新数栈的大小减一一个数字入栈栈的大小加一。这就是后缀表达式无歧义性的直接体现——任意时刻栈里到底有几个数是可以精确预期和验证的。2.3 栈的“后到先用”和生活类比为什么这个场景偏偏用栈因为后缀表达式中运算符总是作用于“最近出现的两个操作数”。这个“最近”就是典型的 LIFO后进先出语义。有一个特别贴切的类比食堂里一摞餐盘。新洗好的盘子叠在最上面取用时也是从最上面拿。你要想拿到最底下那个盘子得先把上面的全部挪走。后缀表达式就是规定“洗好后立刻要用最近的两个盘子”因此栈顶永远是你当前最需要的数据。我见过有人尝试用队列来解这道题结果发现完全对不上——队列是先来先用而后缀表达式要求后来先用方向恰好相反。所以别凭感觉选数据结构先搞清楚数据的消费顺序是“最近优先”还是“最早优先”再选容器。3. 这道题真正容易踩的四个坑3.1 数字不止一位.号的设计意图这是 P1449 最常见的卡点。如果输入全是3.5.2.这种个位数那直接ch - 0压栈也能过。但题目并没有说操作数只有一位比如表达式里出现12时输入会是12.而不是1.2.。这就要注意了当你读到一个数字字符时不能立刻压栈得先把它累积起来。正确的处理是遇到数字ch执行num num * 10 (ch - 0)遇到.说明当前这个操作数已经完整把num整体压栈然后num清零。我第一次做的时候没意识到这一点写了个“数字字符直接压栈”的版本输入一长立刻错误。后来才明白.不是摆设它的存在就是为了告诉你多位数的边界在哪里。3.2 读入循环怎么处理和.读入逻辑看起来简单但处理顺序不对也会出错。我的习惯是while (cin ch ch ! ) { ... }先判断当前字符是不是数字是数字就累积再判断是不是.是就把累积的数字压栈如果都不是那就是 - * /四则运算符执行弹栈计算。有个容易忽略的细节循环条件里直接断掉的读取不要在循环体内单独判断if (ch ) break之后还继续做别的事。虽然两种写法最终结果可能一样但前者更清晰后续代码不会误处理结束符。另外如果约定输入是一整行字符串也可以用getline读取后遍历但要注意字符串末尾的换行符和可能的空格。P1449 的数据一般很干净但养成“忽略空白字符”的习惯总没错。3.3 整除、除零与负数除法题目里的/是整除也就是 C 里int / int直接截断小数部分。这在大多数测试数据下没问题但有两个边界值得防御除零P1449 的合法用例大概率不会出现除零但你自己构造测试数据或者把代码拿去扩展使用时一旦b 0整个程序直接 Runtime Error。稳妥做法是在除法分支判断一下除数出错时给个默认结果或者报错。负数除法C 的整数除法是向零取整比如-7 / 2结果是-3而不是数学上的向下取整-4。如果题目明确要求向下取整你得自己写一个 floorDiv。P1449 没考这么细但这是“中缀转后缀 求值”通用场景里一定会遇到的坑。我的个人习惯是栈内统一用long long存储防止中间结果溢出。虽然 P1449 的数据范围用int就能过但养成这种习惯能少很多莫名其妙的 WA。3.4 栈里多出来的数表达式非法的兜底如果输入的后缀表达式是合法的那么求值结束时栈里应该恰好剩下一个数那就是答案。但如果你在调试时发现循环结束后栈里还剩下两个甚至更多的数说明操作数比运算符多表达式有问题反过来如果栈空了说明运算符太多。这里给一个小技巧调试期可以在每步操作后打印栈的 size 和栈顶内容观察是不是符合预期。比如 P1449 这个样例每读一个 token栈大小的变化应该是 1、2、3、2、1、2、1非常有规律。一旦发现栈大小在某些不该减少的时候突然减到 0 甚至访问了空栈那几乎可以肯定是弹栈顺序写反了。4. 中缀转后缀把人类习惯翻译成机器节奏4.1 为什么要先转后缀光会求值还不够因为你日常能拿到的输入大概率还是3*(5-2)7这种中缀写法。与其写一个同时处理优先级和括号的求值器不如先把中缀统一转成后缀然后再用前面那套简单的栈求值。这就是典型的“把复杂问题拆成两个简单问题”。转换算法有个著名的名字调度场算法Shunting-yard Algorithm。核心思想是引入一个运算符栈用来“悬挂”那些暂时还不能执行的运算符。为什么需要悬挂因为当你读到一个运算符时它右侧的操作数还没有出现你只能先把运算符放在一边等条件成熟了再从栈里弹出来。4.2 调度场算法的五条规则假设我们从左到右扫描中缀表达式维护一个输出字符串和一个运算符栈规则如下数字直接输出多位数字先累积遇到非数字再整体输出。(直接压栈。)一直弹栈并输出直到遇到(然后把这个(弹出但不输出。遇到 - * /时只要栈不空、栈顶不是(、且栈顶运算符优先级不低于当前运算符就反复弹栈输出最后把当前运算符压栈。扫描结束后把运算符栈里剩余的所有运算符依次弹出输出。来手动跑一个小例子3*(5-2)7。读3数字输出3。读*栈空压栈。读(直接压栈。读5输出5。读-栈顶是(不弹出任何东西-压栈。读2输出2。读)弹栈输出-再弹出(丢弃。读栈顶*优先级高于弹栈输出*栈空压栈。读7输出7。扫描结束弹栈输出。最终得到3 5 2 - * 7 和 P1449 样例去掉点号后的形式完全一致。4.3 左结合与右结合为什么要用而不是很多实现挂在同一个地方规则 4 里的“不低于当前优先级”也就是。这里有一个非常经典的左结合问题。看表达式8-3-2。我们人知道应该(8-3)-2 3。但如果转换时用而不是遇到第二个-时因为栈顶的-优先级是 1当前-优先级也是 1判断不成立第二个-直接压栈。最终输出是8 3 2 - -求值时变成8 - (3 - 2) 7结果错误。用的逻辑是两个级别相同的运算符左边那个已经出现应该先结算这样才能保持左结合性。这个细节面试很喜欢问原理也不难记——你在中缀里写的连续减号、连续除号天然是从左往右算的转换算法必须保证这一点。4.4 一个完整的转换代码骨架下面给一个我常用的转换函数输出为空格分隔的后缀表达式这样求值时用空格切分很方便string infixToPostfix(const string s) { string res; stackchar ops; long long num 0; bool hasNum false; auto flush []() { if (!hasNum) return; res to_string(num) ; num 0; hasNum false; }; for (char c : s) { if (isdigit(c)) { num num * 10 (c - 0); hasNum true; } else { flush(); if (c () { ops.push(c); } else if (c )) { while (!ops.empty() ops.top() ! () { res ops.top(); res ; ops.pop(); } if (!ops.empty()) ops.pop(); } else if (c || c - || c * || c /) { while (!ops.empty() ops.top() ! ( priority(ops.top()) priority(c)) { res ops.top(); res ; ops.pop(); } ops.push(c); } } } flush(); while (!ops.empty()) { res ops.top(); res ; ops.pop(); } return res; }这里没有处理一元负号比如中缀里的-7 2在标准算法里会有歧义。我的建议是需要支持一元负号时把它改写成0 - 7 2再参与转换这也是很多编译器早期采用的朴素做法。P1449 本身不涉及这个问题但你在 LeetCode 或其他场景遇到时值得知道。5. 完整参考实现P1449 原题、转换器和自测用例5.1 可以直接过 P1449 的提交版#include bits/stdc.h using namespace std; int main() { char ch; long long num 0; vectorlong long st; while (cin ch ch ! ) { if (ch 0 ch 9) { num num * 10 (ch - 0); } else if (ch .) { st.push_back(num); num 0; } else if (ch || ch - || ch * || ch /) { long long b st.back(); st.pop_back(); long long a st.back(); st.pop_back(); long long r; if (ch ) r a b; else if (ch -) r a - b; else if (ch *) r a * b; else r (b 0 ? 0 : a / b); // 防御除零 st.push_back(r); } } cout st.back() \n; return 0; }有人喜欢用std::stack我更喜欢vector模拟栈因为随时可以看st[st.size() - 2]这类次栈顶元素调试起来很方便这个习惯在更复杂的状态栈场景里很有用。5.2 通用求值函数空格分隔版下面这个函数接收infixToPostfix的输出按空格分隔处理long long evalPostfix(const string t) { vectorlong long st; long long num 0; bool hasNum false; for (char c : t) { if (isdigit(c)) { num num * 10 (c - 0); hasNum true; } else if (c ) { if (hasNum) { st.push_back(num); num 0; hasNum false; } } else { if (hasNum) { st.push_back(num); num 0; hasNum false; } long long b st.back(); st.pop_back(); long long a st.back(); st.pop_back(); switch (c) { case : st.push_back(a b); break; case -: st.push_back(a - b); break; case *: st.push_back(a * b); break; case /: st.push_back(b 0 ? 0 : a / b); break; } } } if (hasNum) st.push_back(num); return st.back(); }两个代码拼在一起就是一套完整的“中缀输入 → 转后缀 → 栈求值”工具链。5.3 自测用例和 LeetCode 迁移我建议你把下面几个用例跑一遍覆盖加减乘除、连续运算、括号、多位数等情况中缀表达式转换后的后缀表达式期望结果3*(5-2)73 5 2 - * 7 168-3-28 3 - 2 -3(12)*(34)1 2 3 4 *2110/410 4 /20-720 7 - 2 -5这里最后一条是负数场景的绕法用0 - 7代替一元负号。跑通这些之后你顺手把输入格式从“空格分隔 结束”改成“vector 字符串数组”就是 LeetCode 第 150 题“逆波兰表达式求值”的解法。换句话说P1449 相当于把这道经典面试题换了个输入外壳核心模型完全一致。我个人在实际操作中的体会是遇到“计算器”或“表达式求值”这类题目时先别急着模拟人脑的运算习惯而是问自己“能不能先拍平成 RPN 栈”这样代码量通常会减半正确率还高。P1449 只是一个起点后面还有 LeetCode 150、中缀转后缀、表达式树等等都是同一套思维在不同壳子下的变形。先把这里每一步栈的变化亲手走一遍比背十个题解都管用。