如果你正在准备某通信科技公司的机试“实现一个简单的计算器”这道题几乎绕不开。我第一次在在线笔试系统里看到它时心里想不就是小学算术吗真正把代码写出来才发现它考的不是你会不会算数而是你对待字符串、栈和边界条件的耐心。这道题适合所有即将参加机试的求职者也适合想巩固栈、表达式解析这类基础数据结构的开发者。本文会从考点拆解讲到完整代码再把机试现场的常见坑和排查技巧都过一遍争取让你看完就能稳过。1. 题目还原与考点拆解1.1 一道看似“送分”的题先还原一下题目形态给定一个字符串表达式里面只包含非负整数、加号、减号、乘号、除号和左右括号可能夹杂空格要求计算出最终结果。机试里通常限定用 C/C 实现除法按整数除法处理输入长度不会特别夸张时间限制一般给到 1 秒。看起来条件简单却难倒过不少人。这个题最迷惑人的地方在于你觉得自己在做“计算”实际上题目想考的是“解析”。表达式是一长串字符没有现成的树形结构也没有人帮你标好优先级。你得自己从字符流里读出数字识别运算符处理括号嵌套还要在计算过程中时刻保持正确顺序。任何一个环节出错结果都是错的而且往往错得莫名其妙。我第一次尝试时天真地用了最直观的办法从左往右先算乘除再算加减但括号一多就彻底乱了。后来才明白这类题目需要的是一个标准的数据结构方案而不是临场拍脑袋的“我好像能行”。这道题在机试里反复出现是因为它的考察面足够综合同时又能控制在一个合理的代码量范围内非常适合在限时场景里筛人。1.2 表面要求与潜在考察点表面要求是“能算出结果”但潜在考察点至少可以拆成三块每一块都对应一个容易翻车的细节。第一块是字符串处理。你面对的不是现成的整数数组而是一长串字符。数字可能连续出现比如 314 是三个字符拼成的整数空格可能在任意位置出现运算符和括号夹杂其间。你要能从中提取出语义正确的 token 序列。这是词法分析的最基础环节平时没写过相关代码的人很容易在这里卡住。第二块是运算符优先级。同样是“1 2 * 3”先算加法和先算乘法结果是完全不同的。乘除必须优先于加减同级运算符又要按从左到右的顺序执行。这个规则在数学里是约定俗成的但在代码里没有任何隐式机制能帮你自动遵守必须显式地写出来告诉程序。第三块是括号嵌套。括号的作用是改变优先级顺序而嵌套括号意味着你在处理过程中要动态维护一个“当前该先算哪里”的上下文。这里自然会用到栈左括号压栈右括号弹出中间遇到运算符还要根据优先级决定是立刻计算还是等一等。括号匹配一旦处理错轻则结果不对重则死循环甚至段错误。从题型家族来看这道题和逆波兰表达式求值、中缀表达式转后缀表达式是同一大类。你可以把它理解成“栈的经典应用课”吃透这一道后面那些亲戚题基本都能顺带解决。1.3 为什么这种题在机试里反复出现我个人的判断是这道题的区分度设计得非常好。它不依赖某个偏门算法也不需要数学天赋而是考察基础功底和工程细节栈的压入弹出时机、运算符结合性、整数溢出防护、输入读取方式。很多人想到思路是一回事能不能在半小时内写出完全正确的代码又是另一回事。在线笔试系统的编辑器通常没有智能补全也不能像本地 IDE 那样随时打断点一切都得靠脑内模拟。这种情况下平时理解不到位的小细节会被无限放大。比如运算符弹出时机差一个等号就可能导致“10 - 5 - 2”算成 7操作数弹出顺序写反减法就变成了反向减法。正因为如此我强烈建议把这类题做到“肌肉记忆”程度而不是停留在“思路懂了”。下面我会把两条主流实现路线都展开讲你也可以跟着代码一步步验证。2. 核心思路栈是如何解决表达式问题的2.1 从“人算”到“机算”人算表达式的时候会下意识地全局观察。比如看到“1 2 * 3”你会先注意乘号心里先把“2 * 3”算成 6再把 1 加进去。这个过程对人来说很自然但对程序来说从左到右读字符的机器并没有“把目光跳到中间”的能力。所以需要一个数据结构来辅助延迟决策。栈就是一个后进先出的临时存储区。你可以把读到的数字和运算符先“压”进去等到某个条件满足时再“弹”出来计算。这个“压在栈里等一等”的机制完美匹配了表达式求值中“不能立刻决定是否计算”的需求。举个例子你读到“1 2”之后看到了加号但你还不知道后面会不会出现乘号。如果现在就把“1 2”算了等到后面冒出“* 3”时整体优先级就错了。正确做法是先把“”存起来继续往后看确认后面是低优先级运算符或表达式结束时再回头结算。这就像排队时你手里拿着一个号码牌不确定前面的人是不是 VIP先等着再说。2.2 优先级与结合性的规则表达式求值里最核心的规则就是优先级乘除高于加减括号内的内容优先于括号外。实现时通常给每个运算符一个整数表示的优先级加号减号是 1乘号除号是 2。当一个新的运算符出现时要和栈顶已有的运算符比较优先级。如果栈顶优先级更高或相等说明栈顶的运算可以率先结算否则新运算符要入栈等待。这里“更高或相等”的“相等”很关键它保证了同级运算符从左到右结合。想象一下“10 - 5 - 2”如果不处理相等优先级程序可能把后面的“5 - 2”先算结果变成“10 - (5 - 2) 7”而正确答案是“3”。很多人第一次写都栽在这个等号上。括号则是优先级规则的特例。左括号一旦入栈它就形成了一道“屏障”屏障内的运算符不管优先级高低都不能越过它去和外面的运算符比较。只有当右括号到来时这道屏障才解除括号内的所有运算符按优先级依次结算。2.3 两条主流实现路线表达式求值有两条非常经典的路线。一条是“双栈单遍扫描”一个栈存数字一个栈存运算符从左到右遍历一次表达式边读边算。这条路线代码短、速度快是机试现场最推荐的方案。另一条是“中缀转后缀 后缀求值”。先把中缀表达式转换成后缀表达式也叫逆波兰表达式再对后缀表达式做一次简单的栈运算。这条路线多了一层转换但每一步的逻辑都更纯粹遇到“输出后缀表达式”这种衍生题时会很有优势。两条路线的本质是相通的区别只在于“结算时机”。双栈法是在遍历过程中遇到合适条件就立即结算中缀转后缀法是把结算动作全部推迟到后缀求值阶段。我会在核心实现部分优先讲双栈单遍然后在进阶部分完整演示中缀转后缀你看完自然会理解两者的关系。3. 双栈单遍求值的完整实现3.1 代码结构总览直接进入实操。我用 C 写一个完整版本这也是机试平台最通用的语言。整体结构分三部分一个计算函数 apply一个优先级函数 precedence一个主解析函数 calculate。先定义两个栈。操作数栈存数字运算符栈存符号。为什么操作数栈要用 long long因为表达式的中间结果可能因为乘法和括号嵌套而变得很大int 很容易溢出。机试数据虽然不一定会卡这个点但用 long long 几乎无成本没必要省。apply 函数负责具体执行一次二元运算。这是整个程序里最容易出错的函数操作数弹出顺序。栈是后进先出的先弹出的数字实际上是表达式里靠右的操作数后弹出的才是靠左的操作数。也就是说遇到 a - b 时先弹出的是 b再弹出的是 a。如果写反了减法会变成相反数除法也会得到错误结果。这个细节我会在后面的调试部分反复强调。3.2 主循环的四个分支主循环逐个字符扫描表达式对每个字符分四类情况处理。我按代码执行顺序来拆解。第一类是空格。空格没有语义直接跳过。但注意读取方式表达式可能整体带着空格所以不能用 cin s 读入那会在第一个空格处断开。应该用 getline(cin, s) 读取一整行。这个细节能直接决定你一次提交的成败。第二类是数字字符。当遇到数字时不能只取一位要用一个 while 循环把连续的数字字符全部读完拼成一个完整的整数然后压入操作数栈。很多人第一次写只处理了单个字符导致 314 被拆成三个数计算结果自然一塌糊涂。第三类是左右括号。左括号直接压入运算符栈。右括号则触发一段循环不断从运算符栈弹出运算符并用 apply 执行计算直到栈顶遇到左括号为止。弹出完成后再把左括号也弹掉。这个过程本质上是把括号内积压的所有未结算运算一次性做完。第四类是普通运算符也就是加减乘除。这是逻辑最密集的地方。处理规则是只要运算符栈非空且栈顶不是左括号且栈顶运算符的优先级不低于当前运算符就不停地弹出栈顶并计算。循环结束后再把当前运算符压入运算符栈。这个“先结算再入栈”的规则就是优先级控制的核心。再拿“1 2 * 3”演练一遍遇到 时栈为空直接入栈遇到 2 入数字栈遇到 * 时栈顶 的优先级小于所以 不出来直接入栈遇到 3 入栈遍历结束栈里剩下 和 *按顺序弹出计算先 2 * 3 得 6再 1 6 得 7。3.3 边界与异常处理机试输入通常保证是合法表达式但代码还是要尽量健壮至少不能因为正常边界情况而崩。这里有几个必须考虑的点。除零是一个。除法运算前要检查右操作数是否为 0。如果题目没有额外说明遇到除零直接报错或按题目要求处理。不要让它静默通过或触发运行时异常。括号不匹配也是一个。如果读到一个右括号但运算符栈里一直找不到左括号说明输入有问题。如果你的代码在这种场景下会死循环那问题就严重了。防御写法是在 while 循环条件里加上“栈非空”的判断。表达式读完后运算符栈里可能还有残余运算符。这时要循环执行 apply直到运算符栈清空。最终操作数栈顶就是结果。关于负数还有一个实用小技巧。表达式可能以负号开头或者括号后面紧跟负号比如“-3 2”或“(-3) * 4”。最简单优雅的解法是当检测到当前字符是负号且它前面是表达式开头、左括号或其他运算符时先向操作数栈压入一个 0。这样“-3”就变成了“0 - 3”整个表达式逻辑完全一致不需要额外维护一个“当前是否期望操作数”的状态。3.4 完整代码与用例验证我给出一个可直接运行的完整版本你可以复制到本地编译器里验证。#include iostream #include stack #include string #include cctype using namespace std; int precedence(char c) { if (c || c -) return 1; if (c * || c /) return 2; return 0; } void apply(stacklong long nums, stackchar ops) { long long a nums.top(); nums.pop(); long long b nums.top(); nums.pop(); char op ops.top(); ops.pop(); long long res 0; switch (op) { case : res b a; break; case -: res b - a; break; case *: res b * a; break; case /: res b / a; break; } nums.push(res); } long long calculate(const string s) { stacklong long nums; stackchar ops; int i 0; int n s.size(); while (i n) { char c s[i]; if (c ) { i; } else if (isdigit(c)) { long long num 0; while (i n isdigit(s[i])) { num num * 10 (s[i] - 0); i; } nums.push(num); } else if (c () { ops.push(c); i; } else if (c )) { while (!ops.empty() ops.top() ! () { apply(nums, ops); } if (!ops.empty()) ops.pop(); i; } else { if (c - (i 0 || s[i-1] ( || s[i-1] || s[i-1] - || s[i-1] * || s[i-1] /)) { nums.push(0); } while (!ops.empty() ops.top() ! ( precedence(ops.top()) precedence(c)) { apply(nums, ops); } ops.push(c); i; } } while (!ops.empty()) { apply(nums, ops); } return nums.top(); } int main() { string s; getline(cin, s); cout calculate(s) endl; return 0; }拿几个典型用例验证一下输入 “12*3”输出 7。输入 “(12)*3”输出 9。输入 “10-5-2”输出 3。输入 “2*(34)-5/2”输出 12因为 5/2 按整数除法是 2。输入 “-32*4”输出 5。这些用例覆盖了多位数解析、优先级、同级左结合、括号和负号。你的代码能一次性通过它们基本就稳了。4. 中缀转后缀的另一种实现路线4.1 转换规则理解了双栈法之后中缀转后缀会更容易吸收。后缀表达式也叫逆波兰表达式它的核心特点是运算符跟在操作数后面比如“1 2 * 3”写成“1 2 3 * ”。由于运算符顺序已经被调整好后缀表达式求值时完全不需要回看优先级。转换规则可以总结成五句话。第一数字直接输出到结果序列。第二运算符在入栈前先把栈中优先级不低于它的所有运算符弹出并输出。第三左括号直接入栈。第四右括号触发弹出直到遇到左括号左括号本身不输出。第五表达式遍历完后把栈里剩余运算符全部弹出输出。这套规则和双栈单遍法的“先结算再入栈”几乎一样差别只在于双栈法把弹出的运算符立即用于计算而这里只是把弹出的运算符写进结果序列。4.2 转换代码关键片段假设输入表达式中包含多位整数和空格中缀转后缀的核心代码可以这样写string toPostfix(const string s) { string res; stackchar ops; int i 0; while (i s.size()) { char c s[i]; if (c ) { i; } else if (isdigit(c)) { while (i s.size() isdigit(s[i])) { res s[i]; i; } res ; } else if (c () { ops.push(c); i; } else if (c )) { while (!ops.empty() ops.top() ! () { res ops.top(); res ; ops.pop(); } if (!ops.empty()) ops.pop(); i; } else { while (!ops.empty() ops.top() ! ( precedence(ops.top()) precedence(c)) { res ops.top(); res ; ops.pop(); } ops.push(c); i; } } while (!ops.empty()) { res ops.top(); res ; ops.pop(); } return res; }这段代码里我习惯在每输出一个数字或运算符后加空格不是为了好看而是为了后续解析方便。早期调试时我用过不带空格的输出结果得到“123”这种连在一起的字符串还得再费劲拆开。加一个空格后面用字符串流按空白分割会舒服太多。4.3 后缀表达式求值后缀求值的代码比转换简单得多。遍历后缀表达式的每个 token如果是数字就压入数字栈如果是运算符就弹出两个操作数计算结果压回栈。因为后缀表达式已经没有括号也没有优先级问题计算顺序完全由 token 序列本身决定。拿“1 2 3 * ”举例读入 1、2、3遇到乘号弹出 2 和 3 得到 6压回去遇到加号弹出 1 和 6 得到 7。整个过程没有分支判断逻辑非常干净。很多工业级计算器在内部也会先把表达式转成后缀表达式或抽象语法树再统一求值原因就在这里把复杂问题拆成简单阶段。4.4 两条路线怎么选如果要参加机试我建议主攻双栈单遍方案理由很实在代码更短状态更少出错概率更低。中缀转后缀要多维护一个结果序列还要多写一层解析逻辑在限时环境里变数更多。但中缀转后缀的思维不能跳过。一方面它能帮你从原理层面彻底理解栈的作用另一方面机试偶尔会出现“输出后缀表达式”这种直接变体。如果只会双栈法遇到衍生题会比较被动。我的训练顺序是先把双栈法写熟再练习中缀转后缀做到两种路线都能二十分钟内无错写出。在这里额外提一句如果你在本地调试中发现某个表达式在两种方案下结果不一致那通常不是方案的问题而是某个分支判断写错了。把两个方案都实现一遍本身也是一种交叉验证手段。5. 机试实战常见问题与排查技巧5.1 高频错误速查表我整理了一份机试现场最容易翻车的问题列表每一条背后都是实际踩过的坑。症状根因对策结果偏大或出现负数乱码用 int 存中间值溢出操作数栈统一用 long long带空格表达式算错cin s 读入中断改用 getline(cin, s)314 被当成 3、1、4数字解析只取一位while 循环读连续数字10-5-2 结果等于 7优先级比较没用 同级运算必须先结算减法和除法结果错弹出顺序写反先弹右操作数再弹左操作数遇到前导负号就崩负号分支没处理在负数前补 0 再入栈括号不匹配导致死循环右括号循环缺少终止判断循环条件加“栈非空”“弹出顺序”这条怎么强调都不过分。我在帮朋友 review 代码时十个人里至少有五个第一次都写反过。写 apply 时永远记住第一下 top 弹出来的是表达式靠右边的数第二下 top 弹出来的才是靠左边的数。5.2 调试三板斧现场调试不能依赖 IDE所以要练会用“脑内栈模拟”和“输出打印定位”。这里分享三个实打实有效的方法。第一板斧是打印中间状态。在 apply 函数里临时加一行输出把弹出的操作数、运算符和计算结果打印出来。比如算“12*3”时你会看到先打印“2 * 3 6”再打印“1 6 7”整个计算顺序一目了然。如果输出顺序不符合预期说明结算时机有问题。第二板斧是构造最小复现用例。不要一开始就测“(12)*3-4/5”这种长式子。先测“5”这种单个数字再依次叠加特性加号、优先级、括号、负号、连续减法。每加一个特性就跑一次一旦结果出错就能精准定位到刚添加的那个特性对应的代码分支。第三板斧是回归旧用例。每改一次代码都把你前面跑过的所有用例重新跑一遍。机试现场没有时间给你反复回归但平时训练必须养成这个习惯。否则很容易修好 A bug又把 B bug 引出来而你自己完全没察觉。5.3 机试策略细节在线笔试和本地开发是两种完全不同的场景。本地有断点、有变量监视、有无限次重试机试往往只有有限提交次数一次失败就是一次机会的磨损。因此我建议按这个顺序操作先搭框架再写核心逻辑最后专项自测。框架阶段先把 calculate 函数、apply 函数和 main 函数的结构写好确保能编译通过。核心逻辑阶段再补齐分支处理。写完后必须留出至少五分钟构造边界用例自测——不要觉得写完了就万事大吉边界用例往往能暴露最隐蔽的问题。输入输出格式也要提前确认。有的机试题目要求计算多个表达式每个表达式一行每行输出一个结果。这种情况下main 函数应该用 while (getline(cin, s)) 循环处理。如果输入可能包含空行还要在计算前判断 s 是否为空。再说一个我自己坚持的习惯主函数尽量简化只负责读入和输出。计算逻辑全部封装成独立函数。好处很明显自测时可以直接调用 calculate不需要反复走读入流程出了问题也能快速缩小排查范围。如果你在机试里允许使用 Python也可以用更精简的方式实现。思路和 C 完全一致只是语法更简洁def calculate(s: str) - int: nums, ops [], [] i, n 0, len(s) def apply(): a, b nums.pop(), nums.pop() op ops.pop() if op : nums.append(b a) elif op -: nums.append(b - a) elif op *: nums.append(b * a) else: nums.append(int(b / a)) while i n: c s[i] if c : i 1 elif c.isdigit(): num 0 while i n and s[i].isdigit(): num num * 10 int(s[i]) i 1 nums.append(num) elif c (: ops.append(c) i 1 elif c ): while ops and ops[-1] ! (: apply() ops.pop() i 1 else: if c - and (i 0 or s[i-1] ( or s[i-1] in -*/): nums.append(0) while ops and ops[-1] ! ( and (ops[-1] in */ or c in */): apply() ops.append(c) i 1 while ops: apply() return nums[0]注意 Python 整数除法和 C 不一样Python 的 // 是向下取整C 的 / 是向零取整。如果题目要求向零取整这里可以写成 int(b / a)。机试一般不会出负数除法的极端用例但知道这个差异总是好的。5.4 适应机试平台的额外提醒在线笔试系统通常没有自动补全也不能临时查资料。这意味着 stack 的 push、pop、top、empty 这些接口必须烂熟于心。如果连头文件都忘写提交时直接编译失败那是最冤枉的挂法。我见过不少人平时全靠 IDE 补全到了机试环境写不出最基础的栈操作最后只能用数组模拟栈倒是也能跑但明显不够流畅。建议你平时多练“脱稿写代码”直接在记事本里写不依赖任何补全。至少这道计算器题应该做到随时能从头完整写出来。机试的另一个特点是会有很多你没有预料到的输入形式。比如表达式中可能混入制表符而不是空格或者在测试用例末尾意外带了空行。你的解析逻辑应该对这类“噪音”足够宽容适当地跳过不可见字符能省不少麻烦。“最后一个字符”这种细节也很重要。遍历完整个字符串后运算符栈里残留的运算符必须全部结算完才能得到正确结果。千万别忘了循环弹出。我看到过不少版本主循环写得很漂亮但最后少了 while (!ops.empty()) 这一步答案永远差一点排查起来又很难发现。我个人在实际操作中的体会是这道计算器题值得反复练三遍。第一遍用双栈单遍方案第二遍用中缀转后缀方案第三遍尝试处理扩展场景比如自定义空格、前导负号、浮点数甚至幂运算。三遍下来你对栈的理解会明显上一个大台阶。之后遇到“最长有效括号”、“逆波兰表达式求值”这类亲戚题你会发现自己几乎不用思考套路马上就能浮现出来。当初我自己就是从第一次写反除法操作数顺序练到后来十分钟内无错写完整解靠的就是这种重复打磨。