L2-033简单计算器：栈模拟与运算顺序的经典题解

1. 项目概述与题目定位1.1 这道题到底是什么团体程序设计天梯赛的练习集里L2-033“简单计算器”是一道非常经典的栈应用题目。第一次看到这个题名的时候很多人会以为是个输入表达式求值的题目毕竟“计算器”三个字天然让人联想到中缀表达式转后缀、运算符优先级这些麻烦事。但实际上这道题出得很克制它把计算器的核心逻辑简化成了一道纯粹的栈模拟题只考你两件事会不会用栈以及能不能把加减乘除的运算顺序理清楚。题目本身不复杂。输入一共两行第一行给出一个正整数N代表参与运算的数字个数第二行给出N个整数按顺序压入栈中第三行给出N-1个运算符同样按顺序压入另一个栈中。之后你就需要模拟一个计算过程每次从数字栈中弹出两个数字再从运算符栈中弹出一个运算符进行对应的运算把结果压回数字栈。重复这个过程直到数字栈里只剩一个数字那就是最终结果。但这里有一个很重要的限制条件除法运算要求结果必须是整数如果两个数字相除除不尽直接输出ERROR整个程序结束。题目限定N不超过1000数字绝对值不超过1000运算符只有加减乘除四种。数据范围很小暴力模拟完全够用不需要开什么优化。这道题在L2序列里属于比较靠前的题目难度适中很适合用来练习栈的基本操作或者作为团队赛赛前热身的题目。1.2 适合谁来练这道题按照我的经验L2-033适合以下几类人第一类是刚学完栈和队列、想找点题目练手的学生。这道题对栈的基本操作考察非常直接没有复杂的数据结构嵌套只要把push、pop、top这三个操作搞清楚基本就能做出来。第二类是准备参加团体程序设计天梯赛的选手。天梯赛L2阶段的题目通常带有一定的综合性和细节陷阱这道题就是一个典型的“看似简单、实则暗藏杀机”的题目非常适合用来锻炼比赛时的细心程度。第三类是已经工作、但想保持算法手感的人。平时写业务代码写多了栈这种基础数据结构反而容易手生拿这道题热热身十分钟写一遍也不会花太多时间。我自己在带学生训练的时候经常把这道题作为栈专题的入门题目给新手做。原因很简单它的代码量小核心逻辑清晰但坑点一点也不少既能检验基础又能让学生踩几个典型的坑加深印象效率很高。2. 核心算法思路拆解2.1 为什么用栈来模拟计算器如果你之前接触过逆波兰表达式也就是后缀表达式你会发现L2-033的这个操作流程跟你手动计算后缀表达式几乎一模一样从左到右扫描遇到数字就压栈遇到运算符就弹出两个数字做运算结果再压回去。只不过这道题更简单它把数字和运算符都提前分好、按顺序排列好了连扫描解析的步骤都省了直接从“弹出两个数、弹出一个运算符、计算、压回结果”开始。栈这种数据结构天然适合做这个事情因为它能保证运算顺序不会乱。计算器本质上是一个递归的结构一个表达式里可能嵌套着多个子表达式而后进先出的特性恰好匹配这种嵌套关系。你用栈来模拟计算器的时候数字和运算符的顺序是被严格控制的不会出现先算后面的、再算前面的这种错误。实际生活中也是这样你手动算一个复杂的表达式时往往会从最内层的括号开始算一层一层往外退这就是一种天然的栈行为。这道题既然题目名就叫“简单计算器”那必然是考察你用栈来模拟计算的过程。如果你不用栈而是用数组加下标来模拟也不是不行但逻辑上会更绕而且要手动维护指针位置容易出错。相比之下直接用C标准库的stack容器是最自然、最不容易出bug的做法。我自己写题的时候几乎不会在这道题上犹豫数据结构看到“按顺序压入栈中”这几个字直接stack 和stack 就上手。2.2 加减乘除的运算顺序到底怎么定这道题最大的坑点不在栈本身而在运算顺序。题目说的是“每次从数字栈中弹出两个数字”这两个数字谁是N1、谁是N2直接影响减法运算和除法运算的结果。我们手动推演一遍。假设数字栈从栈底到栈顶依次是a、b此时你执行pop操作第一次拿出来的数字是b第二次拿出来的才是a。也就是说先出栈的数字是靠近栈顶的那个后出栈的数字是靠近栈底的那个。题目明确说了N1是后弹出的数字N2是先弹出的数字所以N1 aN2 b运算规则是N1 op N2。对于加法和乘法来说顺序无所谓N1 N2和N2 N1结果一样乘法同理。但减法和除法不一样N1 - N2和N2 - N1可能完全不同除法更是如此甚至除不尽的情况都会因为调换顺序而发生变化。所以在写代码的时候一定要注意这一点先弹出的数要放在运算符右边后弹出的数放在运算符左边。我见过很多学生在这里犯错他们把代码写成num2 - num1结果样例都能过但一提交就WA因为题目给的样例恰好没有暴露出顺序问题。这个细节非常阴必须在写代码的时候就刻进脑子里。2.3 除法的两个坑除零和整除题目里还有一个很容易被忽略的细节除法运算要求结果必须是整数如果除不尽直接输出ERROR。这句话翻译成代码逻辑就是先判断除数是否为0如果是0直接ERROR再判断被除数能否被除数整除也就是取模运算的结果是否为0如果不是0也直接ERROR。很多第一次做这道题的人会漏掉“除不尽”这个条件以为只要除数不为0就万事大吉。结果遇到8除以3这种例子代码算出2.666……如果用整数除法就得到2看起来好像也合理但题目明确要求这种情况下直接输出ERROR而不是做整数除法截断。这里需要额外注意你用来存储除法结果的数据类型也会影响判断。如果用double存2.666不等于2还要额外判断如果用int存8除以3直接截断成2你根本不知道它是不是整除。所以最稳妥的做法是不管最终用什么类型存储判断整除性都用取模运算符%直接用num1 % num2 0来判断。除数为0的情况也容易踩。题目虽然没说数字栈里的元素不能为0但运算过程中可能会出现中间结果为0的情况比如1减1得到0然后下一步如果遇到除法除数就可能是0。这种情况必须输出ERROR别指望数据里不会出现。3. 完整代码实现与分步解析3.1 可直接参考的C实现下面是我惯用的实现方式代码量不大但把该处理的细节都处理好了。#include iostream #include stack #include string using namespace std; int main() { int n; cin n; stackint nums; stackchar ops; for (int i 0; i n; i) { int x; cin x; nums.push(x); } for (int i 0; i n - 1; i) { char op; cin op; ops.push(op); } while (nums.size() 1) { int n2 nums.top(); nums.pop(); int n1 nums.top(); nums.pop(); char op ops.top(); ops.pop(); if (op ) { nums.push(n1 n2); } else if (op -) { nums.push(n1 - n2); } else if (op *) { nums.push(n1 * n2); } else if (op /) { if (n2 0) { cout ERROR: n1 /0 endl; return 0; } if (n1 % n2 ! 0) { cout ERROR: n1 / n2 endl; return 0; } nums.push(n1 / n2); } } cout nums.top() endl; return 0; }我解释几个关键设计决策。第一两个数字弹出的顺序是先n2后n1因为栈是先入后出先弹出的那个是后压入的。写的时候我故意用先取n2再取n1跟开头说的N1、N2对应起来这样后面写n1 - n2、n1 / n2的时候就不容易搞混。第二除法的判断我拆成了两步先判n2是否为0再判n1 % n2是否为0。注意这里的顺序不能反如果n2为0n1 % n2本身就是一个非法的操作直接导致运行时错误或未定义行为所以必须先把除数为0的情况拦下来。第三错误信息的格式。题目要求输入“ERROR: 被除数/除数”的形式比如8除以3除不尽输出是ERROR: 8/3中间没有空格冒号后面有一个空格。这个格式细节看起来小但判题是全字匹配的一旦格式不对就是零分。我自己在比赛时就吃过这种亏所以提醒大家仔细对照题目的样例输出尤其是空格和标点符号。3.2 关键步骤的逐行解读再细一点看这个程序的处理流程。读取部分没什么好说的N个数字按顺序读入后数字栈从栈底到栈顶依次就是输入顺序。运算符栈同理输入顺序是第一个运算符在栈底、最后一个运算符在栈顶。这个过程不需要任何排序或者反转因为出栈的时候自然就是逆序操作正好对应题目描述的计算规则。循环条件是nums.size() 1只要数字栈里还剩超过一个数字就说明运算没有完成。每次循环处理一次运算弹出一个运算符、两个数字然后把结果压回数字栈。最终循环结束时数字栈里只剩一个数字那个就是计算结果直接输出栈顶元素即可。有一个细节是循环结束之后理论上ops栈应该也为空因为最初就是N-1个运算符每轮弹一个一共执行N-1轮后刚好弹完。这里不需要额外判断数字栈size减到1的过程天然保证了运算轮数是N-1如果你强行在循环条件里加上ops.empty()的判断反而画蛇添足还容易出逻辑漏洞。另外我使用了cout ERROR: n1 /0 endl这种写法来构造错误输出。因为除数为0时对应的表达式就是n1/0所以直接拼字符串就行不需要额外处理。除不尽的情况则要输出n1和n2的具体值。这两种情况都和除法运算本身有关分开写比统一放到一个函数里更清晰代码也不会变得冗长。3.3 用样例实际跑一遍用题目自带的样例验证一下逻辑。假设输入5 2 3 8 4 5 * - /数字栈从栈底到栈顶依次为2、3、8、4、5运算符栈从栈底到栈顶依次为*、、-、/。第一轮数字栈弹出一个5作为n2弹出一个4作为n1运算符栈弹出/。计算n1 / n2 4 / 5注意4 % 5 4不等于0除不尽直接输出ERROR: 4/5程序结束。你看这个样例的设计很巧妙第一个运算就是除法而且直接除不尽用来测试你是否正确处理了除法整除条件。如果你在代码里把除不尽的情况忽略掉或者运算顺序写反计算5/4都会得到不同的结果。这样也能验证自己写的是不是真的理解了栈的方向。再看另一个验证案例3 5 4 2 *第一轮弹出n22n14运算符*4*28压回。第二轮弹出n28n15运算符5813输出13。这个例子主要验证的是加减乘除混合运算时结果的累积是否正确中间结果8被压回栈然后作为n2参与后续运算顺序也没有错。4. 竞赛场景下的常见问题与排查技巧4.1 新手最容易犯的几个错误这道题虽然代码量小但我看过的提交记录里错误类型非常集中基本就那几类这里给大家列一下。第一个错误是减法运算顺序写反。上面已经说过栈弹出的第一个数字要放在运算符右边第二个数字放在左边。如果你把代码写成n2 - n1在部分测试数据下会全错。怎么快速自查你可以构造一组两个数字的输入比如数字是10和3运算符是-如果程序输出7说明顺序对输出-7说明写反了。第二个错误是除法的整除判断被忽略。有些提交直接写nums.push(n1 / n2)完全不管除不尽的情况这种代码能过其实属于运气好数据没卡到这个点上。但天梯赛的测试数据从来不会这么善良所以光靠运气是不可靠的除法必须显式判断取模结果。第三个错误是把运算符栈当字符串处理用getline(cin, str)去读一整行的运算符结果中间如果有空格就出错。题目输入运算符时是逐个字符给出的中间可能有空格也可能没有稳妥的做法是用cin op的方式逐个读取cin会自动跳过空白字符不需要手动处理空格问题。第四个错误是漏判除数为0的情况。有些同学只判断了除不尽没判断除数是否为0结果在遇到除数为0时程序直接崩溃输出随机数或者段错误还找不到原因。这一点在写代码的时候就要考虑到不要抱侥幸心理。第五个错误是输出格式出错。ERROR:后面少了一个空格或者多加了一个空格都会被判零分。这种错误看起来蠢但在紧张的比赛环境里非常容易犯建议写完代码后专门盯着输出语句检查一遍。4.2 问题速查表为了方便参考我整理了一个表格覆盖了这道题里可能出现的主要问题。问题现象可能原因排查方式样例通过但提交WA减法或除法顺序写反构造两个数的用例手动验算运行时报错或崩溃除数为0时未做判断在除法分支前检查n2是否等于0除法运算结果错误忽略了整除条件用n1 % n2 ! 0判断后输出ERROR输出格式不对ERROR后缺空格或多了空格对照题目样例输出逐字符比对读取运算符出错用getline读入了空格改用cin op逐个读取字符最终结果不对但错法无规律循环条件写错检查while条件是否用nums.size() 1这张表不是凭空来的是我在带训练营的时候把四十多个学生提交的错误代码集中分析后总结出来的高频问题。可以说覆盖了这道题大约九成的WA和RE原因对照排查基本都能定位到问题。4.3 调试这类题目的通用思路调试这类栈模拟题有一个很实用的方法手动模拟小数据。因为栈的操作过程是确定的你完全可以用纸笔把每一步的stack状态画出来然后和代码执行的结果做对比。具体做法是选择一个N3的用例数字1、2、3运算符和-手动模拟得到结果应该是1 - (2 3) -4。如果你代码输出的不是-4那说明要么运算顺序写错要么压栈过程写错直接在草稿纸上跟踪每一步就能找到问题。另一种调试方式是在代码的关键位置打印中间状态比如每次压栈后打印栈顶元素。比赛时不太建议加太多调试输出但日常练习时这样做能帮你快速确认自己的代码行为是否符合预期。我平时练习时会写一个debug函数把当前数字栈的所有元素按栈底到栈顶顺序打印出来这样能很直观地看到中间结果的变化。还有一种进阶的调试技巧是用random数据做压力测试。虽然这道题N很小但你仍然可以写一个生成随机用例的脚本输出一个正确答案再和你的代码输出比对用来验证边界情况。虽然这道题暂时用不上这种重型手段但这个思路对处理更复杂的栈题非常有用值得练手的时候养成习惯。5. 从L2-033延伸到更广的竞赛场景5.1 天梯赛赛制里的做题策略团体程序设计天梯赛的赛制是三个人组队在限定时间内共同完成尽可能多的题目积分规则是看整体完成度。L2级别的题目通常分布在比赛的中段它们的难度介于基础题和复杂题之间是队伍拉开分数的关键区域。这种赛制下L2-033这种题目其实是性价比很高的题。它代码量小不算难题花十分钟快速搞定就能稳定拿到一部分积分。我在实际的团队训练里一直给学生强调一个原则比赛开始后先把所有题目都扫一遍挑出像L2-033这样“看起来就能做”的题目优先解决不要在一道题上死磕太久。天梯赛的积分规则决定了你多解出一道简单题比在一道难题上多花一小时更有价值。另外L2-033这种栈模拟题放在实战中也有一个作用它可以作为热身题帮助队伍在比赛初期进入状态。当你的手感和思维还没有完全热起来的时候做一道结构清晰、不含糊的模拟题能帮整个队伍建立信心和节奏。如果一上来就做复杂题很容易卡住反而影响士气。5.2 同类型题目的延伸练习如果你觉得L2-033做得不过瘾想继续加深对栈的理解我非常推荐接下来练习下面几类题目。第一类是表达式求值题也就是给你一个完整的中缀表达式需要处理括号、运算符优先级和多位整数的情况。这类题是L2-033的升级版你不仅要会压栈弹栈还要会处理优先级通常需要两个栈一个存数字、一个存运算符并在遇到右括号或低优先级运算符时触发计算。第二类是后缀表达式求值题如果L2-033你完全掌握了后缀表达式求值其实跟它非常像只是数字和运算符混在同一个序列里不再分成两个独立的栈你需要自己判断当前读入的是数字还是运算符。第三类是涉及栈的DFS/BFS题比如模拟迷宫、括号匹配、单调栈找下一个更大元素等。这些题目会让你对栈的理解从“模拟计算”上升到“利用栈解决更抽象的问题”。特别是单调栈它在实际算法题里出现频率非常高用好了能解决很多看似复杂的题目。我的建议是做完L2-033之后不要急着刷更多模拟题而是去看一看中缀表达式转后缀表达式的经典算法。你把那个算法搞懂了再回头看L2-033会感觉很简单因为你的思维层次已经从“按题意模拟”上升到“理解为什么用栈来模拟计算”了。5.3 关于这道题的一个延伸思考有一个细节值得深入想一下为什么题目要求除法除不尽就输出ERROR而不是像普通计算器那样保留小数或者四舍五入我的理解是这道题既然叫“简单计算器”它模拟的是一个只做整数运算的计算器。比赛中经常有这种设定目的是考察你处理边界情况的能力——除数为0算一种、除不尽算一种都是常见的算术陷阱。选手只有在写代码时把各种可能性都考虑到才能保证程序的鲁棒性。这其实也是竞赛题目和业务代码的共同点数据是不可能友好的程序中每一个分支都需要你自己去兜底。如果你有兴趣可以想想如果允许结果是非整数这道题应该怎么做。最简单的做法是用double类型存储所有数字除法直接做浮点除法最终结果也以浮点形式输出。但这会引入浮点误差的问题比如0.1 0.2不等于0.3这种经典坑你还要额外设置误差范围。这样一对比你就会发现题目限定整数运算其实是在帮你避开浮点数这个大坑出题人考虑得还是蛮周全的。6. 给初学者的实操建议与复盘思路6.1 从零开始刷这道题的推荐流程如果你以前没怎么写过栈相关的题目建议按照下面这几步来推进而不是一上来就看题解。第一步自己独立读题三遍并把题目里的关键信息用笔画出来。“按顺序压入栈中”这八个字值得你圈起来看三遍“先弹出的数字是N2”这种描述也要重点关注因为这两个描述决定了代码里弹出的顺序。第二步不看任何参考代码先动手写一版。哪怕写得不对也要先写出来因为只有亲手写了一遍踩过的坑才会记得牢。写完以后拿题目给的样例去试能过就继续尝试自己构造几个用例来测试。第三步如果卡住了再去看题解但不要只看代码要看思路。看题解里为什么这样定义N1和N2为什么除法要判断两次。弄懂思路以后合上题解自己再写一遍。这个“复写”的过程非常重要我能保证这样做一次比你看十遍题解都有效。第四步把这道题总结到你的错题本里。重点记录三个内容一是栈弹出的顺序问题二是除法的整除判断三是错误输出格式的细节。过两周再回头把这道题重写一遍看自己能不能一次通过如果能写对说明你真的掌握了。6.2 写题时养成的好习惯通过L2-033这道题我想顺带分享几个平时写竞赛题时就该养成的好习惯。第一个习惯是定义变量名的时候要能看出含义。像n1、n2这种名字在题目已经给出了明确定义的情况下直接沿用题目说法是很好的做法这样写代码时不容易混淆。相反如果你随手写a、b写到最后自己都不知道哪个先弹出的。第二个习惯是每个分支写完后心里要过一遍这个分支可能会出错的地方。比如写完除法的分支后就追问自己“如果n2是0会怎样”“如果n1和n2不能整除会怎样”。这种自我提问的习惯在竞赛中能让你回避很多隐藏的WA点。第三个习惯是写完代码后先检查输出语句再检查边界条件最后才检查算法思路。因为输出格式错误和边界条件错误是最好发现也最可惜的错误先排除它们能节省大量调试时间。第四个习惯是如果你时间充裕可以在提交之前给代码加上几个临时测试用例手动验算一遍。虽然天梯赛的正式比赛不提供本地调试的便利但日常练习中你完全可以编译后多跑几组数据确认无误再提交这样能显著提高AC率。养成这些习惯以后你会发现不仅是做算法题连写业务代码的时候思考问题的思路都会变得更严谨排查bug的效率也会提高不少。6.3 从一道题到一类题的心法L2-033是一道非常典型的“题小但坑多”的题目它教会我们的核心能力不是栈本身而是“按题目要求精确执行”的能力。比赛里很多题目并不需要多么高深的算法但要求你把过程拆解得一丝不苟把各种边界情况都想到。这种能力不是天生的是大量做题、大量踩坑、大量复盘之后慢慢养成的。我一直觉得算法竞赛训练到最后比的不是谁知道更多高深的算法而是谁在限制条件下犯错更少。L2-033就是这样一个用来训练“少犯错”的完美素材它结构简单所以你不会因为算法太难而分心可以全身心放在细节处理上。如果你想在算法这条路上走得更远我建议你记住这道题带给你的感觉很多WA并不是因为“不会做”而是因为“没想全”。当你以后遇到任何一道题都习惯性地在动手写之前先问自己“这个题的边界条件有哪些”“哪一步的顺序最容易被搞反”你的实力一定会有质的提升。L2-033虽然简单但我每带一届新人都会让他们认真对待这道题因为它值得被当作一道标杆题目来学习。