2. 公式解析与抽象语法树

在“公式生成代码与计算结果校验”这条链路里，第一步永远是把人写的公式字符串变成机器能理解的结构。比如用户输入 (a+b)*2 - sin(x)/3，程序看到的只是一串字符；如果直接按字符顺序处理，就会把括号、优先级、函数调用全部搞乱。解析（parsing）的任务，就是把这串字符转换成一种带层次、带语义的树形结构——抽象语法树（Abstract Syntax Tree，AST）。后续的求值、化简、求导、生成代码、比对结果，几乎都建立在这棵树之上。

为什么需要 AST，而不是直接算

最朴素的做法是“边读边算”，但数学表达式天然具有嵌套和优先级。以 2+3*4 为例，若从左到右算得 20，正确结果应是 14。AST 把“先乘后加”这一语义固化成树形：根节点是加法，左子节点是 2，右子节点是乘法（3 和 4）。这样无论求值、改写还是序列化，都只需按树遍历，不必反复处理字符串。AST 还剥离了空格、多余括号等表层信息，只保留运算与操作数的本质关系，因此称为“抽象”。

一个典型的 AST 节点包含三类信息：节点类型（数字、变量、二元运算、函数调用等）、该类型的载荷（如运算符 +、函数名 sin、常量值），以及子节点列表。例如 a+b 对应一个 BinaryOp(op='+') 节点，左右子节点分别是变量 a 和 b。函数调用 sin(x) 则是 Call(name='sin')，子节点为 x。

表达式 (a + b) * 2 − sin(x) / 3 的抽象语法树 根节点为减法；乘法与除法优先级高于加减，括号提升加法层级 减法 − 乘法 × 除法 ÷ 加法 + 2 sin( ) 3 a b x 根运算 乘除 括号内加法 函数调用 常量 变量

运算符优先级与结合性

AST 的形状由两条规则决定：优先级（precedence）和结合性（associativity）。优先级决定“谁先结合”，结合性决定“同级从左还是从右”。常见数学约定中，函数调用与括号最高，其次是一元负号，再是乘除、加减，最后是比较与逻辑运算。结合性方面，加减乘除都是左结合，即 a-b-c 解析为 (a-b)-c；幂运算 a^b^c 通常是右结合，解析为 a^(b^c)。这一点在实现解析器时极易出错，必须显式约定。

工程上常用“优先级爬升”（precedence climbing）或递归下降来构造 AST。核心思路是：每层函数只处理自己这一优先级的运算符，遇到更高优先级就递归下沉。下面是一个极简的递归下降骨架，仅演示加减与乘除两层，帮助理解“层级如何变成树”：

# 伪代码：两层递归下降，返回 AST 节点
def parse_expr(tokens):        # 处理 + -
    node = parse_term(tokens)  # 先取一个更高优先级的项
    while peek(tokens) in ('+', '-'):
        op = next(tokens)
        right = parse_term(tokens)
        node = BinaryOp(op, node, right)   # 左结合：新节点成为父节点
    return node

def parse_term(tokens):        # 处理 * /
    node = parse_atom(tokens)  # 数字、变量、括号、函数调用
    while peek(tokens) in ('*', '/'):
        op = next(tokens)
        right = parse_atom(tokens)
        node = BinaryOp(op, node, right)
    return node

注意 parse_expr 中每次循环都把“已有节点”作为左子节点、新解析的项作为右子节点，这正是左结合的体现。若把幂运算写成右结合，则应在递归调用后再组装，顺序相反。括号的处理放在 parse_atom：遇到左括号就递归调用 parse_expr，再消费右括号，从而让括号内的低优先级运算“提升”为子树。

常见解析库：SymPy 与 Math.js

实际项目中很少从零手写完整解析器，更常见的是借助成熟库。SymPy 是 Python 的符号计算库，sympy.sympify("(a+b)*2 - sin(x)/3") 会直接返回 SymPy 表达式对象，它本身就是一棵可遍历的树，可用 expr.args 取子节点、expr.func 取节点类型。Math.js 是 JavaScript 生态的数学库，math.parse("(a+b)*2 - sin(x)/3") 返回 Node 树，节点带 type（如 OperatorNode、SymbolNode、FunctionNode），并支持 toString() 还原、compile() 求值、transform() 改写。

对比维度SymPy（Python）Math.js（JavaScript）
主要定位符号计算：化简、求导、积分、解方程数值计算与表达式解析，偏工程计算
解析入口sympify() / parse_expr()math.parse()
树节点访问expr.args、expr.funcnode.type、node.args
求值方式expr.subs(...).evalf()node.compile().evaluate(scope)
典型优势符号化简与精确有理数运算浏览器/Node 直接运行，单位与矩阵支持好

选择时看任务重心：若校验需要“化简后比对是否恒等”“求导验证”，SymPy 更合适；若公式要在前端即时求值、批量代入参数，Math.js 更轻便。两者都遵循标准优先级约定，但函数名、常量名（如 pi 与 pi）和隐式乘法的支持程度略有差异，跨库迁移时要重点核对。

解析前先做规范化：统一全角括号与运算符、去除多余空格、把 ^ 与 ** 约定为同一种幂运算。规范化不改变语义，却能显著减少解析失败。
不要用 eval() 直接执行用户公式。它无法控制优先级之外的语义，还存在注入风险；应走解析库生成 AST，再在受控作用域内求值。

掌握 AST 的结构与优先级规则后，下一步的求值、化简与结果比对才有可靠基础。建议在动手前先用一个小例子手绘树形，确认每个运算符的父子关系，再对照库返回的节点结构，这样能快速发现结合性约定不一致的问题。

← 上一章 📖 返回目录 下一章 →