表达式求值入门：栈结构、运算符优先级与取模处理实战

1. 这道表达式求值到底考什么先把题目拆开看第一次在题库里刷到 P1981 这道题很多人的反应是就这——输入一行只含加号、乘号和数字的字符串求值最后对 10000 取模。看上去像小学三年级的口算题。但真正坐下来动手写你会发现它是一道被名字严重耽误的栈结构入门题也是把优先级这个抽象概念第一次翻译成机器能执行的代码的经典场景。题目核心约束就三条表达式里没有括号运算符只有和*表达式长度上限十万级。这三条直接决定了整个方案的设计走向——没有括号意味着不需要处理嵌套上下文只有两种运算符意味着优先级只有两层长度十万意味着你必须考虑数字本身的位数问题。很多新手栽在第三点上以为题目给的数字都是int范围内的三五位数结果一提交就挂掉一半测试点。所以这道题真正的考察点是你能不能把先乘后加这个约定俗成的数学规则转换成一个程序可以稳定执行的过程你能不能理解取模运算为什么可以边算边取而不是最后一次性取你能不能在字符流上正确地切分出一个可能长达数万位的大整数。这篇文章面向刚接触栈和模拟题的初中级读者也面向想复习一遍中缀表达式处理的老手——后面我会把双栈法、单栈累积法、中缀转后缀、递归下降四种打法全部摊开讲附带我对拍验证过后的数据和踩过的坑。2. 整体思路拆解为什么这道题是栈的最佳入门案例2.1 从数学约定出发把表达式重新理解一遍在动手写代码之前我习惯先把题目里隐含的数学结构翻译成人话。像12*34*5这样的式子按运算优先级实际执行的顺序是1 (2*3) (4*5)。这个划分方式非常关键加号是分割符它把整个表达式切成了若干个互不干扰的乘法块。每一块内部只做乘法块与块之间只做加法。换个角度看a*b c*d e*f里的三个乘积项之间是平等的、可交换的它们之间不存在谁先谁后的问题。这就意味着一个极其朴素的思路我只要在扫描字符串的过程中把当前正在构建的乘积项维护好一旦碰到加号就把这个乘积项结算出来扔进总和然后重新开始一个新的乘积项。整道题瞬间从一个需要优先级判断的复杂问题退化成了一个单次扫描的线性问题。这个视角转变是本篇文章最重要的一句话。很多人一上来就搬出教科书里的双栈法写七八十行代码各种边界情况调试到崩溃其实是因为没意识到这道题的特殊性。双栈法是通用解法但通用是有代价的——它需要你正确实现优先级比较、需要你在符号栈里维护单调性、需要在末尾清空两个栈。而在这道题里优先级层次固定为两层我们完全可以把逻辑写死。当然我把双栈法也完整写出来原因有两个一是它是后面加括号、加减号、加除法的扩展基础二是很多题目的变种并不会像这道题这么友好掌握通用解法是必须的。先讲特殊再讲通用这个顺序我认为更适合学习。2.2 四种主流解法的横向对比与选型理由我把这道题能用的几种方案列了个对比表按我个人的推荐顺序排解法代码量时间复杂度空间复杂度适用场景主要风险点单栈乘积累积法约 25 行O(n)O(1)无括号、仅加乘末尾结算容易漏双栈中缀求值约 60 行O(n)O(n)可扩展到加减乘除括号优先级比较写反中缀转后缀再求值约 80 行O(n)O(n)教学演示、需要复用后缀序列数字与运算符切分递归下降解析约 50 行O(n)O(递归深度)后续加括号、加一元负号递归边界写错导致死循环单栈法的优势是常数极小、不占额外内存跑十万长度毫无压力代价是它高度依赖只有加号乘法、没有括号这个前提一旦题目改成含减号你就得重新想括号和负号的表示问题扩展性几乎为零。双栈法是稳妥派虽然代码长但思维模型和后面所有的表达式题目通用我建议每个人至少手写一遍。中缀转后缀也就是常说的大约 1960 年代提出的调度场算法思路在这道题上其实有点杀鸡用牛刀因为结果并不需要真的输出后缀序列。不过如果你想理解编译器前端是怎么解析表达式的这条路值得走一遍。递归下降则是从语法定义出发的写法expr : term ( term)*term : factor (* factor)*写成代码之后逻辑异常清晰是很多竞赛选手最爱的手感。我个人的建议是先用单栈法把题过掉建立信心再用双栈法重写一遍建立通用能力最后用递归下降写一遍建立对表达式语法的直觉。三遍下来你对表达式这个东西的理解会发生质变。2.3 取模到底该放在哪一步一个容易被忽视的设计决策题目要求对 10000 取模。这里有个非常典型的思维分岔口是先把整个表达式算完再取模还是边算边取模从数学上看加法和乘法对取模是同态的。也就是说(a b) mod m ((a mod m) (b mod m)) mod m乘法同理(a * b) mod m ((a mod m) * (b mod m)) mod m。这两条性质保证了边算边取和最后取的结果完全一致。但工程上边算边取是唯一可行的方案原因在于溢出。题目给的长度是十万级最极端的情况下整个输入就是一串数字那么这个数字可能有接近十万位。哪怕用 64 位整数也装不下必须边读边取模。我实际测过如果只用一个int存储完整的数字输入到第二十几个数字就开始出错。这是这道题的第一个大坑。还有一个细节值得说清楚取模之后再做乘法两个数最大都是 9999乘积约等于 1e8远小于int上限 2.1e9理论上用int也安全。但我依然建议你在中间变量上统一使用long long因为一旦后续题目把模数改成 1e97这是个非常常见的变体int乘int立刻会溢出。养成中间结果用 long long的习惯成本几乎为零收益却很大。3. 核心细节解析字符流里的三个关键动作3.1 数字的逐位读取与进位取模输入是一整行字符串数字和运算符之间没有空格。这就意味着你必须自己处理从哪个字符开始是数字到哪个字符数字结束。标准写法是这样的long long x 0; while (i n isdigit(s[i])) { x (x * 10 (s[i] - 0)) % MOD; i; }这段三行代码里有三个值得展开讲的点。第一x * 10意味着每一位都在向前进位这和你手算多位数是一样的原理只不过进制固定为 10。第二s[i] - 0是把字符7转成整数 7 的标准技巧因为 ASCII 编码里数字字符是连续排列的相邻字符的差值就是字符对应的数值差。第三取模放在累加之后而不是循环结束之后保证x在任何时刻都不超过 9999永远不会溢出。注意那个i写在循环体内部循环结束后i指向的是数字后面的第一个非数字字符。如果外层也是for循环并且也做i就会跳过这个字符导致运算符被吞掉。我的做法是在内层循环结束后立即i--让外层的i把它推回正确位置另一种做法是把外层改成while (i n)手动控制。前者更常见但第一次写特别容易忘。还有一个隐蔽的边界表达式可能以数字结尾。如果你依赖读到运算符时才结算前面的数字那么最后一个数字永远不会被结算。这是这道题第二高频的错误来源我在下面第 5 节会专门做一张速查表。3.2 加号作为分块符的语义解读前面提到加号把表达式切成乘法块这个理解在代码里怎么落地我用单栈法来解释因为它最直接。维护三个变量num表示当前正在读但还没归属的数字term表示当前这一乘以块已经积累的乘积sum表示已经结算完成的块的总和。扫描过程中遇到数字字符继续累积到num遇到*把num乘进term然后清空num表示这个因子已经被消化了遇到先把num乘进term完成当前块然后把term加进sum接着把term重置为乘法单位元 1num清零扫描结束后还剩最后一块没结算照做一次即可。这里有个初学者常犯的概念错误把term初始化成 0。为什么必须是 1因为term代表的是若干个因子的乘积而在还没乘任何因子之前这个乘积是空的。数学上空乘积定义为 1这就是乘法单位元。如果初始化成 0那么第一个块无论乘什么都变成 0答案直接错。这种单位元思维在累加初值 0和累乘初值 1里反复出现值得记牢。3.3 取模位置对正确性的三重影响取模这事儿我见过三类翻车方式都很典型。第一类是忘记在数字解析时取模导致x溢出为负数或者别的数取模后得到乱七八糟的余数。第二类是在乘法之后忘记再取一次模term * num最大可能到 1e8 级别虽然这道题不会溢出但如果你把模数改成 1e97 立刻爆掉。第三类最隐蔽结算加和时忘记取模sum累加多次之后可能超过int范围。我给自己的规矩是只要这个值之后还要参与运算就立刻取模。写起来多敲几个%MOD但省下的调试时间远超成本。这道题的模数 10000 不是质数10000 2^4 × 5^4这一点在纯加减乘的场景下没有影响但如果你打算把题目扩展成含除法的版本就必须注意不能简单用费马小定理求逆元得改用分解质因数或者高精度除法的思路。这个坑我在第 6 节扩展部分会再提一次。4. 实操过程三套代码从零写到通过4.1 单栈乘积累积法最短路径这是我最推荐的第一遍写法逻辑干净几乎不可能写错#include cstdio #include cstring const int MOD 10000; char s[100005]; int main() { scanf(%s, s); int n strlen(s); long long sum 0; // 已完成块的总和 long long term 1; // 当前乘积块乘法单位元是 1 long long num 0; // 正在读取的数字 for (int i 0; i n; i) { char c s[i]; if (c 0 c 9) { num (num * 10 (c - 0)) % MOD; } else if (c *) { term (term * num) % MOD; num 0; } else if (c ) { term (term * num) % MOD; sum (sum term) % MOD; term 1; num 0; } } // 收尾结算最后一块 term (term * num) % MOD; sum (sum term) % MOD; printf(%lld\n, sum % MOD); return 0; }我逐段说一下意图。scanf(%s, s)会自动跳过前导空白并读到第一个空白为止这对题目给的一行表达式输入格式来说正好够用如果你用getline读入记得处理可能存在的回车残留。数组开到 100005 是因为输入长度上限约十万多开几个字节防越界这是竞赛里很便宜的保险。主循环里三个分支互斥顺序无所谓但我习惯按数字优先、乘法次之、加法最后排因为这是优先级从高到低的顺序读代码时大脑负担更小。收尾那两行是整段代码里最容易漏的只要你在本地测试用例里放一个12第一次提交大概率就是在这里挂掉。提示如果你写的是while (i n)而不是for记得在数字解析的内层循环里手动推进i别写成死循环。这类内层循环和外层循环共享下标的写法是模拟题里最常见的死循环来源。4.2 双栈中缀求值通用方案的完整实现想清楚通用解法是为了后面遇到带括号、带减号的变种时不用重新发明轮子。双栈法的核心是两个栈一个存操作数一个存运算符核心规则是新运算符入栈前先把栈顶所有优先级不低于它的运算结算掉。#include bits/stdc.h using namespace std; const long long MOD 10000; int priority(char c) { if (c *) return 2; return 1; // } int main() { string s; cin s; int n s.size(); stacklong long nums; stackchar ops; auto apply []() { long long b nums.top(); nums.pop(); long long a nums.top(); nums.pop(); char c ops.top(); ops.pop(); if (c ) nums.push((a b) % MOD); else nums.push((a * b) % MOD); }; for (int i 0; i n; i) { if (isdigit(s[i])) { long long x 0; while (i n isdigit(s[i])) { x (x * 10 (s[i] - 0)) % MOD; i; } i--; // 回退一位交给外层 for 推进 nums.push(x); } else { while (!ops.empty() priority(ops.top()) priority(s[i])) { apply(); } ops.push(s[i]); } } while (!ops.empty()) apply(); cout nums.top() % MOD endl; return 0; }有几个地方我想重点圈一下。apply里先取b再取a顺序不能反因为栈是后进先出先弹出的是右操作数。减法和除法对顺序敏感这道题虽然只有加乘无所谓顺序但养成正确习惯以后少踩坑。priority(ops.top()) priority(s[i])里的也很讲究。用意味着遇到同优先级的运算符时先算左边这符合加乘的结合律方向也让表达式求值符合直觉。如果你把改成在只有加乘的情况下结果依然正确因为加减乘都满足结合律但一旦扩展进减法就会算错。这种当前正确但扩展就错的隐患是我调试时最警惕的东西。那个i--是我个人认为这段代码里最丑但必不可少的一行。数字解析用内层while把i推到了运算符位置外层for还会再推一次所以要退回来。另一种更干净的写法是全程用while (i n)加手动推进我见过不少选手这么写可读性确实更好但对指针位置的心智负担更高。两种写法没有绝对优劣选定一种并保持全篇一致就行。4.3 递归下降解析从语法定义直接翻译成代码如果你对表达式是一种语法结构这件事有感觉递归下降会让你写得非常爽。它的思路是把表达式按语法规则拆成三层expr : term ( term)*term : factor (* factor)*factor : number代码几乎就是这三行规则的直译#include bits/stdc.h using namespace std; const long long MOD 10000; string s; int pos 0; int n; long long parseFactor() { long long x 0; while (pos n isdigit(s[pos])) { x (x * 10 (s[pos] - 0)) % MOD; pos; } return x; } long long parseTerm() { long long v parseFactor(); while (pos n s[pos] *) { pos; v (v * parseFactor()) % MOD; } return v; } long long parseExpr() { long long v parseTerm(); while (pos n s[pos] ) { pos; v (v parseTerm()) % MOD; } return v; } int main() { cin s; n s.size(); cout parseExpr() % MOD endl; return 0; }这段代码没有任何显式的栈结构但递归调用栈本身就是栈。parseExpr里调用parseTerm的那一刻多余的加号先被压在调用栈上等parseTerm返回后再继续加这就是优先级的天然实现。我第一次看懂这种写法的时候是很震撼的——原来优先级不需要用显式的数据结构去比对语法层级本身就编码了优先级。它的缺点是递归深度受栈大小限制。这道题的表达式最坏情况下可能由五万个小块组成每次加法对应一层递归……不对注意parseExpr里的while循环是迭代写法加号并不产生新的递归层级所以递归深度只受嵌套影响而这题没有括号深度恒定。这也是为什么我能放心推荐它。但如果题目加了括号parseFactor里就会递归调用parseExpr深度等于括号嵌套层数这时候就得注意栈溢出的风险了。4.4 三种写法的实测结果与性能对照我把三份代码在本地各跑了一遍构造了三类测试短表达式、纯数字的十万位大数、大量1*1*1*...*111...交替的极值串。结果如下写法样例通过极端长度耗时代码行数首写正确率我的经验单栈累积是约 3 ms约 35 行高但收尾易漏双栈求值是约 8 ms约 60 行中i--和优先级易错递归下降是约 5 ms约 50 行高语法映射直觉强耗时差异在竞赛里可以忽略因为数据规模只有十万任何 O(n) 的写法都是毫秒级。选择哪一篇的标准不该是性能而是你能不能一次性写对、以及这个写法能不能让你后面少走弯路。我自己的实际路径是比赛时用单栈法因为敲得快、不容易错平时练习用递归下降因为写起来最享受给别人讲题时用双栈法因为它最教科书听众的接受度最高。这三种场景对应三种不同需求别硬套一个方案。5. 常见问题排查我踩过的坑与速查表5.1 十个高频错误的成因与修法下面这张表是我从自己和他人的提交记录里整理出来的按出现频率从高到低排现象根因修法末尾数字丢失循环结束后没结算最后一块收尾强制补一次term*num和sumterm大数测试点错误数字解析时没取模x (x*10 d) % MOD运算符被吞内层循环后没回退下标加i--或改while控制全 0 输出term初始化成 0初始化为 1乘法单位元结果差 1 或差模数输出前没再取一次模输出sum % MOD段错误数组开得太小开到上限 5乘法处溢出中间变量用int统一用long long空表达式崩溃没考虑输入为空加判空保护换行符干扰用getline未剥离\r用scanf(%s)或手动剥离优先级写反写成或反之明确结合方向后在注释里写清我特别想讲全 0 输出这一条。第一次写单栈法的时候我把term初始化为 0本地跑12*3得到 0盯着看了十几分钟没想明白。后来才反应过来term是乘积第一块也是从空积开始乘的空积就是 1。这个错误很蠢但它背后的概念单位元不蠢想清楚之后类似的错误就再也不会犯了。还有运算符被吞这一条它的表现非常诡异123会算成123之类的结果看起来像是某个加号消失了。第一次遇到时我一度怀疑是输入读取的问题加了打印才发现是下标推进的锅。这类症状和原因隔了一层的 bug最好的排查方式就是在循环里打印当前下标和当前字符而不是靠猜。5.2 手造数据与对拍验证正确性的低成本手段题目的样例往往只有一两个覆盖不到你代码里的隐藏假设。我的习惯是自己造一组覆盖几类典型情况12*3 → 7 1*23*4 → 14 0 → 0 10000 → 0 9999*9999 → 1 1*11*11 → 39999*9999这个用例是用来验证取模正确性的因为 9999 是模数的前一个数它的平方对 10000 取模正好是 1。10000用来验证数字本身就大于等于模数的边界。1*11*11用来检查乘积项之间的累加有没有把加号误当成乘号。如果要更严格地验证我推荐写一个对拍脚本写一份暴力版本比如用 Python 的大整数直接把表达式算出来最后取模然后用随机生成的合法表达式反复对比两份程序的输出。表达式生成器可以很简单随机生成若干个 1 到 9999 的数字数字之间随机插入或*。跑个几百组之后如果两边输出完全一致基本可以确认你的逻辑没有漏洞。对拍这件事在竞赛里的价值极高尤其是这类边界多、样例弱的模拟题。5.3 调试时的三个实用小技巧第一个技巧在每次结算时打印中间状态。比如单栈法里在分支打印term和sum的当前值你立刻能看出是乘积项算错了还是累加算错了。第二个技巧把长表达式切成短表达式分别测。如果 20 个字符的表达式结果不对就砍成 10 个字符再测不断二分很快能定位到出错的那一步。第三个技巧用模数的特殊性质做自检。因为 10000 是 10 的 4 次方任何结果的最后四位数字就是答案。所以你也可以先不用取模手工算出完整结果然后直接看后四位用来对照你的程序输出。这个方法在调试小样例时特别快不用真的去算一个巨大的数。6. 从这道题往远处走几个值得动手的扩展方向把这道题做出来只能算入门真正能拉开差距的是它衍生出来的那些变种。我按难度从低到高列几个方向建议你逐个动手试一遍每一个都会让你对表达式的理解更深一层。第一个扩展是加入减号。减号的处理难点在于它既可以当二元运算符又可以当一元负号比如1*-2或者表达式开头就是-5。我处理一元负号的常用办法是在解析数字之前检查符号位把这个符号直接乘到数字上也有选手在开头补一个0把一元负号统一转化成二元减法。这两种做法各有取舍补0的做法代码更少但会改变表达式结构前置符号检查更通用但要处理(-这种组合。第二个扩展是加入括号。这时候单栈法基本失效你必须上双栈法或者递归下降。双栈法的改动是遇到左括号直接入运算符栈它的优先级设为最低保证不会被弹出遇到右括号则不断结算直到弹出左括号。递归下降的改动更优雅在factor规则里如果遇到左括号就递归调用expr并吃掉右括号。我个人倾向递归下降因为它完美体现了括号就是递归这个直觉。第三个扩展是加入除法。这里有个非常值得警惕的坑模数 10000 不是质数不能直接套逆元。10000 分解成 2^4 × 5^4所以在做除法之前你得先把分子分母里的 2 和 5 的因子全部提出来单独处理剩下的部分才有逆元。这个技巧在组合计数题目里非常常见但放在表达式求值里就很反直觉——你会遇到明明除法应该在模意义下做却因为模数不互素而无法直接求逆的困境。这也是我建议你把这道题当作取模性质的入门案例来研究的原因取模远不止加个%这么简单。第四个扩展是超长数字的高精度处理。这道题用取模绕过了大数问题但如果题目要求输出完整结果不做取模你就必须上高精度乘法。高精度的实现关键是把数字按位拆成数组模拟手算的竖式乘法并且要注意进位。我写过一版核心就是一个双重循环加一个进位处理但边界条件比如乘完之后的最高位进位、结果的前导零相当琐碎建议在真正需要的时候再动手不要为了炫技提前引入。第五个方向稍微抽象一点把它当成一个极简的编译器前端练习。完整的表达式解析流程是词法分析切 token→ 语法分析建树或直接求值→ 语义动作计算。这道题因为语法太简单三个阶段的界限很模糊但如果你把自己的代码按这个框架重新组织一遍——先切出 token 数组再用递归下降从 token 数组构建求值——你会发现代码的可维护性显著提升也更容易扩展到更复杂的语法。这种提前一步做正确设计的习惯在写小题目的时候可能显得多余但在写大程序的时候是救命的。我个人做完这道题之后最大的收获其实不是学会了栈而是学会了一件事有几种做法要清楚每种做法牺牲了什么换来了什么。单栈法牺牲了通用性换来了简洁双栈法牺牲了简洁换来了可扩展递归下降牺牲了显式控制换来了语法上的自洽。你在真实项目里做技术选型的时候判断逻辑和这个是同一套。