简介这是一份面向编程学习者与开发者的字符串表达式求值示例程序聚焦如何将“23*4”“(23)*4”之类的字符串安全解析并计算出结果。资源围绕词法分析、语法分析、操作符优先级、括号匹配、递归下降解析和逆波兰表示法等核心知识点通过一个可运行的C工程演示了基于栈的表达式求值算法与常见异常处理思路适合正在学习编译原理、数据结构或准备相关课程设计的人群参考。压缩包共7个文件核心是一个cpp源代码文件配套dsp、dsw、ncb、plg、opt等Visual C工程辅助文件以及一个说明txt文档整体仅10KB结构精简、便于快速查看核心实现。目前已有325人学习下载。借助这份代码读者可以对照理解表达式解析流程、栈在求值中的用法、括号匹配与运算符优先级控制并据此扩展出计算器、命令行表达式工具或脚本解释器中的类似功能。1. 表达式字符串求值一场从符号到数值的翻译如果有人问我输入一个字符串表达式计算其值这类的代码包到底在解决什么问题我的回答通常是它解决的是中缀表达式与计算机执行模型之间的鸿沟。人写(2 3) * 4脑子里按括号和优先级自动排序但计算机从左往右扫这串表达式字符串时如果不做任何处理只会得到顺序计算出错的荒谬结果。表达式求值领域最常用的落地路径有两条调车场算法配后缀栈求值以及递归下降解析。这两条路覆盖了从简单四则运算计算器到带函数、变量和条件分支的公式引擎的绝大多数需求。下面的实现可以直接抄进自己的项目每一步会讲清楚为什么这么做以及参数怎么调。2. 字符串表达式解析token 化与调车场算法的优先级处理2.1 中缀表达式为什么不能顺序求值顺序求值悖论来自两个机制运算符优先级*高于和括号对运算顺序的强制覆盖。任何求值方案都必须显式处理这两者区别只在于处理时机。拿8 / 4 * 2举例按数学惯例从左往右算结果是 4但如果某个计算器把*的优先级定得比/高结果就会变成 1。这个例子说明优先级表本身就是语义的一部分不同业务场景可能给出不同定义必须做成显式配置。后缀表达式Reverse Polish Notation把运算符放到操作数之后3 4 * 2变成3 4 2 * 。此时遇到运算符就弹出最近的两个操作数成为唯一规则优先级和括号都被折叠进排列顺序里。把中缀转换成后缀的这个阶段就是调车场算法的用武之地。先转换再求值的两段式设计能让每一步的错误定位更清晰转换阶段报括号错误求值阶段报操作数错误互不混淆。2.2 先做词法分析用正则切出 token 流所有解析都从读字符串开始。我不推荐逐字符手写状态机——正则表达式配合re.match就足够覆盖四则运算加括号的场景代码短且不易出错import re TOKEN_PATTERN re.compile(r\s*(?Pnumber\d(?:\.\d)?|\.\d)|(?Pop[\-*/^()])) def tokenize(expr): tokens [] pos 0 while pos len(expr): m TOKEN_PATTERN.match(expr, pos) if not m: raise ValueError(f无法识别的字符: {expr[pos]!r} (位置 {pos})) if m.group(number) is not None: tokens.append((num, float(m.group(number)))) else: tokens.append((op, m.group(op))) pos m.end() return tokens这个切分器有两个关键参数值得说明。一是\s*放在每轮匹配开头负责吃掉数字或运算符之间的空白所以1 2和12得到完全相同的 token 流表达式字符串的格式宽容度在这里确定。二是数字和运算符放进不同的命名组后续无论是调车场还是递归下降都能直接靠token[0]判断类型。float()转换意味着1.5、.5两种写法都被接受如果你要禁止.5这类省略整数部分的形式删掉\.\d分支即可。词法分析阶段最容易漏掉的场景是空表达式。tokenize()返回空列表这个情况不要在 tokenizer 里报错留给求值器统一处理。原因在于错误分层tokenizer 只负责字符级错误语义级错误交还给上层这样调用方捕获异常时能根据阶段快速定位。TOKEN_PATTERN中的[\-*/^()]是运算符白名单新增运算符比如%要同步修改这里和后面的优先级表。2.3 调车场算法两个栈与一张优先级表调车场算法由 Dijkstra 提出思路是用一个输出队列和一个运算符栈把中缀重排为后缀。规则如下数字直接进输出队列左括号压入运算符栈右括号持续弹栈直到遇到左括号弹出的运算符进输出队列普通运算符先弹出栈顶所有优先级不低于自己的运算符再压栈优先级表和结合性设置如下运算符优先级结合性-1左结合*/%2左结合^3右结合结合性为什么重要2 ^ 3 ^ 2按数学约定等于2 ^ (3 ^ 2)即 512。如果全部按左结合处理调车场会输出2 3 ^ 2 ^求值得到(2^3)^2 64结果直接错。右结合运算符弹出栈顶的条件必须改为栈顶优先级严格大于当前运算符PRECEDENCE {: 1, -: 1, *: 2, /: 2, %: 2, ^: 3} RIGHT_ASSOC {^} def shunting_yard(tokens): output [] ops [] for kind, val in tokens: if kind num: output.append((num, val)) elif val (: ops.append(val) elif val ): while ops and ops[-1] ! (: output.append((op, ops.pop())) if not ops: raise ValueError(括号不匹配多余的右括号) ops.pop() else: while ops and ops[-1] ! (: if val in RIGHT_ASSOC: if PRECEDENCE[ops[-1]] PRECEDENCE[val]: break else: if PRECEDENCE[ops[-1]] PRECEDENCE[val]: break output.append((op, ops.pop())) ops.append(val) while ops: if ops[-1] (: raise ValueError(括号不匹配多余的左括号) output.append((op, ops.pop())) return output弹出条件是这段代码最容易被改错的地方。以左结合为例ops[-1]是栈顶旧运算符val是新到的运算符旧运算符优先级不低于新运算符时弹出相当于把已经可以结算的运算符先排出去。拿1 2 * 3走一遍*到达时栈顶是优先级 2 不低于 1所以不弹*压栈最终输出1 2 3 * 。而1 * 2 3中到达时栈顶*的优先级 2 高于 1弹出最终输出1 2 * 3 。两个方向都验证过这个实现才算是可靠的。2.4 递归下降解析什么时候比调车场顺手调车场算法不是唯一解。递归下降把文法规则直接翻译成函数调用表达式拆成 term乘除、factor数字、括号、一元负号每个优先级对应一层函数def parse_expression(tokens): node parse_term(tokens) while tokens and tokens[0] (op, ) or tokens and tokens[0] (op, -): op tokens.pop(0) right parse_term(tokens) node (op[1], node, right) return node处理一元负号和函数调用时递归下降天然支持不需要像调车场那样额外补丁。代价是代码结构更长每增加一个优先级就要多一层函数运算符一多嵌套层次就深。我一般这样选只做四则运算加括号用调车场代码短且状态少要做公式引擎后面要接函数、变量、比较运算直接上递归下降。两者在性能上没有实质差异——表达式求值是毫秒级任务真正的决策点是语法还要扩展多少。3. 后缀表达式的栈求值从 token 流到数值3.1 求值循环的不变量与弹出顺序后缀表达式求值比转换简单得多从左到右扫描数字压栈运算符弹出栈顶两个数字计算后压回。这里有一个容易忽视的细节弹出顺序。a b -在栈中先弹出来的是b后弹出来的是a所以减法和除法必须写成a - b、a / b写反了结果就错。我自己踩过这个坑当时8 2 /算出 0.25排查半天才发现是 lambda 里参数顺序写反了。整个循环维持一个不变量栈中任意时刻的元素都是已经就绪、等待参与后续运算的操作数。这个不变量也解释了为什么后缀求值不需要回头看——运算符到达时它的两个操作数必然已经全部入栈这是中缀转后缀阶段保证过的。一旦违反这个不变量比如表达式字符串是1 求值器会在取第二个操作数时发现栈空此时抛出的错误信息应当直接指向操作数不足。3.2 完整实现运算符表、求值器与错误分层import math OPERATORS { : lambda a, b: a b, -: lambda a, b: a - b, *: lambda a, b: a * b, /: lambda a, b: a / b, %: lambda a, b: math.fmod(a, b), ^: lambda a, b: a ** b, } def eval_postfix(postfix): stack [] for kind, val in postfix: if kind num: stack.append(val) continue if len(stack) 2: raise ValueError(f表达式不完整运算符 {val} 缺少操作数) b stack.pop() a stack.pop() stack.append(OPERATORS[val](a, b)) if len(stack) ! 1: raise ValueError(表达式不完整存在未使用的操作数) return stack[0] def evaluate(expr): tokens tokenize(expr) postfix shunting_yard(tokens) return eval_postfix(postfix)eval_postfix里的两个检查值得展开。len(stack) 2拦截了1 这类操作数不足的表达式len(stack) ! 1拦截了 token 流里存在多余操作数的情况这在调车场正常输出时不会发生但如果你后续扩展了手动构造后缀表达式的接口这个检查就是安全网。OPERATORS表把运算实现与解析逻辑解耦新增一个//整除运算符只需加一行字典项。再强调一个原则绝不直接对表达式字符串调用 Python 内置的eval()。eval(__import__(os).system(whoami))能执行任意系统命令这在任何面对用户输入的场景里都是致命的远程代码执行漏洞。自己写解析器不只是学习价值更是安全底线。上面的实现把evaluate的输入限制在数字、运算符和括号天然免疫注入攻击。3.3 取模语义与浮点精度运算符表里的细节上面%用的是math.fmod而不是 Python 内置的%。Python 的%对负数的语义是向下取整-7 % 3返回 2而大多数计算器语义是截断取余-7 % 3返回 -1。表达式求值器面向通用计算场景用math.fmod更符合用户对计算器的预期。如果业务需要 Python 语义把%映射改成lambda a, b: a % b即可这一行就是取模策略的切换点。浮点精度是另一个隐藏问题。0.1 0.2在 IEEE 754 下得到0.30000000000000004如果你的业务对精度敏感比如金额计算需要在求值器外围做好结果格式化或者在 tokenize 阶段改用decimal.Decimal保存数字。Decimal 方案会拖慢计算速度但表达式求值本身就是小规模运算性能代价完全可接受。我的建议是普通计算器用 float涉及钱的场景直接上 Decimal不要试图用 round 补救。4. 表达式字符串的边界问题与容错设计4.1 非法输入的分层防御表达式求值器最容易在边界输入上崩。下面是实际使用中高频出现的场景和预期行为输入预期行为或 抛空表达式1 抛运算符缺少操作数(1 2抛括号不匹配1 2抛连续运算符1 / 0抛自定义的 DivisionByZeroError1 2 3抛存在未使用的操作数前四类大部分能被现有代码拦截但1 2值得单独讨论tokenizer 不会报错因为是合法字符调车场也不会报错因为两个连续运算符会按优先级规则正常压栈出栈直到eval_postfix第二次遇到时栈里只剩一个操作数才抛出运算符缺少操作数。这条错误信息能定位问题但不够直观。常见做法是在 tokenizer 阶段追加一个相邻 token 检查def validate_no_consecutive_ops(tokens): for prev, cur in zip(tokens, tokens[1:]): if prev[0] op and cur[0] op and prev[1] ! ) and cur[1] ! (: raise ValueError(f连续运算符: {prev[1]} {cur[1]})这个检查要放在一元负号处理之后否则-3 2会被误判为连续运算符。顺序很重要先做一元负号的 0 补丁再做连续运算符校验才能同时兼容-3和1 2两种场景。4.2 除零用自定义异常不要在底层裸抛1 / 0在 Python 里会产生ZeroDivisionError但如果上层调用方是计算器 UI用户看到 Python 堆栈没有意义。常见做法是定义业务异常层次把底层的数值错误翻译成业务可读的提示class EvalError(Exception): pass class DivisionByZeroError(EvalError): pass def safe_div(a, b): if b 0: raise DivisionByZeroError(f除数为零: {a} / {b}) return a / b把OPERATORS里的/映射改成safe_div除法错误就有了统一出口。比ZeroDivisionError更需要警惕的是0.0 / 0.0——Python 不抛异常而是返回nan。这个值进入后续计算后整个表达式会静默变成nan且不产生任何错误信号是线上最难排查的问题。建议在eval_postfix返回前追加检查结果若是math.isnan(result)或math.isinf(result)统一抛EvalError。4.3 一元负号处理给 token 流打补丁-3 2和2 * (-3)是调车场算法最经典的边界。直接套用现有规则-会被当作二目减法处理-3缺少左操作数必然报错。业界最常见的补丁是把一元负号解释成0 - x在 tokenizer 阶段如果-出现在表达式开头、左括号之后或另一个运算符之后就在它前面插入一个数字 0。def tokenize_with_unary(expr): tokens tokenize(expr) result [] prev None for kind, val in tokens: if val - and (prev is None or prev[1] in (*-/^): result.append((num, 0.0)) result.append((op, -)) else: result.append((kind, val)) prev (kind, val) return result补丁之后-3 2变为0 - 3 2调车场不需要任何改动。代价是每个一元负号多引入一次减法运算对性能无实质影响。prev[1] in (*-/^的判断条件决定了哪些位置的一元负号会被识别如果你打算把函数调用也接进来左括号之后的情况已经涵盖在此。另一种更正规的做法是在语法树层级处理一元运算符适合递归下降方案调车场方案下补丁式处理是性价比最高的选择。5. 扩展求值器函数调用与回归验证5.1 给表达式加函数从 tokenizer 和运算符表两头动手把sqrt(16)这类函数调用接进来是公式引擎最常见的要求。tokenizer 需要先识别函数名在现有正则里增加一个[a-zA-Z_]\w*分支匹配到的函数名单独作为一种 token 类型。然后把它压入运算符栈遇到右括号弹出时如果栈顶是函数名就把从函数名到括号内的参数序列作为一个整体处理。更简洁的替代方案是把函数调用挂在求值阶段tokenizer 输出函数名后求值器遇到函数名 token 时解析其后的括号参数。函数实现在FUNCTIONS字典中注册FUNCTIONS { sqrt: math.sqrt, abs: abs, log: math.log, min: min, max: max, }函数名直接映射到 Python 内置函数或math模块函数省去重复实现。注意函数参数个数要固定可变参数的函数在表达式语言里调试成本高。例如log如果允许第二个参数做底数签名会变得难以在 token 流里描述建议先用单一签名等业务真的需要再加。5.2 用断言构造回归测试集不必引入测试框架表达式求值器的回归测试不需要 pytest一组assert就够了。这套断言集就是你的体检CASES [ (1 2 * 3, 7.0), ((1 2) * 3, 9.0), (2 ^ 3 ^ 2, 512.0), (-3 2, -1.0), (7 % 3, 1.0), (8 / 2, 4.0), (2 * (-3), -6.0), ] for expr, expected in CASES: result evaluate(expr) assert abs(result - expected) 1e-9, f{expr} {result}, expected {expected}2 ^ 3 ^ 2是右结合性回归用例-3 2和2 * (-3)是一元负号的两个位置回归用例。浮点比较永远不要用统一用绝对误差阈值1e-9。等扩充了函数支持把sqrt(16)、abs(-3)加进 CASES 末尾每次改动解析器后跑一遍这个文件就能确认新功能没有破坏旧的求值行为——表达式求值器这类基础组件回归验证越早做后面接业务逻辑时心里越有底。本文还有配套的精品资源点击获取