自定义公式计算器解析表达式时如何处理运算符优先级？

Question

在实现自定义公式计算器时，一个常见问题是：如何正确处理包含多级优先级运算符（如加减乘除、括号、幂运算）的表达式解析？例如，表达式 "3 + 5 * 2" 应先算乘法，但若按从左到右顺序解析则结果错误。许多开发者采用简单的递归下降或正则分割方式，导致无法准确体现运算符优先级。更复杂的情况如嵌套括号和右结合的幂运算（如 2^3^2）进一步加剧了解析难度。如何设计语法分析器，使不同优先级的运算符按正确顺序求值，是构建可靠公式引擎的核心挑战之一。

Answer 1

一、问题背景与挑战概述

在构建自定义公式计算器时，最核心的技术难点之一是表达式解析。尤其是当表达式包含多级优先级运算符（如加减乘除、括号、幂运算）时，若处理不当，会导致计算结果严重偏差。

例如，表达式 "3 + 5 * 2" 的正确结果为 13，而非按从左到右顺序计算的 16。这要求系统必须识别并遵循标准数学运算优先级规则。

更复杂的场景包括：

• 嵌套括号：((2 + 3) * (4 - 1))
• 右结合的幂运算：2^3^2 = 2^(3^2) = 512，而非 (2^3)^2 = 64
• 函数调用与变量引用：sin(x + 1) * 2

这些问题暴露了简单正则分割或线性遍历方法的局限性，亟需一套结构化的语法分析机制。

二、常见错误实现方式及其缺陷

实现方式	典型做法	主要缺陷
字符串分割 + 线性扫描	使用 split 按操作符切分，再逐个处理	无法体现优先级，易出错
正则提取所有数字和符号	通过正则匹配 token 流后直接计算	缺乏语法树结构，难以扩展
递归下降无优先级控制	每个非终结符对应一个函数，但未分层	左递归导致栈溢出，优先级混乱

三、由浅入深：表达式解析的进阶路径

1. 词法分析（Lexing）：将输入字符串拆分为 Token 序列，如 NUMBER、PLUS、TIMES、LPAREN 等。
2. 语法分析（Parsing）：基于上下文无关文法构建抽象语法树（AST），体现运算结构。
3. 优先级处理：采用“递归下降 + 优先级分级”或“Pratt解析器”技术区分不同层级运算。
4. 结合性控制：对 ^ 运算符设置右结合，+、* 设置左结合，确保语义正确。
5. 语义动作执行：遍历 AST，递归求值，支持变量绑定与函数调用。

四、推荐解决方案：Pratt 解析器（自顶向下运算符优先级解析）

Pratt 解析器（也称 TDOP, Top-Down Operator Precedence）由 Vaughan Pratt 在 1973 年提出，特别适合表达式解析场景。

其核心思想是为每个 token 定义两个函数：

• nud()（Null Denotation）：前缀上下文行为，如负号 -5
• led(left)（Left Denotation）：中缀/后缀行为，如 a + b

同时维护一个绑定强度（binding power）来控制优先级。

五、代码示例：JavaScript 实现简易 Pratt 解析器

function createParser() {
    let tokens = [];
    let pos = 0;

    function token(type, value) {
        return { type, value };
    }

    function tokenize(input) {
        const regex = /\d+(\.\d+)?|\+\+|\*\*|[-+*/(),^]/g;
        const result = [];
        let match;
        while ((match = regex.exec(input))) {
            let type = 'NUMBER';
            if (match[0] === '(') type = 'LPAREN';
            else if (match[0] === ')') type = 'RPAREN';
            else if (['+', '-'].includes(match[0])) type = 'INFIX';
            else if (['*', '/'].includes(match[0])) type = 'INFIX';
            else if (match[0] === '^') type = 'POWER';
            result.push(token(type, match[0]));
        }
        return result;
    }

    function parseExpression(rbp = 0) {
        let left = tokens[pos++].nud();
        while (pos < tokens.length && rbp < tokens[pos].lbp) {
            left = tokens[pos++].led(left);
        }
        return left;
    }

    function infixOp(id, lbp, ledFn) {
        token('INFIX', id).lbp = lbp;
        token('INFIX', id).led = ledFn;
    }

    function setupTokens() {
        for (let t of tokens) {
            if (t.type === 'NUMBER') {
                t.nud = () => ({ type: 'literal', value: parseFloat(t.value) });
            } else if (t.type === 'LPAREN') {
                t.nud = () => {
                    const expr = parseExpression();
                    pos++; // skip RPAREN
                    return expr;
                };
            }
        }

        infixOp('+', 10, (left) => ({
            type: 'binary',
            op: '+',
            left,
            right: parseExpression(10)
        }));
        infixOp('*', 20, (left) => ({
            type: 'binary',
            op: '*',
            left,
            right: parseExpression(20)
        }));
        infixOp('^', 30, (left) => ({
            type: 'binary',
            op: '^',
            left,
            right: parseExpression(29) // 右结合：右侧优先级更低
        }));
    }

    return function parse(input) {
        tokens = tokenize(input);
        setupTokens();
        pos = 0;
        return parseExpression();
    };
}
    

六、AST 结构与可视化流程图

以表达式 3 + 5 * 2 为例，生成的 AST 如下：

{
  type: "binary",
  op: "+",
  left: { type: "literal", value: 3 },
  right: {
    type: "binary",
    op: "*",
    left: { type: "literal", value: 5 },
    right: { type: "literal", value: 2 }
  }
}
    

对应的 Mermaid 流程图表示如下：

graph TD
    A["+"] --> B[3]
    A --> C["*"]
    C --> D[5]
    C --> E[2]

七、高级特性支持建议

• 函数调用：扩展 nud 处理 IDENTIFIER 后接 '(' 的情况
• 变量环境：求值时传入 context 对象，支持动态绑定
• 错误恢复：添加位置信息与异常提示，便于调试
• 性能优化：缓存 AST 或编译为可执行函数
• 扩展文法：支持逻辑运算、三元表达式等

八、工业级实践参考

许多成熟项目采用类似架构：

• MathJS：JavaScript 数学库，内置强大表达式引擎
• ANTLR：通过 DSL 定义文法，生成高效解析器
• Esprima：JavaScript 解析器，可用于子集公式解析

对于高可靠性场景，建议结合形式化测试（如 property-based testing）验证解析正确性。