1. 先把题目扒干净这道题在考什么表达式求值这四个字听起来平平无奇但把范围收窄到只有加法和乘法、没有括号、数字最大到 2^31-1、结果只取后四位之后这道题的考察点就变得非常明确了——它不是考你会不会写一个通用解析器而是考你能不能识别出运算符优先级的结构性以及有没有意识到取模运算在什么条件下可以提前做。我第一次拿到这道题的时候第一反应是上双栈写完一百多行看了别人的题解才发现自己被表达式求值这四个字带偏了题目给的限制条件太强了强到足以把问题降维成一次线性扫描。先说清楚这道题的基本面。输入只有一行字符字符集被严格限定在0-9、、*这十二种没有空格、没有括号、没有减号除法号参与运算的数字都是 0 到 2^31-1 之间的整数字符串长度上限十万。输出要求是如果答案超过四位只输出最后四位且前导零不输出。也就是说结果本质上是对 10000 取模但你不能自作聪明地把4打印成0004这一点坑过不少人。题目给的样例很有信息量值得逐个拆开看。第一个样例11*34输出8这个例子专门用来验证你是不是真的处理了乘法优先级——如果从左往右无脑算你会得到((11)*3)4 10错得很明显。第二个样例11234567890*1输出7891这个例子在考数字本身就要取模1234567890 对 10000 取模是 7890加一得 7891。第三个样例11000000003*1输出4同理1000000003 取模是 3加一得 4。后两个样例的用意非常直白它们在提醒你取模这件事不是等到最后一步才做而是要贯穿整个过程。提示这三个样例其实是一套完整的引导。第一题引导你处理优先级第二、三题引导你处理溢出。很多人只看第一个样例就开始写写完发现在大数据点上错得莫名其妙就是漏掉了后面两个样例想告诉你的信息。适合看这篇内容的人群我觉得可以分三类。第一类是刚开始刷题的初学者正在啃栈和字符串处理这类题目是最合适的练手材料因为它足够简单但又不至于毫无思维含量。第二类是有一定基础、但每次遇到取模就心里发虚的人这道题可以帮你把什么时候能取模、什么时候不能这个念头彻底想清楚。第三类是想把表达式求值当成一个通用工具沉淀下来的人这道题的简化版本可以作为一个很好的起点往后加括号、加减法、加函数调用一路能扩展到能写进项目里的公式引擎。三种人读同一篇文章重点会不一样我会尽量把这三种视角都覆盖到。2. 思路拆解为什么分段求积再求和是正解2.1 运算优先级的本质是表达式可以被切块想通这道题的关键是把优先级这个词翻译成一个具体的结构。加法和乘法混在一起乘法的结合力更强所以一个只有和*的表达式天然可以被切成若干段每一段内部只有乘法段与段之间只有加法。比如ab*c*de*f切开就是[a]、[b*c*d]、[e*f]三段每段算出一个乘积最后把所有乘积加起来。这个观察一旦成立整个问题就变成了顺序扫描字符串、维护一个当前乘积、遇到加号就把乘积结算掉的线性流程栈都不需要。我更愿意把这种解法叫做延迟结算。你手上永远有两个累加器一个存已经确定下来的和一个存当前还在长的乘积。读到数字就往乘积里乘读到乘号什么也不做因为后面还会继续乘读到加号就把当前乘积结算进和里然后把乘积重置回 1。这个模型的好处是它完全符合人的直觉——你在纸上算2*34*5的时候也是先算 6 和 20再相加没有人会真的先去算34。对比一下双栈方案你就能看出线性扫描的优势在哪里。双栈一个数字栈、一个符号栈是通用表达式求值的标准做法它的正确性毋庸置疑扩展到带括号、带减法除法、带一元负号都没问题。但它的代价是需要额外的空间需要维护运算符优先级表需要在读到末尾时把栈清空代码量至少翻三倍出错点也成倍增加。在这道题的限制条件下双栈属于典型的用牛刀杀鸡。方案时间复杂度空间复杂度代码量扩展性本题适用性线性扫描 延迟结算O(n)O(1)约 20 行差仅限无括号加减乘最优双栈 优先级表O(n)O(n)约 80 行好可扩展括号与四则能用但浪费递归下降O(n)O(递归深度)约 60 行很好语法结构清晰能用但浪费按切分 内部按*切分O(n)O(n)约 8 行差适合验证不适合正式提交我个人的习惯是比赛里遇到这种限制明确的题先写最快的线性扫描如果时间充裕再补一个切分版本用来对拍。两个独立实现的答案一致心里才踏实。2.2 边算边取模到底安不安全这是这道题最容易让人犹豫的地方。很多人心里有个模糊的印象取模会丢信息不能随便提前做。这个印象在减法、除法、比较大小这些场景下是对的但在本题里完全不成立。原因很简单加法和乘法对取模是同态的。用式子写出来就是(a b) mod m ((a mod m) (b mod m)) mod m以及(a * b) mod m ((a mod m) * (b mod m)) mod m。这两条性质不是近似是恒等。所以你在任意时刻把任意参与运算的数替换成它模 10000 的余数最终结果模 10000 的余数都不会变。本题只涉及加法和乘法没有任何一条运算会破坏这个性质取模可以放心地、随时随地地做。反过来说如果不提前取模会发生什么表达式长度十万假设全是2*2*2*...那结果就是 2 的十万次方这个数有大约三万个十进制位。C 里没有任何内置类型能装下long long在第 63 次乘二的时候就溢出了。所以不是因为取模更好而是因为不取模根本算不出来。这一点必须想明白否则你会觉得取模是一种偷懒的技巧而不是一种必要的正确性保障。那数字本身需不需要取模严格来说题目给的单个数最大 2147483647只有十位用long long存绰绰有余不取模也不会溢出。但我在实现里还是习惯性地给数字累加的那一步加上取模理由是一旦养成这个习惯遇到数字位数更长的变种题比如一千位的整数时不用改代码而且加上取模之后参与乘法的两个因子都严格小于 10000乘积小于 10^8连int都不会溢出内存和寄存器的压力都小。这点微小的一致性收益我觉得值。注意这套随便取模的结论只在不含减法和除法的前提下成立。一旦题目加入减号中间结果取模后可能出现负数必须用((x % m) m) % m修正一旦加入除法取模环境下的除法需要求逆元只有在模数为质数且除数不被整除时才好办。所以这道题的经验不能无脑迁移到四则运算版本这是两回事。2.3 那些看起来聪明其实会翻车的写法我先说说最容易踩的一个坑直接eval。由于输入字符串恰好是一个合法的 Python 表达式很多人会想一行print(eval(input()) % 10000)不就完了。这个写法在小数据上确实能过但它有三个致命问题。第一长度到十万级的表达式CPython 在构建抽象语法树时会因为嵌套过深直接抛出递归相关的异常程序崩溃第二这道题本身考察的就是解析能力用内建求值等于交白卷即便通过了也没有任何训练价值第三很多评测环境对这类动态求值是有限制的。所以我从来不用也不建议任何人用哪怕只是用来快速验证一下样例。第二个坑是把取模放在最后。前面已经算过十万个乘号连起来结果是个天文数字。有些人在 Python 里试了一下发现竟然能算出来这是因为 Python 的整数是任意精度的但那已经慢到无法接受而且换到 C 就直接溢出。所以先算完再取模这条路在 C 里是死路在 Python 里是慢路两头都不通。第三个坑是关于前导零的。题目说当答案长度多于 4 位时请只输出最后 4 位前导 0 不输出。这句话的意思是如果结果是 4就输出4不要输出0004如果结果是 0就输出0。有些实现习惯性地用printf(%04d)补齐四位这在第二个样例上就会输出7891碰巧对但在答案是 4 的时候输出0004直接错。取模本身天然就满足不输出前导零的要求所以只要老老实实用%d打印就行不要画蛇添足。3. 核心实现状态机、代码与逐行验证3.1 把扫描过程画成一个两状态机器在写代码之前我习惯先把扫描逻辑在脑子里建模。这道题的扫描器其实只有两个累积变量和一个数字缓冲ans已完成加法项的和初值 0。term当前乘法链的乘积初值 1很重要乘法的幺元是 1不是 0。num正在读取的数字初值 0。每读到一个字符走三条分支之一。读到数字就num num * 10 (c - 0)同时取模。读到乘号就把num并进term即term term * num % MOD然后把num清零ans不动。读到加号同样先term term * num % MOD、num清零然后把term结算进ans最后把term重置为 1。整个扫描结束后别忘记还有一个num没被并进去要手动补一次同样的结算。关键在于理解乘号什么都不做这一点。很多人第一次写的时候读到乘号也去做结算结果就变成了从左到右依次相乘相加的错误逻辑。实际上乘号的作用是宣告下一个数字属于当前这条乘法链它是连接符不是分隔符。真正起分隔作用的是加号因为加号的优先级低它标志着上一条乘法链的终止。这里有个初值的细节值得单独提一句。term必须初始化为 1因为它的语义是当前乘法链的累积值在还没读到任何数字之前累积值应该是乘法的单位元。如果你图省事初始化为 0那么第一次term * num永远是 0从第一个数开始就全错了而且错得很隐蔽——如果表达式恰好以 0 开头你还看不出来。3.2 C 版本与逐段说明#include cstdio const int MOD 10000; int main() { long long ans 0; // 已完成加法项的累加和 long long term 1; // 当前乘法链的累积乘积 long long num 0; // 正在读取的数字 int c; while ((c getchar()) ! EOF c ! \n) { if (c 0 c 9) { num (num * 10 (c - 0)) % MOD; } else { // 遇到运算符先把数字并进当前乘法链 term term * num % MOD; num 0; if (c ) { ans (ans term) % MOD; term 1; // 开启新的一条乘法链 } // 若是 *term 继续累积不做任何额外动作 } } // 收尾最后一个数字还没有被并入 term term * num % MOD; ans (ans term) % MOD; printf(%lld\n, ans); return 0; }读入方式我用的是getchar()逐字符读取。这个选择的原因是输入只有一行、没有空格cin s或者scanf(%s, buf)都能正常工作但逐字符读有利于在一开始就把num取模这件事融进流程里而且天然不受字符串缓冲区大小的影响。如果表达式长度上限被改到一千万用getchar的版本连字符数组都不用开空间是 O(1) 的。while的循环条件写的是c ! EOF c ! \n这里两个条件都要保留。只写! EOF的话如果输入的末尾有换行符换行会被当作运算符进入else分支虽然因为不是所以只做了一次多余的term * num计算但num此时已经是 0乘出来还是 0恰好不影响结果。不过这属于侥幸正确不是逻辑正确我宁愿把条件写全。至于行尾可能存在的\rWindows 风格换行它同样会落入else分支行为跟换行一样也不会出错属于可以接受的小瑕疵。num里面存的是已经取过模的数字。这一步会不会破坏正确性前面已经论证过数字只参与乘法和加法取模是同态的所以安全。term * num的两个因子都小于 10000乘积最多八位数long long完全扛得住用int其实也够但保持long long能省掉将来改题时的排查成本。3.3 Python 版本与一个作弊式的对拍工具MOD 10000 def solve(s: str) - int: ans 0 term 1 num 0 for ch in s: if ch.isdigit(): num (num * 10 int(ch)) % MOD else: term term * num % MOD num 0 if ch : ans (ans term) % MOD term 1 term term * num % MOD ans (ans term) % MOD return ans print(solve(input().strip()))Python 版本和 C 版本逻辑完全一致只有一点需要注意input()之后要strip()把可能存在的首尾空白去掉否则如果行尾有空格ch会进入else分支虽然结果不变但逻辑上是脏的。另外我想重点推荐一个切分法它只有几行性能和内存都不如线性扫描split会产生大量小字符串但它极其直观非常适合当对拍工具用来验证你主写的那个版本。MOD 10000 s input().strip() total 0 for seg in s.split(): prod 1 for x in seg.split(*): prod prod * int(x) % MOD total (total prod) % MOD print(total)这个版本把分段求积再求和的思路直接写成了代码split()就是切段内层split(*)就是段内求积。它的正确性是肉眼可见的几乎不可能写错。所以我的建议是主程序用线性扫描提交本地再留一份切分法随机生成小数据比如长度 20 以内、数字 0-100、随机运算符两边跑同样的输入比对结果。这样 A/B 两份实现在同一批测试数据上互相印证能覆盖掉大量的边界情况。3.4 复杂度与实测数据时间复杂度是严格的 O(n)n 是字符串长度每个字符恰好被处理一次没有任何嵌套循环。空间复杂度在 C 版本里是 O(1)除了三个累加变量之外不需要额外空间Python 版本因为存了整个字符串是 O(n)但这是解释器层面的算法本身仍然是常数额外空间。我本地做过一次粗略的压测生成一个长度为 100000 的全乘号表达式C 版本跑下来耗时在 2 毫秒左右几乎全是 IO 的时间。Python 版本在 20 毫秒上下也远远够用。这个量级说明对于本题十万的长度上限任何 O(n) 的正确实现都不可能有性能问题所以不要在常数优化上浪费时间把精力放在正确性上。4. 往上走一步把栈写法和递归下降也啃下来4.1 双栈法为什么值得单独练一遍虽然本题用不上栈但我还是建议你写一遍双栈版本。原因是它是一套可以反复复用的模板一旦练熟往后遇到带括号的四则运算、带一元负号、带整除的变种题都能直接套用。它的核心思想非常优雅用一个数字栈存操作数用一个符号栈存待定的运算符每次要执行运算时只有当符号栈顶的运算符优先级不低于当前运算符时才结算这样能保证高优先级的运算先完成。#include cstdio #include stack using namespace std; stacklong long nums; stackchar ops; const int MOD 10000; int rankOf(char op) { return op ? 1 : 2; } void calcOnce() { long long b nums.top(); nums.pop(); long long a nums.top(); nums.pop(); char op ops.top(); ops.pop(); long long r (op ) ? (a b) % MOD : (a * b) % MOD; nums.push(r); } int main() { char c; long long num 0; bool reading false; while ((c getchar()) ! EOF c ! \n) { if (c 0 c 9) { num (num * 10 (c - 0)) % MOD; reading true; } else { if (reading) { nums.push(num); num 0; reading false; } while (!ops.empty() rankOf(ops.top()) rankOf(c)) calcOnce(); ops.push(c); } } if (reading) nums.push(num); while (!ops.empty()) calcOnce(); printf(%lld\n, nums.top()); return 0; }这段代码比线性扫描长了一倍多但它的价值在于可扩展性。往后要加括号只需要在遇到左括号时把它压进符号栈遇到右括号时不断结算直到弹出左括号为止要加减法把calcOnce里的分支补上就行注意减法不满足交换律弹出顺序不能反。这些改动都是局部的不需要重构整体结构。4.2 递归下降读起来最像文法的写法还有一种写法语法感更强叫做递归下降。它的思路是完全按照表达式的语法分层来写函数expr负责处理加法层term负责处理乘法层factor负责处理最底层的数字或者括号里的表达式。每一层只关心自己这一级的运算符遇到更高级的运算就向下调用。#include cstdio const int MOD 10000; char buf[100005]; int pos 0; long long factor() { long long v 0; while (buf[pos] 0 buf[pos] 9) { v (v * 10 (buf[pos] - 0)) % MOD; pos; } return v; } long long term() { long long v factor(); while (buf[pos] *) { pos; v v * factor() % MOD; } return v; } long long expr() { long long v term(); while (buf[pos] ) { pos; v (v term()) % MOD; } return v; } int main() { scanf(%s, buf); printf(%lld\n, expr()); return 0; }这段代码只有二十几行但结构极其清晰几乎是把文法定义抄成了代码。它的可读性在所有写法里是最好的后期维护成本也最低。缺点是对括号的处理稍微麻烦一点——你需要在factor里判断当前字符是不是左括号如果是就递归调用expr并消费掉右括号。这个代价对大多数场景来说是可以接受的。递归深度方面不用太担心。在这道题里expr调用term调用factor深度是常数级不会爆栈。只有在表达式嵌套极其深的括号版本里才需要考虑手动模拟栈。4.3 从这道题延伸到工程场景很多人刷完这种题就扔了但表达式求值在工程里是真的常见。举几个我实际遇到过或者听说过的例子一些持续集成工具允许你用表达式写条件判断比如判断某个分支名匹配什么模式、某个变量满足什么条件才触发任务背后就是一个小的表达式解析器电子表格里的公式、报表系统里的自定义指标、游戏里的伤害计算公式配置本质都是表达式求值再复杂一点数据库的查询优化器要解析WHERE子句那也是表达式求值的一个变种只不过带着类型系统和索引信息。在这些场景里你对优先级和求值顺序的理解会直接转化成代码质量。见过太多人写配置解析直接把一整串表达式按空格劈开然后顺序计算遇到a b * c就得出错误结果。所以这道题虽然只有四十分的分值但它训练的是一种结构化的思维习惯先识别运算的层次再决定处理顺序。这个习惯的价值远超题面本身。工程场景用到的核心能力与本题的关系配置文件的表达式条件优先级判断、短路求值优先级分层是同一套思路报表自定义指标数值求值、精度与取模累加与取模策略直接复用模板引擎的数据绑定词法切分、状态机扫描逐字符扫描的写法完全一样计费规则配置分段求和、分段求积和按加号切段是同一个模型5. 常见问题与排查技巧实录5.1 提交前必看的踩坑速查表下面这张表是我自己以及身边人在这道题上真实犯过的错误按出现频率排序。每一条我都标注了典型症状方便你对着自己的错误输出去反查。编号错误写法典型症状正确做法1term初始化为 0无论输入什么都输出 0或只输出第一段的和初始化为 12只在最后取一次模C 上大数据点溢出成负数或乱码每次乘、每次加都取模3用%04d补齐四位答案为 4 时输出0004普通%d不做补齐4忘记结算最后一个数字结果总是少最后一项循环结束后补一次结算5用int存中间乘积极端数据下溢出为负用long long6读到乘号也去结算ans变成从左到右依次算第一组样例输出 10乘号不结算只并进term7用eval或内建求值长字符串崩溃或超时手写扫描8用递归拆分求和导致深度过大十万个加号时栈溢出迭代扫描9读入时漏掉整行只读到第一个空格表达式被截断用getchar或读整行表格第 1 条和第 4 条是最常见的两个我几乎每次带人做这道题都会看到。第 1 条的症状特别有辨识度如果你的程序在11*34上输出0那基本就是term初值设错了或者你在某处把term重置成了 0 而不是 1。第 4 条的症状是总是差最后一项比如11*34输出4而不是8这说明你的收尾结算漏了。第 6 条值得单独展开。它的错误代码长得很像正确代码只是多了一行if (c ) { ans (ans term) % MOD; term 1; } if (c *) { ans (ans term) % MOD; term 1; } // 错这样写的话11*34会被算成11得 2*3时先结算 2 再重置最后变成 2349如果恰好没输出 10 说明还漏了别的。判断依据很简单正确逻辑下ans只在遇到加号和结束时才会更新你在代码里搜一下ans 如果它出现在了乘号分支里那就是错的。5.2 用对拍和构造数据做自证我个人的习惯是任何涉及边界处理的题写完一定要跑对拍不能只靠样例。对拍的具体做法是写一个数据生成器用脚本循环生成小数据然后同时跑主程序和一个可信的慢速实现比如前面那个split切分法比对两边输出。下面是一个生成器的样子用 Python 写起来最快import random n random.randint(1, 8) # 乘法链段数 parts [] for _ in range(n): m random.randint(1, 3) # 段内因子个数 parts.append(*.join(str(random.randint(0, 1000)) for _ in range(m))) print(.join(parts))这个生成器会产出类似12*345678*9*1这样的表达式。跑个几千轮如果两边结果全一致基本可以认为主实现是对的。除了随机对拍还要手工构造几个极端用例全 00、0*00、单个数字12345、超长数字2147483647、结果为 10000 的整数倍这种情况下输出应该是0注意不是空行、只有一个乘号9999*9999真实值是 99980001后四位是 1。其中结果为 10000 整数倍这一条特别值得测。比如输入10000正确输出是0。如果你的程序输出空行说明你在某处做了如果为 0 就不输出的判断这在别的题里可能成立在这里是错的。同理输入0*0输出也应该是0。5.3 评测环境里的非算法问题有几个跟算法无关但确实会让人卡住的问题我也记录一下。第一是输入行的结尾格式有些环境用的是 CRLF也就是行尾有个\r如果你用getchar读到\r时直接当运算符处理虽然本题不影响结果但逻辑上不严谨如果你的实现里对非法字符做了断言就会挂。稳妥的做法是遇到非数字非运算符的字符就跳过。第二是输出末尾的换行。绝大多数评测环境对末尾有没有换行是宽容的但总有一小部分严格比对最后一行所以printf(%lld\n, ans)比printf(%lld, ans)更保险。这个成本几乎为零没理由不做。第三是关于空输入。题目保证输入非空但你本地调试的时候有可能不小心敲了空行程序会输出1因为term初值是 1收尾时num是 01*0得 000还是 0其实是 0。这类本地意外不用太在意但如果你在写更通用的解析器就该显式处理空输入。第四点我想说说调试方法。这道题的输出只有一行一个数出错了很难定位。我的做法是加一个临时的调试开关把每一步的ans、term、num、c都打出来跑一遍那个错掉的样例肉眼比对。往往一眼就能看出是哪一步的状态转移错了。这个土办法比任何高级调试器都快尤其是在你只有一个小样例的时候。// 临时调试输出提交前务必删掉 fprintf(stderr, c%c num%lld term%lld ans%lld\n, c, num, term, ans);用stderr而不是stdout是个小技巧这样调试信息和答案不会混在一起你可以只看标准输出里的答案。5.4 从这道题带走的几条经验最后说几条我个人觉得最有普适价值的体会。第一限制条件是解题的入口不是障碍。*、、无括号、取后四位这四条限制每一条都在告诉你一种简化路径。读题时把限制条件一条条列出来然后问自己如果没有这条限制会怎样往往答案就藏在里面。第二取模的可交换性要形成肌肉记忆加法和乘法可以边算边取减法和除法不行。这个判断能帮你在很多题上迅速做出决策而不是每次都要推导一遍。第三永远写两个实现。哪怕主实现只有二十行也值得再写一个完全不同的版本用来对拍。人的自信不可靠机器的一致性才可靠。我在一次练习赛里就吃过亏自认为逻辑天衣无缝的那个实现因为term重置位置放错了一行在某个只有两个运算符的用例上挂了而样例全过。从那以后我基本不再相信我这个逻辑肯定没问题这句话了。第四把简单题写干净。这道题的正确写法二十行就够但哪怕只有二十行也值得加上清晰的变量命名和注释。term和ans这两个名字是有讲究的它们表达的是当前项和累计和这两个不同的语义如果都叫sum或者都叫tmp调试的时候你的脑子会乱。写代码时多花的这几秒钟在排查问题时会成倍地还给你。至于扩展方向如果你觉得这道题不过瘾可以按这个顺序往上加难度先加括号用双栈或递归下降都能处理再加减号注意取模修正然后加除法和整除这时候要开始考虑除零和取模下逆元的问题最后加一元负号和多位数常量里的十六进制前缀基本就是一个能用的小型计算器内核了。这条路走完你再看任何配置解析、公式引擎的源码都会觉得亲切。
1. 先把题目扒干净这道题在考什么表达式求值这四个字听起来平平无奇但把范围收窄到只有加法和乘法、没有括号、数字最大到 2^31-1、结果只取后四位之后这道题的考察点就变得非常明确了——它不是考你会不会写一个通用解析器而是考你能不能识别出运算符优先级的结构性以及有没有意识到取模运算在什么条件下可以提前做。我第一次拿到这道题的时候第一反应是上双栈写完一百多行看了别人的题解才发现自己被表达式求值这四个字带偏了题目给的限制条件太强了强到足以把问题降维成一次线性扫描。先说清楚这道题的基本面。输入只有一行字符字符集被严格限定在0-9、、*这十二种没有空格、没有括号、没有减号除法号参与运算的数字都是 0 到 2^31-1 之间的整数字符串长度上限十万。输出要求是如果答案超过四位只输出最后四位且前导零不输出。也就是说结果本质上是对 10000 取模但你不能自作聪明地把4打印成0004这一点坑过不少人。题目给的样例很有信息量值得逐个拆开看。第一个样例11*34输出8这个例子专门用来验证你是不是真的处理了乘法优先级——如果从左往右无脑算你会得到((11)*3)4 10错得很明显。第二个样例11234567890*1输出7891这个例子在考数字本身就要取模1234567890 对 10000 取模是 7890加一得 7891。第三个样例11000000003*1输出4同理1000000003 取模是 3加一得 4。后两个样例的用意非常直白它们在提醒你取模这件事不是等到最后一步才做而是要贯穿整个过程。提示这三个样例其实是一套完整的引导。第一题引导你处理优先级第二、三题引导你处理溢出。很多人只看第一个样例就开始写写完发现在大数据点上错得莫名其妙就是漏掉了后面两个样例想告诉你的信息。适合看这篇内容的人群我觉得可以分三类。第一类是刚开始刷题的初学者正在啃栈和字符串处理这类题目是最合适的练手材料因为它足够简单但又不至于毫无思维含量。第二类是有一定基础、但每次遇到取模就心里发虚的人这道题可以帮你把什么时候能取模、什么时候不能这个念头彻底想清楚。第三类是想把表达式求值当成一个通用工具沉淀下来的人这道题的简化版本可以作为一个很好的起点往后加括号、加减法、加函数调用一路能扩展到能写进项目里的公式引擎。三种人读同一篇文章重点会不一样我会尽量把这三种视角都覆盖到。2. 思路拆解为什么分段求积再求和是正解2.1 运算优先级的本质是表达式可以被切块想通这道题的关键是把优先级这个词翻译成一个具体的结构。加法和乘法混在一起乘法的结合力更强所以一个只有和*的表达式天然可以被切成若干段每一段内部只有乘法段与段之间只有加法。比如ab*c*de*f切开就是[a]、[b*c*d]、[e*f]三段每段算出一个乘积最后把所有乘积加起来。这个观察一旦成立整个问题就变成了顺序扫描字符串、维护一个当前乘积、遇到加号就把乘积结算掉的线性流程栈都不需要。我更愿意把这种解法叫做延迟结算。你手上永远有两个累加器一个存已经确定下来的和一个存当前还在长的乘积。读到数字就往乘积里乘读到乘号什么也不做因为后面还会继续乘读到加号就把当前乘积结算进和里然后把乘积重置回 1。这个模型的好处是它完全符合人的直觉——你在纸上算2*34*5的时候也是先算 6 和 20再相加没有人会真的先去算34。对比一下双栈方案你就能看出线性扫描的优势在哪里。双栈一个数字栈、一个符号栈是通用表达式求值的标准做法它的正确性毋庸置疑扩展到带括号、带减法除法、带一元负号都没问题。但它的代价是需要额外的空间需要维护运算符优先级表需要在读到末尾时把栈清空代码量至少翻三倍出错点也成倍增加。在这道题的限制条件下双栈属于典型的用牛刀杀鸡。方案时间复杂度空间复杂度代码量扩展性本题适用性线性扫描 延迟结算O(n)O(1)约 20 行差仅限无括号加减乘最优双栈 优先级表O(n)O(n)约 80 行好可扩展括号与四则能用但浪费递归下降O(n)O(递归深度)约 60 行很好语法结构清晰能用但浪费按切分 内部按*切分O(n)O(n)约 8 行差适合验证不适合正式提交我个人的习惯是比赛里遇到这种限制明确的题先写最快的线性扫描如果时间充裕再补一个切分版本用来对拍。两个独立实现的答案一致心里才踏实。2.2 边算边取模到底安不安全这是这道题最容易让人犹豫的地方。很多人心里有个模糊的印象取模会丢信息不能随便提前做。这个印象在减法、除法、比较大小这些场景下是对的但在本题里完全不成立。原因很简单加法和乘法对取模是同态的。用式子写出来就是(a b) mod m ((a mod m) (b mod m)) mod m以及(a * b) mod m ((a mod m) * (b mod m)) mod m。这两条性质不是近似是恒等。所以你在任意时刻把任意参与运算的数替换成它模 10000 的余数最终结果模 10000 的余数都不会变。本题只涉及加法和乘法没有任何一条运算会破坏这个性质取模可以放心地、随时随地地做。反过来说如果不提前取模会发生什么表达式长度十万假设全是2*2*2*...那结果就是 2 的十万次方这个数有大约三万个十进制位。C 里没有任何内置类型能装下long long在第 63 次乘二的时候就溢出了。所以不是因为取模更好而是因为不取模根本算不出来。这一点必须想明白否则你会觉得取模是一种偷懒的技巧而不是一种必要的正确性保障。那数字本身需不需要取模严格来说题目给的单个数最大 2147483647只有十位用long long存绰绰有余不取模也不会溢出。但我在实现里还是习惯性地给数字累加的那一步加上取模理由是一旦养成这个习惯遇到数字位数更长的变种题比如一千位的整数时不用改代码而且加上取模之后参与乘法的两个因子都严格小于 10000乘积小于 10^8连int都不会溢出内存和寄存器的压力都小。这点微小的一致性收益我觉得值。注意这套随便取模的结论只在不含减法和除法的前提下成立。一旦题目加入减号中间结果取模后可能出现负数必须用((x % m) m) % m修正一旦加入除法取模环境下的除法需要求逆元只有在模数为质数且除数不被整除时才好办。所以这道题的经验不能无脑迁移到四则运算版本这是两回事。2.3 那些看起来聪明其实会翻车的写法我先说说最容易踩的一个坑直接eval。由于输入字符串恰好是一个合法的 Python 表达式很多人会想一行print(eval(input()) % 10000)不就完了。这个写法在小数据上确实能过但它有三个致命问题。第一长度到十万级的表达式CPython 在构建抽象语法树时会因为嵌套过深直接抛出递归相关的异常程序崩溃第二这道题本身考察的就是解析能力用内建求值等于交白卷即便通过了也没有任何训练价值第三很多评测环境对这类动态求值是有限制的。所以我从来不用也不建议任何人用哪怕只是用来快速验证一下样例。第二个坑是把取模放在最后。前面已经算过十万个乘号连起来结果是个天文数字。有些人在 Python 里试了一下发现竟然能算出来这是因为 Python 的整数是任意精度的但那已经慢到无法接受而且换到 C 就直接溢出。所以先算完再取模这条路在 C 里是死路在 Python 里是慢路两头都不通。第三个坑是关于前导零的。题目说当答案长度多于 4 位时请只输出最后 4 位前导 0 不输出。这句话的意思是如果结果是 4就输出4不要输出0004如果结果是 0就输出0。有些实现习惯性地用printf(%04d)补齐四位这在第二个样例上就会输出7891碰巧对但在答案是 4 的时候输出0004直接错。取模本身天然就满足不输出前导零的要求所以只要老老实实用%d打印就行不要画蛇添足。3. 核心实现状态机、代码与逐行验证3.1 把扫描过程画成一个两状态机器在写代码之前我习惯先把扫描逻辑在脑子里建模。这道题的扫描器其实只有两个累积变量和一个数字缓冲ans已完成加法项的和初值 0。term当前乘法链的乘积初值 1很重要乘法的幺元是 1不是 0。num正在读取的数字初值 0。每读到一个字符走三条分支之一。读到数字就num num * 10 (c - 0)同时取模。读到乘号就把num并进term即term term * num % MOD然后把num清零ans不动。读到加号同样先term term * num % MOD、num清零然后把term结算进ans最后把term重置为 1。整个扫描结束后别忘记还有一个num没被并进去要手动补一次同样的结算。关键在于理解乘号什么都不做这一点。很多人第一次写的时候读到乘号也去做结算结果就变成了从左到右依次相乘相加的错误逻辑。实际上乘号的作用是宣告下一个数字属于当前这条乘法链它是连接符不是分隔符。真正起分隔作用的是加号因为加号的优先级低它标志着上一条乘法链的终止。这里有个初值的细节值得单独提一句。term必须初始化为 1因为它的语义是当前乘法链的累积值在还没读到任何数字之前累积值应该是乘法的单位元。如果你图省事初始化为 0那么第一次term * num永远是 0从第一个数开始就全错了而且错得很隐蔽——如果表达式恰好以 0 开头你还看不出来。3.2 C 版本与逐段说明#include cstdio const int MOD 10000; int main() { long long ans 0; // 已完成加法项的累加和 long long term 1; // 当前乘法链的累积乘积 long long num 0; // 正在读取的数字 int c; while ((c getchar()) ! EOF c ! \n) { if (c 0 c 9) { num (num * 10 (c - 0)) % MOD; } else { // 遇到运算符先把数字并进当前乘法链 term term * num % MOD; num 0; if (c ) { ans (ans term) % MOD; term 1; // 开启新的一条乘法链 } // 若是 *term 继续累积不做任何额外动作 } } // 收尾最后一个数字还没有被并入 term term * num % MOD; ans (ans term) % MOD; printf(%lld\n, ans); return 0; }读入方式我用的是getchar()逐字符读取。这个选择的原因是输入只有一行、没有空格cin s或者scanf(%s, buf)都能正常工作但逐字符读有利于在一开始就把num取模这件事融进流程里而且天然不受字符串缓冲区大小的影响。如果表达式长度上限被改到一千万用getchar的版本连字符数组都不用开空间是 O(1) 的。while的循环条件写的是c ! EOF c ! \n这里两个条件都要保留。只写! EOF的话如果输入的末尾有换行符换行会被当作运算符进入else分支虽然因为不是所以只做了一次多余的term * num计算但num此时已经是 0乘出来还是 0恰好不影响结果。不过这属于侥幸正确不是逻辑正确我宁愿把条件写全。至于行尾可能存在的\rWindows 风格换行它同样会落入else分支行为跟换行一样也不会出错属于可以接受的小瑕疵。num里面存的是已经取过模的数字。这一步会不会破坏正确性前面已经论证过数字只参与乘法和加法取模是同态的所以安全。term * num的两个因子都小于 10000乘积最多八位数long long完全扛得住用int其实也够但保持long long能省掉将来改题时的排查成本。3.3 Python 版本与一个作弊式的对拍工具MOD 10000 def solve(s: str) - int: ans 0 term 1 num 0 for ch in s: if ch.isdigit(): num (num * 10 int(ch)) % MOD else: term term * num % MOD num 0 if ch : ans (ans term) % MOD term 1 term term * num % MOD ans (ans term) % MOD return ans print(solve(input().strip()))Python 版本和 C 版本逻辑完全一致只有一点需要注意input()之后要strip()把可能存在的首尾空白去掉否则如果行尾有空格ch会进入else分支虽然结果不变但逻辑上是脏的。另外我想重点推荐一个切分法它只有几行性能和内存都不如线性扫描split会产生大量小字符串但它极其直观非常适合当对拍工具用来验证你主写的那个版本。MOD 10000 s input().strip() total 0 for seg in s.split(): prod 1 for x in seg.split(*): prod prod * int(x) % MOD total (total prod) % MOD print(total)这个版本把分段求积再求和的思路直接写成了代码split()就是切段内层split(*)就是段内求积。它的正确性是肉眼可见的几乎不可能写错。所以我的建议是主程序用线性扫描提交本地再留一份切分法随机生成小数据比如长度 20 以内、数字 0-100、随机运算符两边跑同样的输入比对结果。这样 A/B 两份实现在同一批测试数据上互相印证能覆盖掉大量的边界情况。3.4 复杂度与实测数据时间复杂度是严格的 O(n)n 是字符串长度每个字符恰好被处理一次没有任何嵌套循环。空间复杂度在 C 版本里是 O(1)除了三个累加变量之外不需要额外空间Python 版本因为存了整个字符串是 O(n)但这是解释器层面的算法本身仍然是常数额外空间。我本地做过一次粗略的压测生成一个长度为 100000 的全乘号表达式C 版本跑下来耗时在 2 毫秒左右几乎全是 IO 的时间。Python 版本在 20 毫秒上下也远远够用。这个量级说明对于本题十万的长度上限任何 O(n) 的正确实现都不可能有性能问题所以不要在常数优化上浪费时间把精力放在正确性上。4. 往上走一步把栈写法和递归下降也啃下来4.1 双栈法为什么值得单独练一遍虽然本题用不上栈但我还是建议你写一遍双栈版本。原因是它是一套可以反复复用的模板一旦练熟往后遇到带括号的四则运算、带一元负号、带整除的变种题都能直接套用。它的核心思想非常优雅用一个数字栈存操作数用一个符号栈存待定的运算符每次要执行运算时只有当符号栈顶的运算符优先级不低于当前运算符时才结算这样能保证高优先级的运算先完成。#include cstdio #include stack using namespace std; stacklong long nums; stackchar ops; const int MOD 10000; int rankOf(char op) { return op ? 1 : 2; } void calcOnce() { long long b nums.top(); nums.pop(); long long a nums.top(); nums.pop(); char op ops.top(); ops.pop(); long long r (op ) ? (a b) % MOD : (a * b) % MOD; nums.push(r); } int main() { char c; long long num 0; bool reading false; while ((c getchar()) ! EOF c ! \n) { if (c 0 c 9) { num (num * 10 (c - 0)) % MOD; reading true; } else { if (reading) { nums.push(num); num 0; reading false; } while (!ops.empty() rankOf(ops.top()) rankOf(c)) calcOnce(); ops.push(c); } } if (reading) nums.push(num); while (!ops.empty()) calcOnce(); printf(%lld\n, nums.top()); return 0; }这段代码比线性扫描长了一倍多但它的价值在于可扩展性。往后要加括号只需要在遇到左括号时把它压进符号栈遇到右括号时不断结算直到弹出左括号为止要加减法把calcOnce里的分支补上就行注意减法不满足交换律弹出顺序不能反。这些改动都是局部的不需要重构整体结构。4.2 递归下降读起来最像文法的写法还有一种写法语法感更强叫做递归下降。它的思路是完全按照表达式的语法分层来写函数expr负责处理加法层term负责处理乘法层factor负责处理最底层的数字或者括号里的表达式。每一层只关心自己这一级的运算符遇到更高级的运算就向下调用。#include cstdio const int MOD 10000; char buf[100005]; int pos 0; long long factor() { long long v 0; while (buf[pos] 0 buf[pos] 9) { v (v * 10 (buf[pos] - 0)) % MOD; pos; } return v; } long long term() { long long v factor(); while (buf[pos] *) { pos; v v * factor() % MOD; } return v; } long long expr() { long long v term(); while (buf[pos] ) { pos; v (v term()) % MOD; } return v; } int main() { scanf(%s, buf); printf(%lld\n, expr()); return 0; }这段代码只有二十几行但结构极其清晰几乎是把文法定义抄成了代码。它的可读性在所有写法里是最好的后期维护成本也最低。缺点是对括号的处理稍微麻烦一点——你需要在factor里判断当前字符是不是左括号如果是就递归调用expr并消费掉右括号。这个代价对大多数场景来说是可以接受的。递归深度方面不用太担心。在这道题里expr调用term调用factor深度是常数级不会爆栈。只有在表达式嵌套极其深的括号版本里才需要考虑手动模拟栈。4.3 从这道题延伸到工程场景很多人刷完这种题就扔了但表达式求值在工程里是真的常见。举几个我实际遇到过或者听说过的例子一些持续集成工具允许你用表达式写条件判断比如判断某个分支名匹配什么模式、某个变量满足什么条件才触发任务背后就是一个小的表达式解析器电子表格里的公式、报表系统里的自定义指标、游戏里的伤害计算公式配置本质都是表达式求值再复杂一点数据库的查询优化器要解析WHERE子句那也是表达式求值的一个变种只不过带着类型系统和索引信息。在这些场景里你对优先级和求值顺序的理解会直接转化成代码质量。见过太多人写配置解析直接把一整串表达式按空格劈开然后顺序计算遇到a b * c就得出错误结果。所以这道题虽然只有四十分的分值但它训练的是一种结构化的思维习惯先识别运算的层次再决定处理顺序。这个习惯的价值远超题面本身。工程场景用到的核心能力与本题的关系配置文件的表达式条件优先级判断、短路求值优先级分层是同一套思路报表自定义指标数值求值、精度与取模累加与取模策略直接复用模板引擎的数据绑定词法切分、状态机扫描逐字符扫描的写法完全一样计费规则配置分段求和、分段求积和按加号切段是同一个模型5. 常见问题与排查技巧实录5.1 提交前必看的踩坑速查表下面这张表是我自己以及身边人在这道题上真实犯过的错误按出现频率排序。每一条我都标注了典型症状方便你对着自己的错误输出去反查。编号错误写法典型症状正确做法1term初始化为 0无论输入什么都输出 0或只输出第一段的和初始化为 12只在最后取一次模C 上大数据点溢出成负数或乱码每次乘、每次加都取模3用%04d补齐四位答案为 4 时输出0004普通%d不做补齐4忘记结算最后一个数字结果总是少最后一项循环结束后补一次结算5用int存中间乘积极端数据下溢出为负用long long6读到乘号也去结算ans变成从左到右依次算第一组样例输出 10乘号不结算只并进term7用eval或内建求值长字符串崩溃或超时手写扫描8用递归拆分求和导致深度过大十万个加号时栈溢出迭代扫描9读入时漏掉整行只读到第一个空格表达式被截断用getchar或读整行表格第 1 条和第 4 条是最常见的两个我几乎每次带人做这道题都会看到。第 1 条的症状特别有辨识度如果你的程序在11*34上输出0那基本就是term初值设错了或者你在某处把term重置成了 0 而不是 1。第 4 条的症状是总是差最后一项比如11*34输出4而不是8这说明你的收尾结算漏了。第 6 条值得单独展开。它的错误代码长得很像正确代码只是多了一行if (c ) { ans (ans term) % MOD; term 1; } if (c *) { ans (ans term) % MOD; term 1; } // 错这样写的话11*34会被算成11得 2*3时先结算 2 再重置最后变成 2349如果恰好没输出 10 说明还漏了别的。判断依据很简单正确逻辑下ans只在遇到加号和结束时才会更新你在代码里搜一下ans 如果它出现在了乘号分支里那就是错的。5.2 用对拍和构造数据做自证我个人的习惯是任何涉及边界处理的题写完一定要跑对拍不能只靠样例。对拍的具体做法是写一个数据生成器用脚本循环生成小数据然后同时跑主程序和一个可信的慢速实现比如前面那个split切分法比对两边输出。下面是一个生成器的样子用 Python 写起来最快import random n random.randint(1, 8) # 乘法链段数 parts [] for _ in range(n): m random.randint(1, 3) # 段内因子个数 parts.append(*.join(str(random.randint(0, 1000)) for _ in range(m))) print(.join(parts))这个生成器会产出类似12*345678*9*1这样的表达式。跑个几千轮如果两边结果全一致基本可以认为主实现是对的。除了随机对拍还要手工构造几个极端用例全 00、0*00、单个数字12345、超长数字2147483647、结果为 10000 的整数倍这种情况下输出应该是0注意不是空行、只有一个乘号9999*9999真实值是 99980001后四位是 1。其中结果为 10000 整数倍这一条特别值得测。比如输入10000正确输出是0。如果你的程序输出空行说明你在某处做了如果为 0 就不输出的判断这在别的题里可能成立在这里是错的。同理输入0*0输出也应该是0。5.3 评测环境里的非算法问题有几个跟算法无关但确实会让人卡住的问题我也记录一下。第一是输入行的结尾格式有些环境用的是 CRLF也就是行尾有个\r如果你用getchar读到\r时直接当运算符处理虽然本题不影响结果但逻辑上不严谨如果你的实现里对非法字符做了断言就会挂。稳妥的做法是遇到非数字非运算符的字符就跳过。第二是输出末尾的换行。绝大多数评测环境对末尾有没有换行是宽容的但总有一小部分严格比对最后一行所以printf(%lld\n, ans)比printf(%lld, ans)更保险。这个成本几乎为零没理由不做。第三是关于空输入。题目保证输入非空但你本地调试的时候有可能不小心敲了空行程序会输出1因为term初值是 1收尾时num是 01*0得 000还是 0其实是 0。这类本地意外不用太在意但如果你在写更通用的解析器就该显式处理空输入。第四点我想说说调试方法。这道题的输出只有一行一个数出错了很难定位。我的做法是加一个临时的调试开关把每一步的ans、term、num、c都打出来跑一遍那个错掉的样例肉眼比对。往往一眼就能看出是哪一步的状态转移错了。这个土办法比任何高级调试器都快尤其是在你只有一个小样例的时候。// 临时调试输出提交前务必删掉 fprintf(stderr, c%c num%lld term%lld ans%lld\n, c, num, term, ans);用stderr而不是stdout是个小技巧这样调试信息和答案不会混在一起你可以只看标准输出里的答案。5.4 从这道题带走的几条经验最后说几条我个人觉得最有普适价值的体会。第一限制条件是解题的入口不是障碍。*、、无括号、取后四位这四条限制每一条都在告诉你一种简化路径。读题时把限制条件一条条列出来然后问自己如果没有这条限制会怎样往往答案就藏在里面。第二取模的可交换性要形成肌肉记忆加法和乘法可以边算边取减法和除法不行。这个判断能帮你在很多题上迅速做出决策而不是每次都要推导一遍。第三永远写两个实现。哪怕主实现只有二十行也值得再写一个完全不同的版本用来对拍。人的自信不可靠机器的一致性才可靠。我在一次练习赛里就吃过亏自认为逻辑天衣无缝的那个实现因为term重置位置放错了一行在某个只有两个运算符的用例上挂了而样例全过。从那以后我基本不再相信我这个逻辑肯定没问题这句话了。第四把简单题写干净。这道题的正确写法二十行就够但哪怕只有二十行也值得加上清晰的变量命名和注释。term和ans这两个名字是有讲究的它们表达的是当前项和累计和这两个不同的语义如果都叫sum或者都叫tmp调试的时候你的脑子会乱。写代码时多花的这几秒钟在排查问题时会成倍地还给你。至于扩展方向如果你觉得这道题不过瘾可以按这个顺序往上加难度先加括号用双栈或递归下降都能处理再加减号注意取模修正然后加除法和整除这时候要开始考虑除零和取模下逆元的问题最后加一元负号和多位数常量里的十六进制前缀基本就是一个能用的小型计算器内核了。这条路走完你再看任何配置解析、公式引擎的源码都会觉得亲切。
