简介面向编程初学者与算法学习者的字符串表达式求值实践资源围绕“输入表达式计算其值”的经典任务提供C语言实现的可运行工程。代码演示词法解析、语法分析、操作符优先级、括号匹配等关键环节并引入逆波兰表示法、基于栈的求值算法以及异常处理思路有助于在实践中掌握递归下降解析与栈的应用适合课程设计、OJ练习或面试算法复习时对照学习。压缩包共7个文件含主cpp源码、dsp/dsw工程配置和txt说明同时带有ncb/plg/opt等Visual Studio辅助文件整体仅10KB结构精简方便快速编译与调试。目前已有325人浏览学习虽然体积小巧但完整呈现了从字符串输入到结果输出的处理链路能帮助理解表达式求值的编译原理基础也可直接参考工程结构继续扩展更多运算规则与错误处理机制是一份小而精的入门素材。1. 字符串表达式求值先想清楚要算什么字符串表达式求值这个需求几乎每个做后台开发的人都撞到过前端传过来一个35*2要求在服务端算出13配置中心里放了一条rate 0.8 timeout 500需要解析成布尔值报表系统读到的公式SUM(A1:B3)*2得拆开逐段计算。这类问题在面试题里出现频率极高实际工程里也绕不开难点不在“把字符串变成数字”而在“让计算机理解运算顺序和括号嵌套”。本篇文章讲的就是这条完整链路怎么把一个字符串表达式拆成 token怎么处理运算符优先级怎么用栈完成中缀到后缀的转换与求值最后怎么把这段代码写成能放进生产环境的模块。适合正在写解释器、规则引擎或公式引擎的 Python 后端开发也适合准备算法面试、想搞懂“为什么两个栈能算表达式”的人。标题里那个.rar后缀不用管我们要做的事和压缩包无关——真正要解决的是一个字符串表达式的解析与计算问题。我用 Python 来做完整实现原因是它写起来最接近伪代码结构清晰方便你迁移到 Java、Go 或 TypeScript。下面从最底层的一步讲起。2. 词法分析把字符串拆成 token 序列的规则2.1 为什么第一步不是“直接算”很多初学的人拿到12*3第一反应是循环找运算符看见就算左边加右边。这个思路在只有加减法时勉强能走一旦出现乘法优先级、括号嵌套、负数循环遍历的代码立刻失控12*3如果从左往右算会得到9而不是正确答案7(12)*3需要先识别括号内部-35里的-到底是减号还是负号也无法区分。所以标准的做法分两段走先做词法分析lexical analysis把字符串切成一个个最小的语法单元也就是 token再做语法分析parsing根据 token 之间的运算关系计算值。切分这一步看似简单但规则必须明确数字可以由多位组成整数和小数都要支持运算符包括 - * /和括号空格应该完全忽略。import re def tokenize(expr: str) - list: 把表达式字符串拆成 token 列表tokens 为 (type, value) 元组 pattern re.compile(r\s*(?PNUM\d\.?\d*|\.\d)|(?POP[\-*/()])) tokens [] pos 0 while pos len(expr): m pattern.match(expr, pos) if not m: raise ValueError(f无法识别的字符: {expr[pos]!r}) pos m.end() kind m.lastgroup if kind NUM: tokens.append((NUM, float(m.group()))) else: tokens.append((OP, m.group())) return tokens print(tokenize(12.5 3 * (4 - 2))) # [(NUM, 12.5), (OP, ), (NUM, 3.0), (OP, *), (OP, (), (NUM, 4.0), (OP, -), (NUM, 2.0), (OP, ))]这段代码的正则\s*负责跳过空白字符\d\.?\d*|\.\d匹配整数和小数[\-*/()]匹配单个运算符。其中NUM和OP两个分组名通过lastgroup来判断当前匹配到了什么类型。需要注意和-在字符类里要写成\-否则会被正则解析成“范围”含义。这样切出来的 token 序列后续所有的解析逻辑都只面向列表操作不再碰原始字符串。2.2 数字与运算符的 token 类型设计token 类型的设计直接影响后续代码的复杂度。常见做法是把类型定义成两个常量即可但如果表达式系统要支持变量名、函数调用就得扩展成枚举。下面是一个适合字符串表达式求值的 token 类型设计token 类型含义示例NUM数值字面量统一转为 float3.14、42OP运算符或括号、-、*、/、(、)EOF表达式结束标记可选None对于纯四则运算的表达式NUM和OP两类就够用。但这里有一个值得一提的细节数值类型统一用float会引入精度问题工程上如果要算金额类数据建议使用decimal.Decimal替换 float 存 token 的 value算法验证阶段用 float 更方便。还有一个容易被忽略的点是词法分析阶段不需要检查括号是否匹配、运算符是否连续这些都是语法分析阶段的事——把责任分开出错时能直接定位到哪一层。2.3 词法分析最常见的三个坑切词阶段最常见的坑有三个。第一个是负数识别——-35中的-在 token 序列里只是一个OP真正区分“减号”和“负号”要等到语法分析时结合上下文判断在词法层强行区分会让正则变得复杂且容易出错。第二个是科学计数法1e3这样的写法在\d\.?\d*里无法匹配如果业务需要支持要扩展正则到\d(\.\d)?([eE][-]?\d)?。第三个是非法字符的报错信息——直接抛ValueError(无法识别的字符)时最好把位置pos一并带出去方便上层定位。提示不要把词法分析写得过于复杂。遇到新的字符类型先考虑它能不能归入NUM或OP再考虑新增类型。每多一种类型后续的优先级表和语法分析都要多处理一条分支。3. 中缀转后缀与栈式求值的标准做法3.1 为什么要引入后缀表达式人类习惯的中缀表达式1 2 * 3的问题在于运算符优先级和括号让计算顺序不直观。后缀表达式逆波兰表示法RPN把运算符写在两个操作数之后1 2 3 * 表达的是“先算 2 乘 3再加到 1 上”计算时只要从左往右扫描遇到数字就压栈遇到运算符就弹出两个数字运算再把结果压回栈——不需要回头看优先级也不需要处理括号一个栈就够。这种转换掉的是“可读性”换来的是“计算逻辑的极简”。转换本身有两种主流做法调度场算法Shunting-yard algorithm由 Dijkstra 提出和递归下降解析。调度场算法的思路更贴近栈的本质维护一个运算符栈数字直接输出到结果序列运算符根据优先级决定是压栈还是把栈顶弹出左括号特殊处理右括号会把栈里直到左括号的所有运算符全部弹出。递归下降则把表达式拆成“项 因子 (乘除运算符 因子)*”的递归规则本质上是通过函数调用栈来隐式保存优先级。我在工程里倾向于先用调度场算法因为它的状态转移清晰调试时打印两个栈就能看出每一步发生了什么而递归下降在表达式嵌套层次极深时有递归栈溢出的风险。下面的实现就是调度场算法的完整代码。PRECEDENCE {: 1, -: 1, *: 2, /: 2, (: 0, ): 0} def infix_to_postfix(tokens: list) - list: 中缀 token 列表转后缀 token 列表使用调度场算法 output [] op_stack [] for typ, val in tokens: if typ NUM: output.append((NUM, val)) # 数字直接输出 elif val (: op_stack.append(val) # 左括号无条件入栈 elif val ): while op_stack and op_stack[-1] ! (: output.append((OP, op_stack.pop())) if not op_stack: # 栈空了还没找到左括号 括号不匹配 raise ValueError(括号不匹配多余的右括号) op_stack.pop() # 丢掉左括号 else: # 普通运算符 while (op_stack and op_stack[-1] ! ( and PRECEDENCE[op_stack[-1]] PRECEDENCE[val]): output.append((OP, op_stack.pop())) op_stack.append(val) while op_stack: # 表达式结束弹空运算符栈 if op_stack[-1] (: raise ValueError(括号不匹配多余的左括号) output.append((OP, op_stack.pop())) return output tokens tokenize(1 2 * 3) print(infix_to_postfix(tokens)) # [(NUM, 1.0), (NUM, 2.0), (NUM, 3.0), (OP, *), (OP, )]这里有一个关键参数PRECEDENCE表中(的优先级设为 0这样循环里判断op_stack[-1] current时左括号永远不会被弹出自然地被挡在栈底。和-的优先级低于*和/所以2*3的*会先于出栈。输出序列中操作数的顺序完全保持原样只有运算符的位置发生了移动这保证了求值阶段做减法、除法时操作数的顺序不颠倒。3.2 后缀表达式的栈式求值实现后缀求值的代码比转换更简单一个数据结构就能完成。def evaluate_postfix(postfix_tokens: list) - float: 对后缀 token 序列求值返回 float 结果 stack [] for typ, val in postfix_tokens: if typ NUM: stack.append(val) else: try: b stack.pop() # 注意先弹出的是右操作数 a stack.pop() except IndexError: raise ValueError(表达式操作数不足) if val : stack.append(a b) elif val -: stack.append(a - b) # 用 a 减 b顺序不能反 elif val *: stack.append(a * b) elif val /: if b 0: raise ZeroDivisionError(除数为零) stack.append(a / b) if len(stack) ! 1: raise ValueError(表达式操作数过多检查是否缺少运算符) return stack[0] postfix infix_to_postfix(tokenize((1 2) * 3)) print(evaluate_postfix(postfix)) # 9.0取栈顶两个数字时b先弹出、a后弹出对应后缀表达式里“前面的操作数在前”所以减法必须是a - b除法必须是a / b。这个顺序如果不小心写反了5 3 -会算出-2而不是2而且不报错——逻辑错误比崩溃更难排查。最后检查len(stack) ! 1是为了捕获1 2 3这类多出一个数字的情况这种错误在转换阶段不会暴露只能在求值结束时发现。3.3 一个函数串起整条计算链路把 tokenize、infix_to_postfix、evaluate_postfix 接起来就是完整的字符串表达式求值入口。加上异常处理让调用方拿到的要么是数值要么是明确的错误信息。def eval_expr(expr: str) - float: 字符串表达式求值入口 if not expr or not expr.strip(): raise ValueError(表达式为空) tokens tokenize(expr) postfix infix_to_postfix(tokens) return evaluate_postfix(postfix) # 基本用法 for s in [12*3, (12)*3, 10/4, 1234, 3*4-8/2]: print(f{s} {eval_expr(s)})这段链路有两个可扩展点第一层是tokenize的输出格式只要保证后续函数能识别NUM和OP即可第二层是PRECEDENCE字典想要新增运算符时先在这里加一行再去evaluate_postfix里补运算逻辑。整个流程是流水线式的每一段都能单独测试复杂度被控制在了“每个函数只看一个栈”的范围内。4. 括号、一元负号与错误场景的处理4.1 支持括号嵌套与优先级扩展上面调度场算法已经原生支持任意层级的括号嵌套因为左右括号的处理逻辑是自包含的左括号入栈右括号弹出栈内元素直到遇到左括号。测试一组嵌套表达式可以验证cases [ ((12)*3), # 9.0 1(3*(45)), # 28.0 (12)*(34), # 21.0 ] for c in cases: print(f{c} {eval_expr(c)})如果未来要支持幂运算**或取模%需要做两件事在tokenize的正则字符类中加入运算符在PRECEDENCE表里设置优先级。幂运算比较特殊从数学规则来说它的结合性是右结合的2**3**2应该等于2**(3**2)也就是512但调度场算法里while ... PRECEDENCE[stack_top] PRECEDENCE[current]这种写法会先算前面的2**3得到64。要支持右结合循环里要把改成条件变为“只有栈顶优先级严格大于当前运算符时才弹出”。4.2 一元负号的两种处理方案-35和1-3这类表达式问题出在-出现在表达式开头或紧跟另一个运算符后面此时它不是二元的减号而是一元的取负号。处理方案有两种我在工程中常用的做法是先预处理 token 序列给一元负号包一层“负值”语义。第一种方案是在词法分析时直接区分发现-出现在表达式首字符或前一个 token 是OP时将其标记为NEG一元负号后续求值阶段对NEG单独处理。这种方案最干净但要求 token 类型多一个枚举值。def tokenize_with_negation(expr: str) - list: tokens tokenize(expr) result [] prev None for typ, val in tokens: if val - and (prev is None or prev[0] OP): result.append((OP, NEG)) # 标记为一元负号 else: result.append((typ, val)) prev result[-1] return result第二种方案更省事把-(x)替换成(0-x)即词法阶段直接把-3改写成0-3。代价是表达式变长但优先级问题自动解决——0-3是完全合法的二元减运算。def normalize_unary_minus(expr: str) - str: 把一元负号归一化为 0-x 形式 expr expr.replace((-, (0-) if expr.startswith(-): expr 0 expr # 处理 1-3、1--3 这类连续运算符的情况 expr re.sub(r([\-*/])-\(, r\1(0-, expr) expr re.sub(r([\-*/])-(\d), r\1(0-\2), expr) return expr print(eval_expr(normalize_unary_minus(1-3))) # -2.0 print(eval_expr(normalize_unary_minus(-35))) # 2.0两种方案没有绝对优劣第一种更快且不改变字符串适合高性能场景第二种实现直观适合快速开发。需要留意的是1--3这种连续负号的情况用文本替换很容易出错务必写几个边界测试用例兜底。图上用第一种方案示意表达式原始 token 序列处理后 token 序列-35OP(-) NUM(3) OP() NUM(5)OP(NEG) NUM(3) OP() NUM(5)1-3NUM(1) OP() OP(-) NUM(3)NUM(1) OP() OP(NEG) NUM(3)4.3 非法表达式能给出什么错误信息字符串表达式求值的用户是别的工程师错误信息决定了他能不能 10 秒内定位问题而不是把日志转发给你。我把生产环境里最常用的错误分类整理成一张表每种错误都在对应阶段抛出错误类型触发场景抛出阶段建议信息非法字符1a、23词法分析无法识别字符 a位置 2操作数不足1*2求值阶段操作数不足操作数过多1 2 3求值阶段操作数过多疑似缺少运算符多余右括号(12))中缀转后缀多余的右括号多余左括号(12中缀转后缀多余的左括号除数为零1/0求值阶段除数为零一个容易忽略的问题是空表达式和纯空白字符串。eval_expr( )会进入 tokenize 循环匹配不到任何 token返回空列表然后 infix_to_postfix 也返回空列表最后 evaluate_postfix 走进len(stack) ! 1报“操作数过多”——这个信息对用户是误导。所以入口函数的一开始就要显式检查空串这是我在生产代码里踩过的一个小坑。提示给异常加上阶段前缀比如[词法分析] 无法识别字符...用户看到前四个字就知道该去哪段代码里查。5. 工程化进阶从一次性脚本到可维护求值模块5.1 把三个函数收敛成一个可调用的类脚本阶段三个函数平铺没问题但要放进服务里复用一个类会更好管理——类的初始化只做一次PRECEDENCE定义每次调用eval时创建新的局部栈天然线程安全。这里给出一个落地版本的结构示意class ExpressionEvaluator: 字符串表达式求值器线程安全可重复使用 def __init__(self): self.precedence {: 1, -: 1, *: 2, /: 2, (: 0, ): 0} def eval(self, expr: str, unary_minus: bool True) - float: if not expr or not expr.strip(): raise ValueError(表达式为空) if unary_minus: expr normalize_unary_minus(expr) tokens tokenize(expr) postfix self._to_postfix(tokens) return self._evaluate(postfix) # _to_postfix 与 _evaluate 的实现同上一章略unary_minus参数用于开关一元负号处理。有些使用方明确不需要负号支持关闭后走原始路径逻辑更简单且多一层性能保障。这个开关式设计是我在封库时比较常用的手法——避免为一个“所有表达式都不含负号”的场景付出额外的预处理成本。5.2 性能度量这个求值器到底多快写一个timeit脚本来测试吞吐量是有意义的运营指标。“表达式求值”如果出现在对延迟敏感的路径上每毫秒都很重要。import timeit expr (1 2) * (3 4) / 2 - 5 eval_op ExpressionEvaluator().eval times timeit.repeat(lambda: eval_op(expr), number100000, repeat3) # 单次耗时约 3~8 微秒区间取决于 Python 版本和机器 print(f10 万次平均耗时: {times[0]/100000*1e6:.2f} 微秒/次)这个量级的性能已经可以覆盖绝大多数服务端场景。如果表达式来自不可信的客户端还有两件必须要做的事一是设置表达式最大长度比如 256 字符防止超长字符串拖垮正则引擎二是限制嵌套深度((((...))))深到几千层时会触发 Python 递归限制或栈溢出但调度场算法使用的是显式栈而不是递归天然免疫深度问题这也是我选它而不是递归下降的另一层理由。5.3 单元测试表达式求值器的验证清单最后提供一组拿来就能用的验证用例覆盖正常路径、边界路径和异常路径。我把它们按分类列出你直接抄进test_*.py里跑一遍结果与预期不符的就是代码里有隐蔽 bug比如减号顺序写反、括号不匹配时静默通过等类别表达式期望结果基本四则12*37.0括号优先(12)*39.0小数运算0.10.20.30000000000000004float 精度连续运算1-2-3-4.0除法取整7/23.5一元负号-352.0多层嵌套((12)*(34))21.0除数为零1/0抛ZeroDivisionError空表达式抛ValueError多余括号(12))抛ValueError其中1-2-3这一条值得特别说明它用来验证左结合性。如果后缀转换优先级处理正确1-2-3会被转成1 2 - 3 -求值结果是(1-2)-3 -4。如果某天你“优化”了调度场算法把条件写错这个用例立刻会变成1-(2-3)2结果差距极大一眼就能看出问题。本文还有配套的精品资源点击获取