字符串表达式运算某高校机试真题字符串表达式运算这个题目国内但凡以算法考核为主的机试几乎都绕不开它。我印象里某高校的机试就出过一道很典型的题目输入一个只包含数字、加减乘除和括号的字符串表达式要求计算出它的结果并且要考虑运算优先级、括号嵌套、多位数、负号、空格等一系列细节。题目本身不难但能在半小时内写出鲁棒、简洁、能在边界用例下不翻车的解真得靠平时扎实的基本功。这篇文章我就完整拆解这道题从思路演到最终代码再到测试用例和机试时常见的坑一步步带你把这道题吃透。适合看这篇内容的读者主要是两类一类是准备机试、面试、算法竞赛需要刷“字符串处理 栈”这个高频考点的同学另一类是平时写代码不太注意边界情况、总被表达式校验搞到崩溃的开发者。我会尽量把每一步的“为什么”都讲清楚而不是直接扔一段代码让你背。1. 题目解读与整体设计思路1.1 核心需求解析先来看这道题最朴素的表述给定一个字符串里面包含非负整数、加减乘除 - * /、括号( )偶尔还会混入空格要求你计算这个表达式的结果。比如输入2*(34)-5/2输出12.5输入 1 2 输出3。但机试题目从来不会只考这么一句。真实的考核点藏在题目细节里表达式里的数字可能是多位数比如123*45而不是只有个位数。可能有嵌套括号比如((12)*(34))。可能存在负数比如-35或1(-2*3)题目有时会明确说支持负号有时不说但测试用例里藏着。可能有空格甚至全角空格如果系统输入是中文环境。可能输入为空字符串或只含空格。可能除数为零这需要明确约定通常题目会给约定不给我们就要按浮点数处理或者抛错。可能括号不匹配或者运算符连续34题目可能没有明说但考验你的防御性编程能力。这其实就是真实机试中“字符串运算”类题目的完整画像。它的核心难点不是“计算”本身而是“解析”——你要把一个扁平结构的字符串按数学规则转换为计算机内部的数据结构栈或树再按规则计算。1.2 为什么栈是这类问题的不二选择遇到表达式求值最常见的两种方案是双栈法操作数栈 运算符栈和递归下降解析法把表达式看作是递归定义的文法。还有一个经典做法是把中缀表达式转成后缀表达式逆波兰式再求值。对于机试场景双栈法是性价比最高的方案。原因有三它不需要构建额外的 Expression 树节点内存占用小遍历次数也少。它天然支持括号、优先级、多位数不需要像递归下降那样为每个文法规则写函数。它的代码量相对克制在一张A4纸的范围内能写完加上注释也就七八十行非常适合限时考核。递归下降解析其实也很优雅但它的工程复杂度更高尤其要处理带符号的一元负号时需要额外设计parseUnary()之类的逻辑。对于大多数机试场景杀鸡用牛刀反而容易写错。双栈法的核心思想可以拿“堆盘子”做类比你有一个放数字的盘子堆一个放运算符的盘子堆。碰到一个运算符时如果它比栈顶运算符优先级低或相同就把栈顶的运算符先“算掉”再把新运算符压栈。括号则像特殊标记见到右括号就把匹配的左括号之间的所有运算做完。这个过程保证了乘除永远优先于加减括号里的内容永远先完成。1.3 流程总览整个算法的处理顺序可以拆成 4 个阶段预处理去掉空格、统一符号。空格直接跳过就行不需要真的删除字符串遍历时if ch 就continue。数字解析遇到数字字符时连续读若干位直到遇到非数字把它拼成一个完整的整数或浮点数。这里千万不能只解析一位。运算符处理遇到 - * /根据优先级决定是否要先计算栈里的旧运算符然后把当前运算符压栈遇到(直接压栈遇到)则一直弹栈计算直到弹出对应的(。收尾清算表达式遍历结束后把操作数栈和运算符栈里剩余的部分全部计算完毕栈顶就是最终结果。这个流程本身很简单但里面暗藏很多细节接下来逐一展开。2. 双栈算法的核心细节与关键设计2.1 运算符优先级表的设计优先级是整个算法的灵魂。我们需要定义和-为一级优先级*和/为二级优先级。括号是特殊标记左括号只有在遇到右括号时才弹栈平时它就像一个屏障把左右两侧隔开。这里有个很多初学者会绕进去的地方两个同优先级运算符连续出现时到底谁先算比如8-3-2如果你不弹栈先压入减号再压入第二个减号最后从右往左算就变成了8-(3-2)7结果是错的。正确的是从左往右算(8-3)-23。所以代码里判断“如果栈顶运算符优先级大于等于当前运算符优先级就弹出栈顶并计算”这个“大于等于”是关键。我在代码里用一个函数返回运算符的等级def precedence(op): if op in (, -): return 1 if op in (*, /): return 2 return 0 # 括号当0处理有两个地方会用到它一是判断while是否继续弹栈二是在计算弹出栈顶运算符时确定运算方向。2.2 负数到底怎么处理负数是个极易翻车的点。题目里如果出现-32你直接在数字解析阶段就会卡住因为字符串第一个字符不是数字。我的处理方式分两种情况如果-是表达式的第一个字符或者它紧跟在一个运算符或左括号后面比如1*(-23)那么这个负号不是二元减法而是一元取负。处理方式是往操作数栈里压一个 0把表达式变成0-2这种形式再走正常的减法路线。如果-在两个操作数之间比如3-2它就是二元减法按普通运算符处理。这种“缺省补零”的技巧很实用它避免了你为负号专门写一套解析逻辑。同类问题还有正号比如32不过机试里这个场景极少见我一般只在代码注释里提一下。补零的思路也可以扩展如果题目支持“一元正号”你完全可以在同样位置补零或不处理直接跳过也行。2.3 括号匹配与弹栈时机括号处理是整个流程里最容易写出 bug 的地方。左括号(是直接无条件压栈的——它不参与任何优先级比较也无视栈顶的运算符。为什么因为括号意味着“新开一个计算区域”在遇到右括号之前栈内原有的高优先级运算符已经完成了它们该做的计算新栈内只积累括号里的运算符。当遇到右括号)时你的弹栈条件是while op_stack and op_stack[-1] ! (: # 弹出一个运算符弹出两个操作数计算结果压回操作数栈 ... # 弹出左括号 op_stack.pop()每次弹出一个二元运算符就从操作数栈弹出右操作数和左操作数注意顺序栈底是左边栈顶是右边所以先弹出的数字其实是右操作数。这个顺序如果在写代码时搞反了减法除法会瞬间全错而且很难排查。一个常见的防御性处理是如果遇到右括号时运算符栈里根本没有左括号栈为空或栈顶不是左括号说明表达式括号不匹配。有些机试环境不会给你保证这就可以直接抛异常或者返回错误码。我一般会加一个检查避免线上暴力测试直接崩掉。2.4 运算函数的设计与除法细节基本的四则运算函数很简单唯一要留心的是除法。机试通常有两种要求如果只要求整数结果用整数除法。这种情况下遇到5/2结果是2是向下取整还是向零取整要分语言。Python 里需要写int(left / right)来向零取整直接用//在-7/2这类场景会得到-4不符合数学直觉容易踩坑。如果要求浮点数结果全流程用浮点数。我习惯把所有数字都float()处理最终输出时再根据题目要求格式化。我在实际写的时候为了通用性统一采用浮点数计算最后如果结果跟整数相等就保留成整数形式输出如果不相等保留合适的小数位。有些题目会允许误差那就不必操心直接输出浮点数即可。def apply_op(op, a, b): if op : return a b if op -: return a - b if op *: return a * b if op /: if abs(b) 1e-12: raise ValueError(除以零) return a / b raise ValueError(未知运算符)3. 完整实现与机试现场实操3.1 一套可直接参考的完整实现我先给出一份 Python 版本的完整答案。选 Python 是因为它在机试中调试速度快、能迅速验证思路如果你用的是 C/C整个逻辑完全一样只需要把浮点数类型换成 double把栈用标准库替代即可。def calculate(expression: str) - float: # 去空格 统一处理负数 expression expression.replace( , ) n len(expression) i 0 nums [] ops [] def apply(): if len(nums) 2 or not ops: return op ops.pop() b nums.pop() a nums.pop() nums.append(apply_op(op, a, b)) while i n: ch expression[i] if ch.isdigit() or (ch - and (i 0 or expression[i-1] in (-*/)): # 处理负号缺省补零 if ch - and (i 0 or expression[i-1] in (-*/): nums.append(0.0) ops.append(-) i 1 continue # 解析多位数/小数 j i while j n and (expression[j].isdigit() or expression[j] .): j 1 nums.append(float(expression[i:j])) i j continue if ch in -*/: while ops and ops[-1] ! ( and precedence(ops[-1]) precedence(ch): apply() ops.append(ch) elif ch (: ops.append(ch) elif ch ): while ops and ops[-1] ! (: apply() if not ops: raise ValueError(括号不匹配) ops.pop() # 弹出左括号 i 1 while ops: apply() if len(nums) ! 1: raise ValueError(非法表达式) return nums[0]代码里有个细节值得注意ch - and (i 0 or expression[i-1] in (-*/)这个判断准确识别了负号出现的时机。它解决的是(-3)、1(-2*3)这类用例。如果题目明确不需要支持负数这个分支可以直接删掉代码还能短一截但我建议保留因为防御性编程在机试里永远不会扣分。3.2 关键步骤现场拆解我带你看一遍2*(34)-5/2这个表达式的完整计算过程你就明白为什么栈能保证优先级不出错。步骤读取字符操作操作数栈底→顶运算符栈底→顶12解析数字压栈[2][]2*栈顶无优先级更高的运算符直接压栈[2][*]3(压栈[2][*, (]43压栈[2, 3][*, (]5左括号在栈顶不弹压栈[2, 3][*, (, ]64压栈[2, 3, 4][*, (, ]7)弹取 3、4 得 7 压回弹出左括号[2, 7][*]8-*的优先级大于-先弹*取 2、7 得 14再压-[14][-]95压栈[14, 5][-]10/-优先级等于/不-优先级1小于/的2直接压栈[14, 5][-, /]112压栈[14, 5, 2][-, /]12结束弹/取 5、2 得 2.5弹-取 14、2.5 得 11.5[11.5][]最终结果是 11.5和手算完全一致。你仔细看第 8 步因为*优先级高于随后的-所以在压入-之前要把栈里的*先算掉。这是整个算法最精妙的一步也是所有双栈表达式的核心逻辑。3.3 机试环境下的边界测试用例有了代码紧接着要做的就是测试。机试没有在线调试器你必须养成写用例自测的习惯。以下是我每次写完这个题必测的list输入期望结果测试意图2*(34)-5/211.5常规混合运算12*37乘法优先级(12)*(34)21括号嵌套-352表达式开头负号1(-2*3)-5括号内负号10/2/51连续同优先级除法从左到右8-3-23连续同优先级减法方向2 3 * 414空格乱入123*4567856166多位数(12)*(34)/(2-1)21综合嵌套1/0抛异常或约定值除零防御输出格式方面如果题目没有额外要求11.5可以打印成11.5如果要求整数形式则必须判断小数部分是否为零做一次格式化再输出。这个小细节看起来不起眼但实际机试时因为输出格式不匹配被判错的人远比算法写错的人多。3.4 语言选型带来的微妙差异用 Python 写这个题有一个优势数字解析非常自然float()强转即可不用担心字符到数字的繁琐转换。但它也有坑比如float(1.2.3)会崩虽然我们的解析循环已经规避了连续两个小数点的问题但你写的正则在面对1.时是否也要容忍这个看题目要求通常机试不会出这种变态输入。如果换 C数字解析用stod配合substr会麻烦一点但控制力更强。操作数栈用std::vectordouble运算符栈用std::vectorchar性能也比 Python 好不少。不过在机试时间有限的情况下我强烈建议选择你最熟练的语言而不是选“理论上性能最好”的语言。提示无论你用哪门语言请在写完代码后立刻用上面的测试用例跑一遍。我见过太多人“感觉写对了”结果栽在第一步的边界检查上。4. 调试实录与常见问题速查4.1 我实测中踩过的几个真实大坑每次写这个题我都能在注释里发现至少一个容易忽略的陷阱。它们不是题目本身难而是“考虑不周”导致的全军覆没。第一坑括号里的栈管理混乱。有的同学在遇到左括号时也做了优先级比较直接导致1(2*3)里左括号后的2跑到外层表达式里去了。左括号就应该无条件压栈没有任何例外。它充当的是“保护墙”墙外的东西跟墙内的运算不产生交集。第二坑表达式结束后忘记清空栈。最典型的场景是123你的代码在循环里依次处理完1、、2、、3后ops栈里还有两个加号nums栈里有三个操作数。很多新手看到这里就返回nums[0]结果出来是1而不是6。收尾清算必须写到while ops:循环里。第三坑右括号弹出左括号后没有检查栈是否为空。如果输入是12)右括号前面没有左括号你如果直接把栈清空了再执行后面的步骤就会崩。防御性做法是遇到右括号时在弹栈前先检查栈里是否有左括号。第四坑除零判断遗漏。机试环境里如果输入是1/0你不做检查Python 会抛ZeroDivisionErrorC 会直接程序终止两种情况都会导致你的解答被当作运行错误处理。遇到这种情况要么题目约定输出特定值比如0、-1要么约定输入合法不包含除零否则你必须自己处理。4.2 常见问题速查表问题现象可能原因解决思路3-5-2结果为0而非-4同优先级运算符未弹栈从右往左计算了弹栈时用保证左结合12*3结果为9而非7只压栈不弹优先级更高的旧运算符压入前检查并弹出栈顶高优先级运算符(-32)解析失败负号没考虑一元场景在负号位置补0变成0-322*(34)结果出错左括号处理做了优先级比较左括号无条件压栈表达式末尾多一个运算符缺少合法性校验最终检查len(nums) 1小数输出格式不对未根据题目约定格式化先判断结果是否是整数再输出这张表基本覆盖了这个题八成以上的代码 bug。如果你写完代码先对照这张表自查一遍再去跑样例调试时间能省下一大半。4.3 机试现场的一些实战建议到了真实的机试环境时间是最大的敌人。我习惯的做法是先花两分钟画一个简单的流程草图甚至可以用注释在编辑器里写下来再动手写代码。写完之后绝不马上去看下一题而是先跑题目自带的样例再用自己补充的边界样例验证。机试系统通常只告诉你编译或者运行失败如果结果错误你只能自己靠肉眼找问题。还有一个小技巧先把表达式里的空格全去掉能够极大地降低调试难度。不去掉也完全可以但你在判断字符是否是数字时就得额外检查i n和expression[i].isdigit()组合逻辑麻烦一点。注意机试垂直难度不大但横向覆盖度很广。字符串表达式运算一般不会单独考而是隐藏在“简化路径”“基本计算器”“逆波兰式求值”这些变种题目里。掌握这道题的解法等于掌握了整个表达式家族的钥匙。5. 从这道题延伸出的变体与进阶5.1 支持变量与自定义函数如果你去刷更高级的题目会发现表达式运算有三个必然的变体方向变量替换、函数调用、逻辑运算。变量替换是最常见的延伸。题目可能给你一个dict里面存了x3, y4然后输入xy*2要求计算结果。这种情况下你只需要在数字解析阶段发现字母时去查表替换即可——前提是保证变量名不能和运算符冲突。实现时把当前读取到的连续字母序列作为一个变量名从表里取值再压栈。这个改造量很小但能体现出你对原算法的理解深度。函数调用则要复杂一点。比如输入max(1,2) 3你需要识别max关键字、括号参数、逗号分隔符。这个过程本质上是在做一次简易的 token 解析。我的建议是扩展运算符栈——把max视为一个特殊运算符在遇到)时不仅弹普通运算符还要识别函数运算符并单独处理。5.2 递归下降解析法作为第二方案双栈法虽然好但并不是唯一的答案。递归下降解析法在某些场景下反而更直观把表达式定义为文法规则然后用一组递归函数互相调用解析。它的好处是代码结构天然遵循“乘除优先于加减”的规则阅读性好扩展变量和函数也方便缺点是在机试的高压环境下递归函数的边界条件容易写漏。如果追求极致简洁还可以先转后缀表达式再求值。逻辑是先把中缀表达式扫描一遍按优先级输出到后缀队列然后用一个栈直接对后缀队列求值。本质上双栈法是“扫描一遍就地求值”后缀法是“扫描一遍转换 再扫描一遍求值”后者更容易调试和分步验证但时间上多了一次遍历。以机试的时间考量我还是推荐大家优先掌握双栈法。因为你只要理解透了变种题目只需要在压栈和弹栈条件上做微调即可不用改大框架。5.3 实战训练建议如果你想彻底吃透这道题我建议你用三种不同语言各写一遍并强制加上负数和空格支持。每一遍都是对思路的重塑用你最熟悉的语言写通目标是能完整跑通所有种子用例。换一种语言写你会被迫重新思考类型转换和字符串处理细节比如 C 的isdigit和stod的交互。最后去掉代码里的注释再默写一遍然后立刻用边界用例轰炸自己。这个过程看起来麻烦实际一晚上就能完成。经过这三遍字符串表达式运算这个考点基本就跑不出你的知识框架了。6. 收个尾我自己的一些体会我从第一次接触这道题到现在大概写过十几个版本从最早只支持个位数加减到后来支持小数、负数、变量、幂运算、函数调用每次重构都能发现新的边界。写这种题最爽的一点是它像一把解剖刀把“计算机如何理解数学表达式”这件事剥得清清楚楚。很多刚入门的同学会担心自己没接触过编译原理会不会看不懂双栈法其实完全不用担心。你只需要把“栈”理解成一个堆盘子的地方每当出现一个运算符就问问自己栈顶的东西是不是应该先算如果是就算如果不是就先留着。就这么简单。如果你在机试现场卡在字符串表达式上不妨深呼吸回到“栈 优先级”这两个关键词上。只要这两个点不乱代码再长也不怕。