后缀式求值这道题编号 7-425 分在各类数据结构课程的在线判题平台上常年驻扎属于“看起来一句话就能说完、真正写起来到处漏风”的典型。它考的不是你会不会用栈而是你能不能把栈用对——数字怎么识别、两个操作数谁先谁后、除法怎么处理、输入到什么位置停任何一环想歪一点代码在样例上跑得通提交上去就是一排红。我前后在不同语言、不同平台上重写过这道题不下十遍最早那次卡了很久最后发现是减法的两个操作数顺序反了。所以这篇东西不打算停留在“建个栈、遇数就压、遇符就弹”这种一句话版本而是把题目背后每一个可能让你丢分的细节拆开讲从输入形态的判断到多位数解析的边界再到除法语义和溢出最后给出一份能直接抄的完整代码和一份踩坑清单。刚学完栈、正在被这题卡住的同学能直接用已经过了但想补基础的同学也能从里面捞出一些平时不会注意的东西。1. 先把题目吃透后缀式求值到底考什么1.1 从人的阅读习惯说起中缀式子为什么“不好算”我们平时写的(12)*34这种叫中缀表达式运算符夹在两个操作数中间人的阅读习惯是这样但计算机处理起来很别扭它得先判断括号范围再看乘除优先于加减还得处理同级从左到右本质上是要维护一棵隐式的语法树。你写出来的代码会变成两层循环、一个优先级表稍微一复杂就绕。后缀表达式也叫逆波兰表达式把运算符挪到操作数后面(12)*34写成后缀就是1 2 3 * 4 。这个形态丢掉了括号也丢掉了优先级读到哪算到哪从左往右一遍扫完就能出结果中间不需要回退也不需要“记住”什么东西。计算机喜欢这种结构因为它的处理流程是线性的每一步都对已经处理过的部分做一次规约——把“两个数 一个运算符”缩成“一个数”。正是因为这个特性后缀式求值成了栈这个数据结构的入门第一课每一步都能清楚地对应到一次压栈或弹栈讲原理的时候画图特别顺写代码的时候却没有那么多拐弯。反过来说也正因为流程太直白很多人写的时候不过脑子细节全凭直觉然后就翻车了。1.2 栈在这里扮演的角色一个自助餐托盘架我用一个更接地气的类比来解释栈在这道题里干什么。想象食堂门口的自助餐托盘架弹簧托盘架那种你拿走一个托盘上面的托盘会自动顶上来你只能从最上面拿放回去也只能放最上面。这就是“后进先出”。后缀式求值的流程就是围绕这个架子展开的从左到右扫表达式碰到数字就当作一个托盘放上去碰到运算符就从架子上取两个托盘下来用这个运算符把两个数算成一个新托盘再放回去。扫完之后架子上应该只剩一个托盘那个数就是结果。这里有个关键点需要强调取两个托盘的时候先取下来的是右操作数后取下来的是左操作数。这个顺序在加法和乘法里没有影响ab和ba一样但在减法和除法里就是致命错误。很多人写代码的时候顺手写成“先弹出来的减后弹出来的”样例刚好是加法或者刚好是6 3 -这种正序就蒙混过关了一旦遇到3 5 -直接废掉。1.3 输入形态决定实现方案两种常见版本必须先分清楚这一点是最容易被忽略、又最该在动手前确认的。同一个题名下的“后缀式求值”输入格式至少有两大类代码写法完全不同版本类型典型输入操作数识别方式读取方式容易踩的雷紧凑型345*#每个数字字符就是一个操作数整串读入逐字符扫描误把34当一个数空格分隔型3 4 5 * #连续数字串构成一个多位数读整行跳过空格空格没跳过数字断成两半混合型3 45*#需要按样例判断逐字符扫描 空格过滤规则没定义清楚全凭猜这两类写法的核心区别在于“数字的边界在哪里”。紧凑型里34表示两个操作数 3 和 4因为题目保证操作数都是一位数字空格分隔型里34表示一个数三十四。你要是把这两种搞反代码可能连样例都过不去也可能样例过了但隐藏测试点全错。我的建议很实在打开题目先看样例再决定写法不要凭记忆。如果样例里出现10、25这种两位数那必然是空格分隔或者有明确的多位数字规则如果样例是345*#这种紧贴的那就按单字符来。判断清楚以后再动键盘能省掉一半的调试时间。补充一点有些版本会明确写“操作数为 0-9 的一位数”有些版本会写“操作数为不超过若干位的正整数”还有些版本会以#结尾表示输入结束。这些约定都必须逐字读一遍它们直接决定了你的解析循环怎么写。我见过的最冤的情况是题目明明说“以 # 结尾”有人没看到把#当成非法字符跳过结果循环跑飞数组越界。2. 核心细节拆解五个决定成败的处理点2.1 数字识别从“一个字符”到“一个数”的转换数字识别看起来是最简单的一步实际上藏着最多歧义。在紧凑型里你的判断就是“这个字符是不是 0 到 9”是的话直接c - 0转成数值压栈一行代码搞定。但在多位数版本里你要做的是“从当前位置开始不断往后吞数字字符直到遇到非数字”把它拼成一个完整的整数。这个“吞”的过程有个经典写法陷阱long long num 0; while (i s.size() s[i] 0 s[i] 9) { num num * 10 (s[i] - 0); i; }循环结束时i指向的是第一个非数字字符。而外层通常是个for循环会在每轮末尾再执行一次i于是这个非数字字符就被跳过了。如果那个字符正好是运算符你相当于白白丢掉了一个运算符后面的计算全错。正确的做法是在 while 结束后补一句--i;把位置退回到非数字字符上让外层循环去处理它。这个细节我至少见过七八个同学踩过表现症状是“输入12 3 #输出 12 而不是 15”——因为被跳过了栈里剩下两个数最后输出的是栈底那个。看到这种“结果刚好等于某个操作数”的现象第一反应就该怀疑是不是跳字符了。还有一点如果你的题目里允许负数操作数比如-3 5 那-这个字符就有了双重身份既可能是减号也可能是负号。区分办法是看它出现的上下文如果前一个非空格字符是运算符或者开头那它大概率是负号如果前一个 token 是操作数那它就是减号。这个判断逻辑会显著增加代码复杂度而绝大多数在线判题的这类题目并不要求处理负数操作数所以在动手前确认一下不要过度设计。我自己的习惯是先按“操作数非负”写如果样例里真出现了负数再补判定分支。2.2 弹栈顺序减法和除法的唯一正确姿势这一节单独拎出来讲因为它是这道题最高频的失分点。流程是这样的读到运算符时栈顶是右操作数栈顶下面那个是左操作数。所以代码必须是long long b st[--top]; // 先弹出来的是右操作数 long long a st[--top]; // 后弹出来的是左操作数 long long r a - b; // 左 op 右为什么是这个顺序把表达式5 3 -按流程走一遍先压 5再压 3栈从底到顶是[5, 3]。读到减号弹出栈顶 3这是右操作数再弹出 5这是左操作数计算5 - 3 2压回去。结果 2符合预期。如果顺序写反变成3 - 5 -2样例如果是6 4 -就会输出 -2 而不是 2。而如果你运气好样例里只有加法那么正反都是对的代码就能过样例——然后在隐藏测试点上全军覆没。这种行为模式特别坑因为它给你一种“我写对了”的错觉。除法的道理完全一样a / b里a是被除数b是除数顺序反了结果差得离谱。6 3 /正确是 2反了变成 0因为整数除法 3/6 截断成 0。看到结果莫名其妙变成 0先查这个。提示在弹栈之前一定要判一下栈里的元素够不够两个。题目一般保证输入合法但如果你自己本地测试时手抖输入了这种只有一个运算符的串没有保护的话会直接读到数组下标 -1程序崩得莫名其妙。加一句if (top 2) return 0;之类的保护调试时会舒服很多。2.3 除法语义整数截断、除零和跨语言差异如果题目的操作数是整数那么除法这块有三个问题要一次性想清楚。第一结果是整数还是小数。大多数这类题目都是整数运算输出也是整数那就直接走整数除法。但要留意题目有没有说“结果保留两位小数”或者“保证整除”如果说了保证整除那你用整数除法和浮点除法都对如果没说就得看输出样例——样例里出现.00或者小数位那就必须用浮点。第二除零怎么处理。题目一般保证不会出现除零但你不加保护本地测试的时候一旦手滑就崩溃。我习惯加一行判断除零时按 0 处理或者直接输出一个约定的错误标记。注意别加太复杂的逻辑这题的重点不在异常处理。第三不同语言的除法行为不一样。C、C、Java 的整数除法是向零截断-7 / 2得到-3Python 的//是向下取整-7 // 2得到-4。如果你用 Python 写中间结果又可能出现负数这个差异会让结果对不上。解决办法是用int(a / b)这种先做浮点除再截断的方式或者干脆全程用 float。这个问题在纯非负数的输入里不会暴露一旦出现负数就会很难查因为你看不出来是哪里错的。语言-7 / 2说明C / C-3向零截断Java-3向零截断Python/-3.5得到浮点数Python//-4向下取整容易踩2.4 栈的落地实现数组模拟还是用现成的容器这是一个典型的“两种写法都对但适用场景不同”的选择。数组模拟栈的优势是快、无额外开销、下标操作顺手写起来也就多两行top和--top。缺点是容量要预估估小了下标越界估大了浪费空间。不过这类题目的表达式长度一般也就几千到十万级别开一个十万的数组完全够用不需要纠结。用std::stack或者std::vector的优势是省心不用管容量push和pop一眼就懂代码可读性更好。缺点是在竞赛环境下stack的常数开销比数组大一点虽然在这道题的数据规模下完全可以忽略。另外std::stack的pop()不返回值必须top()和pop()分两步写稍微啰嗦。我的选择是本地练习和写博客用vector正式提交和追求极限用数组。理由很简单vector版代码短、易读、不容易写错下标配合reserve也不会有频繁扩容的开销数组版在完全想清楚之后写一遍可以顺便把top的变化过程在脑子里过一遍对理解栈有帮助。实现方式优点缺点适用场景数组 手工 top快、可控、下标直观容量要预估竞赛提交std::vector安全、自动扩容、可读性好略有开销日常练习、教学std::stack语义最贴合“栈”取栈顶和弹栈要分两步强调概念时2.5 终止条件与输入读取#、换行、空格一个都不能漏输入读取这块坑点集中在“怎么读”和“读到哪停”。先说“怎么读”。如果表达式里没有空格用scanf(%s, buf)或cin s一行读入就够了它们会自动跳过前导空白并读到下一个空白为止。但如果表达式里有空格cin s只会读到第一个空格后面的内容全丢你就只能拿到3这一个数。这种情况下必须用getline(cin, s)读整行。getline也有自己的麻烦。如果前面用过cin n之类的格式化输入缓冲区里会残留一个换行符getline会立刻把它读走得到一个空串。解决办法是在getline之前加一句cin.ignore()或者干脆全程用getline再自己解析。再说“读到哪停”。题目常见的结束标记有这几种以#结尾、读到行尾、读到文件结束。用#的话循环条件写成s[i] ! #或者在循环体里判断到#就break。注意别写成“把#当普通字符处理”那会导致你的运算符分支走到default分支计算出一个乱七八糟的数压进栈。读到行尾的话注意末尾可能有多余的空格和回车符\r有些测试数据是从别处导出的这些都要过滤掉否则它们会走进运算分支。还有一个隐蔽的问题表达式可能在最后一个运算符之后就结束了栈里就剩一个元素。这时候你直接取st[top-1]是对的但如果表达式末尾有多余的运算符或者是空表达式top可能是 0 或者负数直接取就崩了。虽然题目基本保证输入合法但本地调试时手滑的概率不低加个保护性输出会更省事。3. 动手实现从骨架到完整代码3.1 主流程骨架先把循环写出来再填细节在写具体代码之前我习惯先用注释把框架搭出来。这个习惯是被人教会的先把流程控制写清楚细节留成TODO能让你的注意力集中在“逻辑顺序对不对”上而不是一开始就陷进某个字符怎么转数字的细节里。骨架大致长这样读入整个表达式字符串 初始化空栈 top 0 for 从左到右扫描每个字符: 如果是空白字符: 跳过, 继续 如果是结束标记 #: 跳出循环 如果是数字: 解析成操作数, 压栈 否则 (运算符): b 弹出栈顶 a 弹出栈顶 r 计算 a (运算符) b 把 r 压栈 输出栈顶元素这个骨架里有两个地方值得反复确认一是“解析成操作数”这一步在单字符版本里是一行在多位数版本里是一个内层循环二是“弹出两次”的顺序写的时候一定要在旁边注释标上谁是左、谁是右别靠短期记忆。骨架写好之后剩下的工作其实是填空题。我建议先用最笨的方式把两个版本各写一遍而不是直接抄现成的模板。抄模板的结果是下次遇到变体你还是不会因为你没在脑子里跑过一遍流程。3.2 版本一一位数字、无空格输入的紧凑写法这个版本对应最常见的形态输入一串紧凑字符操作数都是 0 到 9 的一位数字以#结尾。代码用 C 语言风格的数组栈逻辑直白适合直接提交。#include cstdio const int MAXN 100005; // 栈容量, 足够放下最长的表达式 char expr[MAXN]; // 存后缀表达式字符串 long long st[MAXN]; // 数值栈, 用 long long 防溢出 int main() { scanf(%s, expr); // 读入一整串, 遇空白停止 int top 0; // 栈顶指针, 指向下一个空位 // 逐字符扫描, 遇到结束标记 # 或字符串结束就停 for (int i 0; expr[i] ! \0 expr[i] ! #; i) { char c expr[i]; if (c 0 c 9) { // 一位数字直接转成数值压栈 st[top] c - 0; } else { // 运算符: 先弹右操作数, 再弹左操作数 long long b st[--top]; // 右操作数 long long a st[--top]; // 左操作数 long long r 0; switch (c) { case : r a b; break; case -: r a - b; break; case *: r a * b; break; case /: r (b 0) ? 0 : a / b; break; default: break; // 非法字符直接忽略 } st[top] r; // 结果压回栈中 } } printf(%lld\n, st[top - 1]); // 栈里只剩一个数, 就是结果 return 0; }这段代码有几个点值得单独说。st[--top]是先把指针减一再取那个位置的值等价于“弹出”比先写--top再写st[top]紧凑但意思一样读的时候别晕。switch里default分支留空是为了容错万一输入里混进了换行或者其他字符不至于算出一个随机结果。long long的选择不是随手写的。如果操作数是较大的整数连乘几次就可能超出int的范围虽然这道题的数据一般不会那么大但用long long的成本几乎为零printf里换成%lld就行属于典型的“花小钱买安心”。再看一个具体的执行过程输入345*#步骤读到的字符操作栈内容底→顶13压栈[3]24压栈[3, 4]3弹 4、弹 3算 347压栈[7]45压栈[7, 5]5*弹 5、弹 7算 7*535压栈[35]6#结束循环[35]最后输出 35和手算一致。这种表格我建议在纸上自己画一遍特别是减法和除法的例子画完你就再也不会搞错顺序了。3.3 版本二多位数、允许空格输入的通用写法如果样例里出现了两位数或者输入里有空格就必须换成这个版本。核心变化有两个用getline读整行数字要用内层循环拼接。#include iostream #include string #include vector using namespace std; int main() { string s; getline(cin, s); // 读整行, 保留空格 vectorlong long st; st.reserve(s.size()); // 预留空间, 避免频繁扩容 for (size_t i 0; i s.size(); i) { char c s[i]; // 过滤空格和控制字符 if (c || c \t || c \r) continue; // 结束标记 if (c #) break; if (c 0 c 9) { // 连续数字拼成一个多位数 long long num 0; while (i s.size() s[i] 0 s[i] 9) { num num * 10 (s[i] - 0); i; } --i; // 关键一步: 退回到非数字字符上 st.push_back(num); } else { // 运算符处理 long long b st.back(); st.pop_back(); // 右操作数 long long a st.back(); st.pop_back(); // 左操作数 long long r 0; switch (c) { case : r a b; break; case -: r a - b; break; case *: r a * b; break; case /: r (b 0) ? 0 : a / b; break; default: break; } st.push_back(r); } } cout st.back() endl; // 最终栈底那个数就是结果 return 0; }那个--i是整段代码里最容易被删掉的一行也是最不能删的一行。我第一次写这个版本的时候就是漏了它输入12 3 #输出 12 而不是 15盯着看了十几分钟才反应过来是被跳过了。后来我的习惯是每次写完内层 while 循环第一时间就问自己“循环结束后下标停在哪外层还会不会再动它”。还有一个细节如果你用的是while (i s.size() ...)这种写法注意别在i已经等于s.size()的情况下再去访问s[i]尤其是把--i放在循环外面的时候逻辑要捋清楚。这里因为 while 的条件先判断再访问是安全的。对于负数操作数这个版本没有处理。要加的话可以在判断数字之前插入一段// 负号判定: 当前是 -, 且它处在操作数位置 if (c - (i 1 s.size() s[i1] 0 s[i1] 9) (i 0 || s[i-1] || s[i-1] ()) { // 当作负号, 让下一轮从数字开始解析 // 这里可以做一个标记, 在解析数字时取反 }但这套判定规则在复杂的表达式里会越来越绕我只在题目明确要求时才写。日常刷题时先确认数据范围能不加就不加加了反而更容易引入新 bug。3.4 测试用例设计不要只跑样例样例只能证明你的代码在一种情况下对测不出边界问题。我一般会准备五类数据来打自己的代码用例输入期望输出考察点基本加减12#3最简流程混合运算123*4#13顺序与优先级后缀天然有序减法方向35-#2弹栈顺序除法方向62/#3操作数位置单个数9#9边界无运算符连续运算234*5-#15多次压弹交错多位数12 3 #15数字拼接正确性大数连乘99*9*9*#729溢出风险这些用例不需要写自动化脚本手工跑一遍对着手算的结果比对就行。我的经验是每加一个新功能就把这张表跑一遍比事后猜哪里出问题快得多。特别注意减法那条35-#它能一次性把弹栈顺序问题揪出来除法那条62/#整数截断如果没做对会输出 0一眼就能看出来。还有一类隐形的边界是“只有一个操作数”和“表达式末尾带空格”。前者考验你的循环是否能正常退出后者考验空格过滤是否彻底。这两类数据一般不会出现在正式测试里但你在本地调试时会遇到提前准备好就不用临时改代码。4. 坑点实录交之前先拿这几组数据打自己一遍4.1 高频坑点速查表下面这张表是我这几年攒下来的基本上覆盖了这道题九成以上的失分场景。写代码时对着看一眼能省掉很多次“提交——红——改——再提交”的循环。编号现象根因修法1结果等于栈底的某个操作数内层解析循环把运算符跳过了while 后补--i2减法结果符号相反弹栈顺序反了先弹的是右操作数3除法结果总是 0被除数除数位置颠倒或整数截断检查a/b位置4多位数被拆成多个操作数按单字符方式解析了改为连续数字拼接5紧凑输入被并成一个大数按多位数方式解析了看清样例再选策略6程序读到一半崩溃字符被当成运算符弹栈时越界完善default分支7大数结果溢出成负数用了int存储中间结果换long long8带空格输入只读到第一个数用了cin 而非getline换getline并过滤空格9getline读到空串输入缓冲区残留换行先cin.ignore()10输出格式不对多空格或少换行输出语句不规范严格按样例格式这些坑里有几个是“改起来只要一行找起来要半小时”的类型。比如第 9 条getline读到空串这个问题第一次遇到会完全懵因为程序明明没报错只是直接输出一个空结果就退出了。知道了原因之后加一句cin.ignore()就完事。4.2 三次典型翻车现场还原说几个我自己真实踩过的场景比抽象讲道理有用。第一次翻车减法顺序。当时写的代码是“弹出 a弹出 b算 a - b”样例里刚好是6 4 -输出 -2我还以为是栈写错了查了半天栈的实现。后来拿纸笔把6 4 -的流程走了一遍才反应过来栈顶是 4弹出的是右操作数。这个错误之所以难查是因为它不影响加法和乘法如果测试数据里减法很少你甚至可能一直看不出问题。第二次翻车多位数解析跳字符。版本二写完单跑12 3 #输出 12我第一反应是“空格没处理好”改了半天空格过滤越改越乱。后来在 while 循环后面打了一行调试输出发现根本没进过运算符分支——原来是被内层循环吃掉了。这个教训让我养成了一个习惯解析类循环写完后立刻打印每个 token 的切分结果比事后猜快十倍。第三次翻车整数溢出。那时候我用int存中间结果测试数据里有个连乘结果变成负数。我盯着代码看了很久怀疑是栈指针算错了最后才想起int只有三十二位几次相乘就爆了。换成long long之后一切正常。这个错误的隐蔽之处在于小数据全对大数据才出错如果你只跑样例永远发现不了。这三次的共同点是错误都不在“算法思路”上而在“实现细节”上。这也说明为什么这道题虽然思路一句话就能讲完却依然值得认真写一遍思路正确只是及格线细节正确才拿得到分。4.3 我的赛前自检清单每次提交前我会对着下面这几条快速过一遍耗时不到一分钟但能挡掉大部分低级错误数字解析方式是否和样例一致一位数还是多位数减法和除法的操作数顺序是否是“左 op 右”中间结果是否用了足够宽的整型结束标记#有没有被正确识别并跳出输入带空格时读取方式是否用了整行读输出格式是否和样例完全一致换行、空格栈为空时是否有保护避免下标越界除零有没有兜底这份清单不复杂但非常有效。很多人提交前只看“样例过了没”而样例往往是最简单的那组数据过了样例不等于过了题。5. 往上再走一步这道题的变体与延伸练习5.1 浮点数版本把整型栈换成 double 栈有些题目会把操作数改成小数或者要求结果保留若干位小数。改动其实不大把栈的元素类型从long long换成double除法直接算输出格式按题目要求控制。#include iostream #include string #include vector #include cstdio using namespace std; int main() { string s; getline(cin, s); vectordouble st; for (size_t i 0; i s.size(); i) { char c s[i]; if (c || c \t) continue; if (c #) break; if ((c 0 c 9) || c .) { // 解析小数: 整数部分 小数部分 double num 0; bool dot false; double base 0.1; while (i s.size() ((s[i] 0 s[i] 9) || s[i] .)) { if (s[i] .) { dot true; } else if (!dot) { num num * 10 (s[i] - 0); } else { num (s[i] - 0) * base; base * 0.1; } i; } --i; st.push_back(num); } else { double b st.back(); st.pop_back(); double a st.back(); st.pop_back(); double r 0; switch (c) { case : r a b; break; case -: r a - b; break; case *: r a * b; break; case /: r a / b; break; } st.push_back(r); } } printf(%.2f\n, st.back()); // 按题目要求控制小数位 return 0; }浮点版本要注意两件事一是小数解析的精度0.1这种基数连乘会累积误差如果题目对精度要求高最好用字符串截取的方式处理二是输出格式printf(%.2f)和cout fixed setprecision(2)都要试一下看题目要的是四舍五入还是截断。另外浮点比较不要用这在别的题里是老生常谈在这道题里主要影响的是“结果是否为 0”这类判断。5.2 中缀转后缀再求值完整链路怎么串有些题目会要求先做中缀转后缀再做求值也有些题目直接给你中缀式让你一步到位。后者的常见做法是“边转换边求值”用一个运算符栈和一个数值栈同步操作逻辑比“先转再算”更紧凑但调试起来更难。中缀转后缀的核心是优先级规则遇到操作数直接输出或者直接压数值栈遇到运算符时先把运算符栈里所有优先级不低于它的运算符弹出并执行再把自己压进去遇到左括号直接压栈遇到右括号则一直弹到左括号为止。乘除优先级高于加减同级从左到右。这套流程的难点在于括号和优先级的组合判断。我的建议是先用“先完整转换成后缀串再对后缀串求值”的两段式写法每一步都能单独验证出错了也好定位等两段式写熟了再合并成一段式。直接上合并版的人往往会在括号嵌套三层的时候彻底迷失。顺带说一句如果你已经能熟练写后缀求值那么中缀转后缀其实就是把“求值”那一步换成“输出”数值栈换成输出序列其余流程几乎一模一样。这两道题放在一起练效果比单独刷要好。5.3 用这题练调试的三个习惯这道题代码量不大但特别适合拿来练调试习惯因为它出错的地方都很具体能被观察和验证。第一个习惯是手算样例。在写代码之前先在纸上把样例的压栈弹栈过程画一遍标出每一步栈里的内容。这一步花不了两分钟但能让你在动笔之前就发现“哦减法是右减左”这种问题。我认识的写这题从不出错的人基本都是先在纸上跑一遍的。第二个习惯是打印中间状态。在循环体里加一行输出把当前字符和栈里所有元素打出来跑一遍小数据你就能清楚看到哪一步开始跟预期不一致。这个方法看起来笨但对“结果不对但不知道错在哪”的情况特别有效。调试完记得删掉或者注释掉别留在提交代码里。第三个习惯是构造反例。样例过了之后主动想一个“如果我的代码写错了会在什么输入下暴露”的数据。比如怀疑弹栈顺序就构造一个35-#怀疑数字拼接就构造一个12 34 #怀疑溢出就构造一个连乘。这套反向思维练熟了你排查问题的速度会明显变快。我在实际使用中发现这道题最值得反复写的地方不是算法本身而是它把“边界条件”这四个字具象化了输入格式的边界、操作数范围的边界、运算语义的边界每一条都能对应到一段具体的代码。写熟之后再遇到类似的表达式解析题、计算器题、配置解析题思路基本可以直接迁移过去。 
长河君 · 2026/11/3 4:28:07 · 阅读 1.2k 后缀式求值全解析：栈、弹栈顺序与边界条件避坑指南
后缀式求值这道题编号 7-425 分在各类数据结构课程的在线判题平台上常年驻扎属于“看起来一句话就能说完、真正写起来到处漏风”的典型。它考的不是你会不会用栈而是你能不能把栈用对——数字怎么识别、两个操作数谁先谁后、除法怎么处理、输入到什么位置停任何一环想歪一点代码在样例上跑得通提交上去就是一排红。我前后在不同语言、不同平台上重写过这道题不下十遍最早那次卡了很久最后发现是减法的两个操作数顺序反了。所以这篇东西不打算停留在“建个栈、遇数就压、遇符就弹”这种一句话版本而是把题目背后每一个可能让你丢分的细节拆开讲从输入形态的判断到多位数解析的边界再到除法语义和溢出最后给出一份能直接抄的完整代码和一份踩坑清单。刚学完栈、正在被这题卡住的同学能直接用已经过了但想补基础的同学也能从里面捞出一些平时不会注意的东西。1. 先把题目吃透后缀式求值到底考什么1.1 从人的阅读习惯说起中缀式子为什么“不好算”我们平时写的(12)*34这种叫中缀表达式运算符夹在两个操作数中间人的阅读习惯是这样但计算机处理起来很别扭它得先判断括号范围再看乘除优先于加减还得处理同级从左到右本质上是要维护一棵隐式的语法树。你写出来的代码会变成两层循环、一个优先级表稍微一复杂就绕。后缀表达式也叫逆波兰表达式把运算符挪到操作数后面(12)*34写成后缀就是1 2 3 * 4 。这个形态丢掉了括号也丢掉了优先级读到哪算到哪从左往右一遍扫完就能出结果中间不需要回退也不需要“记住”什么东西。计算机喜欢这种结构因为它的处理流程是线性的每一步都对已经处理过的部分做一次规约——把“两个数 一个运算符”缩成“一个数”。正是因为这个特性后缀式求值成了栈这个数据结构的入门第一课每一步都能清楚地对应到一次压栈或弹栈讲原理的时候画图特别顺写代码的时候却没有那么多拐弯。反过来说也正因为流程太直白很多人写的时候不过脑子细节全凭直觉然后就翻车了。1.2 栈在这里扮演的角色一个自助餐托盘架我用一个更接地气的类比来解释栈在这道题里干什么。想象食堂门口的自助餐托盘架弹簧托盘架那种你拿走一个托盘上面的托盘会自动顶上来你只能从最上面拿放回去也只能放最上面。这就是“后进先出”。后缀式求值的流程就是围绕这个架子展开的从左到右扫表达式碰到数字就当作一个托盘放上去碰到运算符就从架子上取两个托盘下来用这个运算符把两个数算成一个新托盘再放回去。扫完之后架子上应该只剩一个托盘那个数就是结果。这里有个关键点需要强调取两个托盘的时候先取下来的是右操作数后取下来的是左操作数。这个顺序在加法和乘法里没有影响ab和ba一样但在减法和除法里就是致命错误。很多人写代码的时候顺手写成“先弹出来的减后弹出来的”样例刚好是加法或者刚好是6 3 -这种正序就蒙混过关了一旦遇到3 5 -直接废掉。1.3 输入形态决定实现方案两种常见版本必须先分清楚这一点是最容易被忽略、又最该在动手前确认的。同一个题名下的“后缀式求值”输入格式至少有两大类代码写法完全不同版本类型典型输入操作数识别方式读取方式容易踩的雷紧凑型345*#每个数字字符就是一个操作数整串读入逐字符扫描误把34当一个数空格分隔型3 4 5 * #连续数字串构成一个多位数读整行跳过空格空格没跳过数字断成两半混合型3 45*#需要按样例判断逐字符扫描 空格过滤规则没定义清楚全凭猜这两类写法的核心区别在于“数字的边界在哪里”。紧凑型里34表示两个操作数 3 和 4因为题目保证操作数都是一位数字空格分隔型里34表示一个数三十四。你要是把这两种搞反代码可能连样例都过不去也可能样例过了但隐藏测试点全错。我的建议很实在打开题目先看样例再决定写法不要凭记忆。如果样例里出现10、25这种两位数那必然是空格分隔或者有明确的多位数字规则如果样例是345*#这种紧贴的那就按单字符来。判断清楚以后再动键盘能省掉一半的调试时间。补充一点有些版本会明确写“操作数为 0-9 的一位数”有些版本会写“操作数为不超过若干位的正整数”还有些版本会以#结尾表示输入结束。这些约定都必须逐字读一遍它们直接决定了你的解析循环怎么写。我见过的最冤的情况是题目明明说“以 # 结尾”有人没看到把#当成非法字符跳过结果循环跑飞数组越界。2. 核心细节拆解五个决定成败的处理点2.1 数字识别从“一个字符”到“一个数”的转换数字识别看起来是最简单的一步实际上藏着最多歧义。在紧凑型里你的判断就是“这个字符是不是 0 到 9”是的话直接c - 0转成数值压栈一行代码搞定。但在多位数版本里你要做的是“从当前位置开始不断往后吞数字字符直到遇到非数字”把它拼成一个完整的整数。这个“吞”的过程有个经典写法陷阱long long num 0; while (i s.size() s[i] 0 s[i] 9) { num num * 10 (s[i] - 0); i; }循环结束时i指向的是第一个非数字字符。而外层通常是个for循环会在每轮末尾再执行一次i于是这个非数字字符就被跳过了。如果那个字符正好是运算符你相当于白白丢掉了一个运算符后面的计算全错。正确的做法是在 while 结束后补一句--i;把位置退回到非数字字符上让外层循环去处理它。这个细节我至少见过七八个同学踩过表现症状是“输入12 3 #输出 12 而不是 15”——因为被跳过了栈里剩下两个数最后输出的是栈底那个。看到这种“结果刚好等于某个操作数”的现象第一反应就该怀疑是不是跳字符了。还有一点如果你的题目里允许负数操作数比如-3 5 那-这个字符就有了双重身份既可能是减号也可能是负号。区分办法是看它出现的上下文如果前一个非空格字符是运算符或者开头那它大概率是负号如果前一个 token 是操作数那它就是减号。这个判断逻辑会显著增加代码复杂度而绝大多数在线判题的这类题目并不要求处理负数操作数所以在动手前确认一下不要过度设计。我自己的习惯是先按“操作数非负”写如果样例里真出现了负数再补判定分支。2.2 弹栈顺序减法和除法的唯一正确姿势这一节单独拎出来讲因为它是这道题最高频的失分点。流程是这样的读到运算符时栈顶是右操作数栈顶下面那个是左操作数。所以代码必须是long long b st[--top]; // 先弹出来的是右操作数 long long a st[--top]; // 后弹出来的是左操作数 long long r a - b; // 左 op 右为什么是这个顺序把表达式5 3 -按流程走一遍先压 5再压 3栈从底到顶是[5, 3]。读到减号弹出栈顶 3这是右操作数再弹出 5这是左操作数计算5 - 3 2压回去。结果 2符合预期。如果顺序写反变成3 - 5 -2样例如果是6 4 -就会输出 -2 而不是 2。而如果你运气好样例里只有加法那么正反都是对的代码就能过样例——然后在隐藏测试点上全军覆没。这种行为模式特别坑因为它给你一种“我写对了”的错觉。除法的道理完全一样a / b里a是被除数b是除数顺序反了结果差得离谱。6 3 /正确是 2反了变成 0因为整数除法 3/6 截断成 0。看到结果莫名其妙变成 0先查这个。提示在弹栈之前一定要判一下栈里的元素够不够两个。题目一般保证输入合法但如果你自己本地测试时手抖输入了这种只有一个运算符的串没有保护的话会直接读到数组下标 -1程序崩得莫名其妙。加一句if (top 2) return 0;之类的保护调试时会舒服很多。2.3 除法语义整数截断、除零和跨语言差异如果题目的操作数是整数那么除法这块有三个问题要一次性想清楚。第一结果是整数还是小数。大多数这类题目都是整数运算输出也是整数那就直接走整数除法。但要留意题目有没有说“结果保留两位小数”或者“保证整除”如果说了保证整除那你用整数除法和浮点除法都对如果没说就得看输出样例——样例里出现.00或者小数位那就必须用浮点。第二除零怎么处理。题目一般保证不会出现除零但你不加保护本地测试的时候一旦手滑就崩溃。我习惯加一行判断除零时按 0 处理或者直接输出一个约定的错误标记。注意别加太复杂的逻辑这题的重点不在异常处理。第三不同语言的除法行为不一样。C、C、Java 的整数除法是向零截断-7 / 2得到-3Python 的//是向下取整-7 // 2得到-4。如果你用 Python 写中间结果又可能出现负数这个差异会让结果对不上。解决办法是用int(a / b)这种先做浮点除再截断的方式或者干脆全程用 float。这个问题在纯非负数的输入里不会暴露一旦出现负数就会很难查因为你看不出来是哪里错的。语言-7 / 2说明C / C-3向零截断Java-3向零截断Python/-3.5得到浮点数Python//-4向下取整容易踩2.4 栈的落地实现数组模拟还是用现成的容器这是一个典型的“两种写法都对但适用场景不同”的选择。数组模拟栈的优势是快、无额外开销、下标操作顺手写起来也就多两行top和--top。缺点是容量要预估估小了下标越界估大了浪费空间。不过这类题目的表达式长度一般也就几千到十万级别开一个十万的数组完全够用不需要纠结。用std::stack或者std::vector的优势是省心不用管容量push和pop一眼就懂代码可读性更好。缺点是在竞赛环境下stack的常数开销比数组大一点虽然在这道题的数据规模下完全可以忽略。另外std::stack的pop()不返回值必须top()和pop()分两步写稍微啰嗦。我的选择是本地练习和写博客用vector正式提交和追求极限用数组。理由很简单vector版代码短、易读、不容易写错下标配合reserve也不会有频繁扩容的开销数组版在完全想清楚之后写一遍可以顺便把top的变化过程在脑子里过一遍对理解栈有帮助。实现方式优点缺点适用场景数组 手工 top快、可控、下标直观容量要预估竞赛提交std::vector安全、自动扩容、可读性好略有开销日常练习、教学std::stack语义最贴合“栈”取栈顶和弹栈要分两步强调概念时2.5 终止条件与输入读取#、换行、空格一个都不能漏输入读取这块坑点集中在“怎么读”和“读到哪停”。先说“怎么读”。如果表达式里没有空格用scanf(%s, buf)或cin s一行读入就够了它们会自动跳过前导空白并读到下一个空白为止。但如果表达式里有空格cin s只会读到第一个空格后面的内容全丢你就只能拿到3这一个数。这种情况下必须用getline(cin, s)读整行。getline也有自己的麻烦。如果前面用过cin n之类的格式化输入缓冲区里会残留一个换行符getline会立刻把它读走得到一个空串。解决办法是在getline之前加一句cin.ignore()或者干脆全程用getline再自己解析。再说“读到哪停”。题目常见的结束标记有这几种以#结尾、读到行尾、读到文件结束。用#的话循环条件写成s[i] ! #或者在循环体里判断到#就break。注意别写成“把#当普通字符处理”那会导致你的运算符分支走到default分支计算出一个乱七八糟的数压进栈。读到行尾的话注意末尾可能有多余的空格和回车符\r有些测试数据是从别处导出的这些都要过滤掉否则它们会走进运算分支。还有一个隐蔽的问题表达式可能在最后一个运算符之后就结束了栈里就剩一个元素。这时候你直接取st[top-1]是对的但如果表达式末尾有多余的运算符或者是空表达式top可能是 0 或者负数直接取就崩了。虽然题目基本保证输入合法但本地调试时手滑的概率不低加个保护性输出会更省事。3. 动手实现从骨架到完整代码3.1 主流程骨架先把循环写出来再填细节在写具体代码之前我习惯先用注释把框架搭出来。这个习惯是被人教会的先把流程控制写清楚细节留成TODO能让你的注意力集中在“逻辑顺序对不对”上而不是一开始就陷进某个字符怎么转数字的细节里。骨架大致长这样读入整个表达式字符串 初始化空栈 top 0 for 从左到右扫描每个字符: 如果是空白字符: 跳过, 继续 如果是结束标记 #: 跳出循环 如果是数字: 解析成操作数, 压栈 否则 (运算符): b 弹出栈顶 a 弹出栈顶 r 计算 a (运算符) b 把 r 压栈 输出栈顶元素这个骨架里有两个地方值得反复确认一是“解析成操作数”这一步在单字符版本里是一行在多位数版本里是一个内层循环二是“弹出两次”的顺序写的时候一定要在旁边注释标上谁是左、谁是右别靠短期记忆。骨架写好之后剩下的工作其实是填空题。我建议先用最笨的方式把两个版本各写一遍而不是直接抄现成的模板。抄模板的结果是下次遇到变体你还是不会因为你没在脑子里跑过一遍流程。3.2 版本一一位数字、无空格输入的紧凑写法这个版本对应最常见的形态输入一串紧凑字符操作数都是 0 到 9 的一位数字以#结尾。代码用 C 语言风格的数组栈逻辑直白适合直接提交。#include cstdio const int MAXN 100005; // 栈容量, 足够放下最长的表达式 char expr[MAXN]; // 存后缀表达式字符串 long long st[MAXN]; // 数值栈, 用 long long 防溢出 int main() { scanf(%s, expr); // 读入一整串, 遇空白停止 int top 0; // 栈顶指针, 指向下一个空位 // 逐字符扫描, 遇到结束标记 # 或字符串结束就停 for (int i 0; expr[i] ! \0 expr[i] ! #; i) { char c expr[i]; if (c 0 c 9) { // 一位数字直接转成数值压栈 st[top] c - 0; } else { // 运算符: 先弹右操作数, 再弹左操作数 long long b st[--top]; // 右操作数 long long a st[--top]; // 左操作数 long long r 0; switch (c) { case : r a b; break; case -: r a - b; break; case *: r a * b; break; case /: r (b 0) ? 0 : a / b; break; default: break; // 非法字符直接忽略 } st[top] r; // 结果压回栈中 } } printf(%lld\n, st[top - 1]); // 栈里只剩一个数, 就是结果 return 0; }这段代码有几个点值得单独说。st[--top]是先把指针减一再取那个位置的值等价于“弹出”比先写--top再写st[top]紧凑但意思一样读的时候别晕。switch里default分支留空是为了容错万一输入里混进了换行或者其他字符不至于算出一个随机结果。long long的选择不是随手写的。如果操作数是较大的整数连乘几次就可能超出int的范围虽然这道题的数据一般不会那么大但用long long的成本几乎为零printf里换成%lld就行属于典型的“花小钱买安心”。再看一个具体的执行过程输入345*#步骤读到的字符操作栈内容底→顶13压栈[3]24压栈[3, 4]3弹 4、弹 3算 347压栈[7]45压栈[7, 5]5*弹 5、弹 7算 7*535压栈[35]6#结束循环[35]最后输出 35和手算一致。这种表格我建议在纸上自己画一遍特别是减法和除法的例子画完你就再也不会搞错顺序了。3.3 版本二多位数、允许空格输入的通用写法如果样例里出现了两位数或者输入里有空格就必须换成这个版本。核心变化有两个用getline读整行数字要用内层循环拼接。#include iostream #include string #include vector using namespace std; int main() { string s; getline(cin, s); // 读整行, 保留空格 vectorlong long st; st.reserve(s.size()); // 预留空间, 避免频繁扩容 for (size_t i 0; i s.size(); i) { char c s[i]; // 过滤空格和控制字符 if (c || c \t || c \r) continue; // 结束标记 if (c #) break; if (c 0 c 9) { // 连续数字拼成一个多位数 long long num 0; while (i s.size() s[i] 0 s[i] 9) { num num * 10 (s[i] - 0); i; } --i; // 关键一步: 退回到非数字字符上 st.push_back(num); } else { // 运算符处理 long long b st.back(); st.pop_back(); // 右操作数 long long a st.back(); st.pop_back(); // 左操作数 long long r 0; switch (c) { case : r a b; break; case -: r a - b; break; case *: r a * b; break; case /: r (b 0) ? 0 : a / b; break; default: break; } st.push_back(r); } } cout st.back() endl; // 最终栈底那个数就是结果 return 0; }那个--i是整段代码里最容易被删掉的一行也是最不能删的一行。我第一次写这个版本的时候就是漏了它输入12 3 #输出 12 而不是 15盯着看了十几分钟才反应过来是被跳过了。后来我的习惯是每次写完内层 while 循环第一时间就问自己“循环结束后下标停在哪外层还会不会再动它”。还有一个细节如果你用的是while (i s.size() ...)这种写法注意别在i已经等于s.size()的情况下再去访问s[i]尤其是把--i放在循环外面的时候逻辑要捋清楚。这里因为 while 的条件先判断再访问是安全的。对于负数操作数这个版本没有处理。要加的话可以在判断数字之前插入一段// 负号判定: 当前是 -, 且它处在操作数位置 if (c - (i 1 s.size() s[i1] 0 s[i1] 9) (i 0 || s[i-1] || s[i-1] ()) { // 当作负号, 让下一轮从数字开始解析 // 这里可以做一个标记, 在解析数字时取反 }但这套判定规则在复杂的表达式里会越来越绕我只在题目明确要求时才写。日常刷题时先确认数据范围能不加就不加加了反而更容易引入新 bug。3.4 测试用例设计不要只跑样例样例只能证明你的代码在一种情况下对测不出边界问题。我一般会准备五类数据来打自己的代码用例输入期望输出考察点基本加减12#3最简流程混合运算123*4#13顺序与优先级后缀天然有序减法方向35-#2弹栈顺序除法方向62/#3操作数位置单个数9#9边界无运算符连续运算234*5-#15多次压弹交错多位数12 3 #15数字拼接正确性大数连乘99*9*9*#729溢出风险这些用例不需要写自动化脚本手工跑一遍对着手算的结果比对就行。我的经验是每加一个新功能就把这张表跑一遍比事后猜哪里出问题快得多。特别注意减法那条35-#它能一次性把弹栈顺序问题揪出来除法那条62/#整数截断如果没做对会输出 0一眼就能看出来。还有一类隐形的边界是“只有一个操作数”和“表达式末尾带空格”。前者考验你的循环是否能正常退出后者考验空格过滤是否彻底。这两类数据一般不会出现在正式测试里但你在本地调试时会遇到提前准备好就不用临时改代码。4. 坑点实录交之前先拿这几组数据打自己一遍4.1 高频坑点速查表下面这张表是我这几年攒下来的基本上覆盖了这道题九成以上的失分场景。写代码时对着看一眼能省掉很多次“提交——红——改——再提交”的循环。编号现象根因修法1结果等于栈底的某个操作数内层解析循环把运算符跳过了while 后补--i2减法结果符号相反弹栈顺序反了先弹的是右操作数3除法结果总是 0被除数除数位置颠倒或整数截断检查a/b位置4多位数被拆成多个操作数按单字符方式解析了改为连续数字拼接5紧凑输入被并成一个大数按多位数方式解析了看清样例再选策略6程序读到一半崩溃字符被当成运算符弹栈时越界完善default分支7大数结果溢出成负数用了int存储中间结果换long long8带空格输入只读到第一个数用了cin 而非getline换getline并过滤空格9getline读到空串输入缓冲区残留换行先cin.ignore()10输出格式不对多空格或少换行输出语句不规范严格按样例格式这些坑里有几个是“改起来只要一行找起来要半小时”的类型。比如第 9 条getline读到空串这个问题第一次遇到会完全懵因为程序明明没报错只是直接输出一个空结果就退出了。知道了原因之后加一句cin.ignore()就完事。4.2 三次典型翻车现场还原说几个我自己真实踩过的场景比抽象讲道理有用。第一次翻车减法顺序。当时写的代码是“弹出 a弹出 b算 a - b”样例里刚好是6 4 -输出 -2我还以为是栈写错了查了半天栈的实现。后来拿纸笔把6 4 -的流程走了一遍才反应过来栈顶是 4弹出的是右操作数。这个错误之所以难查是因为它不影响加法和乘法如果测试数据里减法很少你甚至可能一直看不出问题。第二次翻车多位数解析跳字符。版本二写完单跑12 3 #输出 12我第一反应是“空格没处理好”改了半天空格过滤越改越乱。后来在 while 循环后面打了一行调试输出发现根本没进过运算符分支——原来是被内层循环吃掉了。这个教训让我养成了一个习惯解析类循环写完后立刻打印每个 token 的切分结果比事后猜快十倍。第三次翻车整数溢出。那时候我用int存中间结果测试数据里有个连乘结果变成负数。我盯着代码看了很久怀疑是栈指针算错了最后才想起int只有三十二位几次相乘就爆了。换成long long之后一切正常。这个错误的隐蔽之处在于小数据全对大数据才出错如果你只跑样例永远发现不了。这三次的共同点是错误都不在“算法思路”上而在“实现细节”上。这也说明为什么这道题虽然思路一句话就能讲完却依然值得认真写一遍思路正确只是及格线细节正确才拿得到分。4.3 我的赛前自检清单每次提交前我会对着下面这几条快速过一遍耗时不到一分钟但能挡掉大部分低级错误数字解析方式是否和样例一致一位数还是多位数减法和除法的操作数顺序是否是“左 op 右”中间结果是否用了足够宽的整型结束标记#有没有被正确识别并跳出输入带空格时读取方式是否用了整行读输出格式是否和样例完全一致换行、空格栈为空时是否有保护避免下标越界除零有没有兜底这份清单不复杂但非常有效。很多人提交前只看“样例过了没”而样例往往是最简单的那组数据过了样例不等于过了题。5. 往上再走一步这道题的变体与延伸练习5.1 浮点数版本把整型栈换成 double 栈有些题目会把操作数改成小数或者要求结果保留若干位小数。改动其实不大把栈的元素类型从long long换成double除法直接算输出格式按题目要求控制。#include iostream #include string #include vector #include cstdio using namespace std; int main() { string s; getline(cin, s); vectordouble st; for (size_t i 0; i s.size(); i) { char c s[i]; if (c || c \t) continue; if (c #) break; if ((c 0 c 9) || c .) { // 解析小数: 整数部分 小数部分 double num 0; bool dot false; double base 0.1; while (i s.size() ((s[i] 0 s[i] 9) || s[i] .)) { if (s[i] .) { dot true; } else if (!dot) { num num * 10 (s[i] - 0); } else { num (s[i] - 0) * base; base * 0.1; } i; } --i; st.push_back(num); } else { double b st.back(); st.pop_back(); double a st.back(); st.pop_back(); double r 0; switch (c) { case : r a b; break; case -: r a - b; break; case *: r a * b; break; case /: r a / b; break; } st.push_back(r); } } printf(%.2f\n, st.back()); // 按题目要求控制小数位 return 0; }浮点版本要注意两件事一是小数解析的精度0.1这种基数连乘会累积误差如果题目对精度要求高最好用字符串截取的方式处理二是输出格式printf(%.2f)和cout fixed setprecision(2)都要试一下看题目要的是四舍五入还是截断。另外浮点比较不要用这在别的题里是老生常谈在这道题里主要影响的是“结果是否为 0”这类判断。5.2 中缀转后缀再求值完整链路怎么串有些题目会要求先做中缀转后缀再做求值也有些题目直接给你中缀式让你一步到位。后者的常见做法是“边转换边求值”用一个运算符栈和一个数值栈同步操作逻辑比“先转再算”更紧凑但调试起来更难。中缀转后缀的核心是优先级规则遇到操作数直接输出或者直接压数值栈遇到运算符时先把运算符栈里所有优先级不低于它的运算符弹出并执行再把自己压进去遇到左括号直接压栈遇到右括号则一直弹到左括号为止。乘除优先级高于加减同级从左到右。这套流程的难点在于括号和优先级的组合判断。我的建议是先用“先完整转换成后缀串再对后缀串求值”的两段式写法每一步都能单独验证出错了也好定位等两段式写熟了再合并成一段式。直接上合并版的人往往会在括号嵌套三层的时候彻底迷失。顺带说一句如果你已经能熟练写后缀求值那么中缀转后缀其实就是把“求值”那一步换成“输出”数值栈换成输出序列其余流程几乎一模一样。这两道题放在一起练效果比单独刷要好。5.3 用这题练调试的三个习惯这道题代码量不大但特别适合拿来练调试习惯因为它出错的地方都很具体能被观察和验证。第一个习惯是手算样例。在写代码之前先在纸上把样例的压栈弹栈过程画一遍标出每一步栈里的内容。这一步花不了两分钟但能让你在动笔之前就发现“哦减法是右减左”这种问题。我认识的写这题从不出错的人基本都是先在纸上跑一遍的。第二个习惯是打印中间状态。在循环体里加一行输出把当前字符和栈里所有元素打出来跑一遍小数据你就能清楚看到哪一步开始跟预期不一致。这个方法看起来笨但对“结果不对但不知道错在哪”的情况特别有效。调试完记得删掉或者注释掉别留在提交代码里。第三个习惯是构造反例。样例过了之后主动想一个“如果我的代码写错了会在什么输入下暴露”的数据。比如怀疑弹栈顺序就构造一个35-#怀疑数字拼接就构造一个12 34 #怀疑溢出就构造一个连乘。这套反向思维练熟了你排查问题的速度会明显变快。我在实际使用中发现这道题最值得反复写的地方不是算法本身而是它把“边界条件”这四个字具象化了输入格式的边界、操作数范围的边界、运算语义的边界每一条都能对应到一段具体的代码。写熟之后再遇到类似的表达式解析题、计算器题、配置解析题思路基本可以直接迁移过去。