PTA的习题6-7《简单计算器》我前前后后给不少同学讲了好多遍。这道题看起来只要做个加减乘除实际上它是把“运算符优先级”这个C语言初学阶段最容易被忽略的概念藏在一个非常朴素的题目描述里。题目通常长这样输入一个不含括号的四则混合运算表达式只包含正整数、、-、*、/和结尾的等号例如12*3-4/5要求你算出结果并输出。除法是整除不涉及小数也不需要保留余数。它不考什么高深算法却能把“从左到右算”和“先乘除后加减”这两件事的差距放得很大。这篇文章就围绕这个题讲清楚两种主流写法一种是适合刚学数组的两轮扫描法一种是适合进阶的运算符栈方法。同时把我在PTA上摔过的跟头都交代一遍包括多位数解析、等号处理、换行符这种坑。无论你是刚学到循环和数组还是已经在准备天梯赛这类带表达式的题目这篇都能给你一点实在的东西。1. 题目到底在考什么1.1 一道不像表面那么简单的“简单计算器”我第一次见这题的时候第一反应是这不就是scanf一个数读一个运算符再读一个数循环到等号结束后来仔细一看才发现自己把问题想简单了。题目里的“简单”不是说只有一次运算而是说没有括号、没有空格、没有小数、没有负数。操作数是正整数而且可能是多位数比如325*64-34/2这种。表达式以结尾输出一个整数。如果你只处理一位数字或者只处理“数 运算符 数”的格式样例能过换一组数据就崩。另外有一点容易被忽略表达式虽然不含括号但运算符有优先级。*和/要先算和-后算同级别还要从左往右。这就是整道题真正的门槛。不是说你知道“先乘除后加减”就行而是你要在代码里想出一个机制让计算机按照这个顺序去执行。1.2 真正的考点是优先级的实现很多同学能写出从左到右扫一遍的代码但算12*3-4/5的时候就露馅了。因为从左到右扫程序默认每个运算符都是平等的和*没有区别。可实际上2*3必须抢在12之前算。这里有两个理解优先级的关键点乘除的优先级高于加减。也就是说看到*或/时不能急着执行它前面的加减。同级别运算是左结合的。比如8-32要先算8-3再算加2结果是7。如果先从右边算就会变成8-(32)3完全不对。代码里要处理这种“当前运算符不一定马上算”的情况就需要有个地方把暂时不能算的运算符或数字存起来。这就是后面两套解法的共同出发点。2. 为什么直接按顺序算必错2.1 一个反例演示拿一个最简单的混合表达式来看12*3-4/5理解题目顺序后乘除先算2*3 64/5 0整除表达式变成16-0结果7如果直接从左到右算12 33*3 99-4 55/5 1最终得到1。一个1一个7差得离谱。这个例子足以说明计算器题的核心不是“读入和输出”而是什么时候执行运算符。我见过有同学用下面这种思路写代码int result, num; char op; scanf(%d, result); while (1) { scanf(%c, op); if (op ) break; scanf(%d, num); if (op ) result num; else if (op -) result - num; else if (op *) result * num; else if (op /) result / num; } printf(%d\n, result);这段代码遇到12*3-4/5就会得到1而且还会因为读入换行符的问题出现一些小毛病。它的问题就在于没有优先级概念所有运算符一律立即结算。这也是我建议每个初学者先亲手跑一遍错误代码的原因——只有看到错误输出才明白这道题在考什么。2.2 优先级规则怎么落到代码里优先级规则本身不需要背表格只要记住两条*和/是一档和-是一档前者高于后者。同一档里先出现的先算。但落到代码里你需要一个函数来判断“一个运算符是不是比另一个运算符更优先”。我可以这样写int priority(char ch) { if (ch * || ch /) return 2; if (ch || ch -) return 1; return 0; }返回的数字越大优先级越高。后面两套解法都会用到这个函数。先把这个基础打好接下来讲怎么写能AC的完整代码。3. 解法一两轮扫描法适合刚学数组的同学3.1 把表达式拆成两排数组先想一件事表达式其实是有规律的它一定是“数字 运算符 数字 运算符 数字……”。如果把所有数字和所有运算符分别拆出来放在两个数组里会非常规整。比如12*3-4/5数字数组nums [1, 2, 3, 4, 5]运算符数组ops [, *, -, /]数字的个数永远比运算符多一个。这一步没有任何难点主要是解析多位数的时候要注意遇到数字字符就一直累加直到遇到非数字字符为止。char expr[1000]; scanf(%s, expr); int nums[1000], ops[1000]; int numCnt 0, opCnt 0; int i 0; while (expr[i] ! ) { int num 0; while (expr[i] 0 expr[i] 9) { num num * 10 (expr[i] - 0); i; } nums[numCnt] num; if (expr[i] ) break; ops[opCnt] expr[i]; i; }这里为什么用scanf(%s, expr)因为题目给出的表达式没有空格直接读一个字符串最省事。如果用getchar()一个字符一个字符地读多位数和末尾等号会容易出问题这个坑我后面专门讲。3.2 第一轮先把乘除全部消化掉拆成数组之后第一轮只处理*和/。思路是从左到右扫描运算符数组遇到乘除就把它左右两个数字计算一下结果覆盖到左边的数字上然后把数组压缩掉一格。压缩是什么意思举个例子。原来nums [1, 2, 3, 4, 5]对应 5 个数字ops [, *, -, /]对应 4 个运算符。现在要算第一个乘号2*3先算nums[1] 2*3 6这时原来nums[2]里的3没用了把后面的数往前挪一格得到nums [1, 6, 4, 5]同时运算符数组里那个*也没用了把后面的运算符往前挪一格得到ops [, -, /]这样数字数组变成 4 个运算符数组变成 3 个依然保持“数字比运算符多一个”的规律。继续扫描遇到/就算4/5结果覆盖到左边再次压缩。最终第一轮结束后nums [1, 6, 0]ops [, -]第一轮的完整代码长这样for (i 0; i opCnt; ) { if (ops[i] * || ops[i] /) { int a nums[i]; int b nums[i 1]; nums[i] (ops[i] *) ? a * b : a / b; // 删除 nums[i1]后面整体前移 for (int j i 1; j numCnt - 1; j) { nums[j] nums[j 1]; } numCnt--; // 删除 ops[i]后面整体前移 for (int j i; j opCnt - 1; j) { ops[j] ops[j 1]; } opCnt--; } else { i; } }这里最容易被问住的一个点是为什么i不随手i因为压缩之后当前位置会出现一个新的运算符而这个新运算符可能还是乘除。比如2*3*4处理完第一个*之后原来的第二个*会挪到当前位置必须再检查一次才能保证把连续的乘除全部算完。3.3 第二轮只剩加减从左到右算第一轮结束后运算符数组里只剩和-。这时候就没有优先级问题了因为加减同级直接从左到右合并即可。比如上面例子里的nums [1, 6, 0]ops [, -]先算16得到7压缩后nums [7, 0]ops [-]再算7-0得到7压缩后nums [7]第二轮代码和第一轮思路一样只是不再需要判断运算符种类因为能留下来的只有加减while (opCnt 0) { int a nums[0]; int b nums[1]; nums[0] (ops[0] ) ? a b : a - b; for (int j 1; j numCnt - 1; j) { nums[j] nums[j 1]; } numCnt--; for (int j 0; j opCnt - 1; j) { ops[j] ops[j 1]; } opCnt--; } printf(%d\n, nums[0]);这个解法不需要栈不需要递归只需要数组和循环。你对“数组前移”这件事越熟练写起来越顺手。我当年第一次写出完整代码之后自己手动模拟了好几组数据每次都对得上才放心去提交。3.4 完整可提交代码把上面几段拼起来就是一整份可以提交的代码#include stdio.h #include string.h int main() { char expr[1000]; int nums[1000]; char ops[1000]; int numCnt 0, opCnt 0; scanf(%s, expr); int i 0; while (expr[i] ! ) { int num 0; while (expr[i] 0 expr[i] 9) { num num * 10 (expr[i] - 0); i; } nums[numCnt] num; if (expr[i] ) break; ops[opCnt] expr[i]; i; } // 第一轮优先处理乘除 for (i 0; i opCnt; ) { if (ops[i] * || ops[i] /) { int a nums[i]; int b nums[i 1]; nums[i] (ops[i] *) ? a * b : a / b; for (int j i 1; j numCnt - 1; j) { nums[j] nums[j 1]; } numCnt--; for (int j i; j opCnt - 1; j) { ops[j] ops[j 1]; } opCnt--; } else { i; } } // 第二轮处理加减 while (opCnt 0) { int a nums[0]; int b nums[1]; nums[0] (ops[0] ) ? a b : a - b; for (int j 1; j numCnt - 1; j) { nums[j] nums[j 1]; } numCnt--; for (int j 0; j opCnt - 1; j) { ops[j] ops[j 1]; } opCnt--; } printf(%d\n, nums[0]); return 0; }这个代码在PTA上是可以直接交的。测试时你就用12*3-4/5这个输入应该得到7。4. 解法二运算符栈一次扫描搞定4.1 两个栈各管什么事如果你已经学过了栈或者想提前为天梯赛这类题目打基础我推荐第二种解法用两个栈一个数字栈一个运算符栈。思路很直观。数字栈存“已经读进来但暂时不参与运算的数”运算符栈存“优先级还没轮到暂时不能执行的运算符”。每读到一个新运算符就看看栈顶那个运算符是不是比它更着急执行。如果栈顶运算符的优先级大于等于新运算符那就先把栈顶的运算符执行掉再继续比较。这个过程反复进行直到新运算符能顺利进栈。用生活化的说法就是高优先级的运算符来了之后低优先级的运算符要往后排队不能挡路。至于为什么是“大于等于”而不是“大于”原因在前面讲过同级别运算符要左结合先出现的先算。比如8-32读到时栈顶是-优先级一样。如果用判断-不会先算后面就会乱套。只有用才能让同级的左边先算掉。4.2 完整可提交的代码#include stdio.h #include string.h int priority(char ch) { if (ch * || ch /) return 2; if (ch || ch -) return 1; return 0; } int calculate(int a, int b, char op) { if (op ) return a b; if (op -) return a - b; if (op *) return a * b; return a / b; } int main() { char expr[1000]; int numStack[1000]; int numTop 0; char opStack[1000]; int opTop 0; scanf(%s, expr); int i 0; while (expr[i] ! ) { if (expr[i] 0 expr[i] 9) { int num 0; while (expr[i] 0 expr[i] 9) { num num * 10 (expr[i] - 0); i; } numStack[numTop] num; continue; } // 表达式里没有括号剩下的字符一定是运算符 char op expr[i]; // 优先级比新运算符高的先算掉 while (opTop 0 priority(opStack[opTop - 1]) priority(op)) { int b numStack[--numTop]; int a numStack[--numTop]; numStack[numTop] calculate(a, b, opStack[--opTop]); } opStack[opTop] op; } // 表达式读完运算符栈里剩下的全部计算掉 while (opTop 0) { int b numStack[--numTop]; int a numStack[--numTop]; numStack[numTop] calculate(a, b, opStack[--opTop]); } printf(%d\n, numStack[0]); return 0; }这个代码和两轮扫描法相比最大的优势是只扫描一遍式子不需要反复压缩数组。我有一个学生学到这里第一反应是“这两行优先级比较的循环看着头晕”后来我让他用12*3-4/5手动模拟一遍模拟完就通了。模拟是理解栈最好的方式。4.3 两种解法怎么选我把两种方案的适用情况整理成一个对照表对比项两轮扫描法双栈法核心思路先拆数组再按优先级分两轮处理边读边算用运算符栈控制执行时机代码理解难度中等压缩数组需要一点空间想象力初期略难需要理解栈的“暂存”概念代码量偏长中等可扩展性加括号要大改较麻烦加括号只需要补一小段逻辑适合人群刚学数组对栈不熟已经学过栈或想为后续刷题打基础我的建议是如果你现在正处于刚学数组的阶段老老实实用两轮扫描法它能AC且帮你巩固数组操作如果你已经学过数据结构里的栈直接用双栈法后面遇到各种带括号的表达式你会感谢这个选择。5. 我在PTA上摔过的坑5.1 用getchar读入时容易把下一个字符吃掉很多同学写这题的时候喜欢一个字符一个字符地读char ch; while ((ch getchar()) ! ) { // 处理 }这个写法本身没错但解析多位数时很容易出问题。比如读数字34你通常会写一个内层循环int num 0; while (ch 0 ch 9) { num num * 10 (ch - 0); ch getchar(); // 这里已经把下一个运算符读进来了 }问题就出在这里内层循环退出时ch已经保存了数字后面的那个运算符但是外层循环不知道这件事。如果你在外层循环里又执行一次ch getchar()就会把真正的运算符跳过读到一个错位字符。这个bug调试起来真的很烦。我的建议是别挑战自己直接用scanf(%s, expr)把整个表达式读成一个字符串然后用数组下标i来处理。下标比字符流的“已读入状态”好控制得多。5.2 数组开太小导致越界有些同学看到题目说“简单计算器”就以为表达式很短随手开char expr[10]或者int nums[10]。PTA的测试数据有时候挺不讲情面的表达式可能比你想象的长不少。栈也好数组也好开大一点没坏处我习惯开1000。另外要注意用scanf(%s)读字符串时数组末尾会自动补一个\0。如果表达式特别长而数组开小了scanf会直接写出界程序可能在本地跑得好好的一到PTA就异常退出。这种问题最不好排查不如一开始就把数组开大。5.3 整除和负数的理解题目说“除法为整除”意思是4/5的结果是0不是0.8。C语言的整数除法对于正数就是向下截断对于负数则是向零取整。不过这道题操作数都是正整数中间过程因为减法会产生负数比如1-5这种但除数本身不会为负因为负号不会出现在运算符后面单独修饰一个数的位置。还有一点如果a/b里b是0程序会崩溃。题目保证不会出现除数为0的情况但你如果自己造测试数据别拿5/0去试。5.4 输出格式别忽略换行PTA判题对输出格式很严格。printf(%d\n, nums[0])末尾那个\n最好写上。有些同学本地运行没加换行也能看到结果但OJ评测的时候可能就报“格式错误”。这种错误不涉及算法纯粹是细节丢了分很不划算。6. 举一反三后面那些计算器变体6.1 带括号的表达式怎么处理如果你以后遇到带括号的四则运算比如(12)*3双栈法只需要加一点点逻辑遇到左括号(直接压入运算符栈。遇到右括号)不断弹出运算符进行计算直到栈顶是左括号然后把左括号弹出。普通运算符压栈时只要栈顶不是左括号就继续用优先级比较的规则。核心代码片段是这样if (ch () { opStack[opTop] ch; } else if (ch )) { while (opTop 0 opStack[opTop - 1] ! () { // 弹出运算符计算 } opTop--; // 丢掉左括号 } else { while (opTop 0 opStack[opTop - 1] ! ( priority(opStack[opTop - 1]) priority(ch)) { // 弹出运算符计算 } opStack[opTop] ch; }左括号本质上是一个“挡板”它把左边还没算完的运算暂时隔离起来直到右括号出现才放行。这就是括号优先级的代码体现。如果当初用两轮扫描法遇到括号就得大幅度重写这也是为什么我更推荐大家掌握双栈法。6.2 天梯赛和后续刷题会用到什么有热词是“PTA天梯赛L2”如果你后面准备去打天梯赛会发现很多题本质上就是各种表达式的处理比如中缀表达式转后缀表达式、后缀表达式求值等等。它们和这个习题6-7用的是同一套思路数字栈加运算符栈优先级比较左结合规则。换句话说这道“简单计算器”其实是未来那些看起来高大上的题的底层原型。我见过不少同学大一这个题用临时变量硬混过去到了学数据结构的时候又要重新理解表达式求值反而更痛苦。所以我的建议是现在多花半小时把这题搞明白后面能省下好几个半小时。6.3 个人经验总结最后说一点我实际操作中的体会。这个题我至少写过四遍第一遍用两个数组硬拆第二遍用双栈第三遍为了给同学讲题写了带括号版本第四遍是复习时用C语言重写。每一次重写都有新的理解尤其是“为什么压制栈时要优先处理栈顶”这个点写多了之后表达式求值在你眼里就不再是一个算法问题而是“怎么让运算符按规则排队结算”的问题。如果你现在卡在某个样例过不去别急着反复提交。拿笔在纸上画一遍数字栈和运算符栈的变化过程多半就能看出来问题。这道题真的不难但它值得你认真走一遍过程而不是从网上复制一份代码交差。PTA的坑踩过一次就记住了。希望这篇东西能让你少踩几个。