javascript - 将带有数学公式的字符串转换为对象树？

Question

我正在寻找一个函数来转换作为参数传递的数学字符串(使用操作 + 、 - 、 / 、 * )，它返回一个包含数学字符串片段的对象，以有序/更好的方式，更容易遍历。

输入的特征:

• 是一个包含公式的字符串
• 公式中没有= , 所以它不是一个等式
• 没有任何 float ，只有整数
• 整数可以是正数也可以是负数
• 没有像 x, y, z 这样的变量
• 可以包含括号

测试用例

例1:基础数学(同样的运算)

<表类="s-表"><头><日>N 输入(字符串)输出(对象)<正文>11 { values: [1], operation: null } 21+1 { values: [1,1], operation: "+" } 31+2+3 { values: [1,2,3], operation: "+" } 43-2-1 { values: [3,2,1], operation: "-" } 510*80 { values: [10,80], operation: "*" } 6100/10 { values: [100,10], operation: "/" }

示例 2:具有 2 个运算的公式

➡️ + 和 - 示例

N1

输入:1+1-1

输出:

{
    values: [
      {
        values: [1, 1],
        operation: "+",
      },
      1,
    ],
    operation: "-",
};

氮气

输入:3+2-1+5

输出:

{
    values: [
      {
        values: [
          {
            values: [3, 2],
            operation: "+",
          },
          1,
        ],
        operation: "-",
      },
      5,
    ],
    operation: "+",
};

N3

输入:3+2-1+5+10+7

输出:

{
    values: [
      {
        values: [
          {
            values: [3, 2],
            operation: "+",
          },
          1,
        ],
        operation: "-",
      },
      5,
      10,
      7
    ],
    operation: "+",
};

➡️ + 和/样本

N4

输入:1+2/3

输出:

{
    values: [
      1,
      {
        values: [2, 3],
        operation: "/",
      },
    ],
    operation: "+",
};

N5

输入:2/3+1

输出:

{
    values: [
      {
        values: [2, 3],
        operation: "/",
      },
      1,
    ],
    operation: "+",
};

N6

输入:1/2+3/4+5/6

输出:

{
    values: [
      {
        values: [1, 2],
        operation: "/",
      },
      {
        values: [3, 4],
        operation: "/",
      },
      {
        values: [5, 6],
        operation: "/",
      },
    ],
    operation: "+",
};

N7

输入:1/2/3/4/5+6+7+8/9+10/11

输出:

{
    values: [
      {
        values: [1, 2, 3, 4, 5],
        operation: "/",
      },
      6,
      7,
      {
        values: [8, 9],
        operation: "/",
      },
      {
        values: [10, 11],
        operation: "/",
      },
    ],
    operation: "+",
};

➡️/和 - 样本

N8

输入:1-2/3

输出:

{
    values: [
      1,
      {
        values: [2, 3],
        operation: "/",
      },
    ],
    operation: "-",
};

➡️/和 * 样本

N9

输入:10/2*5

输出:

{
    values: [
      {
        values: [10, 2],
        operation: "/",
      },
      5,
    ],
    operation: "*",
};

示例 3:具有 4 个运算的公式

N1

输入:10/2*5+1-1*5/3+2*4

输出:

{
    values: [
      {
        values: [
          {
            values: [
              {
                values: [
                  {
                    values: [10, 2],
                    operation: "/",
                  },
                  5,
                ],
                operation: "*",
              },
              1,
            ],
            operation: "+",
          },
          {
            values: [
              {
                values: [1, 5],
                operation: "*",
              },
              3,
            ],
            operation: "/",
          },
        ],
        operation: "-",
      },
      {
        values: [2, 4],
        operation: "*",
      },
    ],
    operation: "+",
};

示例 4:带 () 括号的公式

N1

输入:1+2*(3+2)

输出:

{
    values: [
      1,
      {
        values: [
          2,
          {
            values: [3, 2],
            operation: "+",
          },
        ],
        operation: "*",
      },
    ],
    operation: "+",
};

氮气

输入:(1+2*3)*2

输出:

{
    values: [
      {
        values: [
          1,
          {
            values: [2, 3],
            operation: "*",
          },
        ],
        operation: "+",
      },
      2,
    ],
    operation: "*",
};

N3

输入:(1/1/10)+1/30+1/50

输出:

{
    values: [
      {
        values: [1, 1, 10],
        operation: "/",
      },
      {
        values: [1, 30],
        operation: "/",
      },
      {
        values: [1, 50],
        operation: "/",
      },
    ],
    operation: "+",
  };

其他案例

N1

输入:-(1+2)

输出:

{
    values: [
      {
        values: [1, 2],
        operation: "+",
      },
    ],
    operation: "-",
};

...

Answer 1

这是一个似乎可以通过所有测试用例的函数。

不知何故，我编写了很多表达式解析器，最终我决定在几乎所有情况下都采用这种方式。这是 recursive descent与功能齐全的表达式解析器一样简单的解析器。

secret 是 parseTokens 函数的 minPrec 参数，它告诉它进行解析，直到遇到优先级较低的运算符。这使得函数可以轻松地在每个优先级递归调用自身。

/**
 * Parse an expression into the required tree
 * @param str {string}
 */
function parseExpression(str) {
    // break string into tokens, in reverse order because pop() is faster than shift()
    const tokens = str.match(/[.0-9Ee]+|[^\s]/g).reverse();
    const tree = parseTokens(tokens, 0);
    if (tokens.length) {
        throw new Error(`Unexpected ${tokens.pop()} after expression`);
    }
    return tree;
}

const BINARY_PRECEDENCE = {
    '+': 0,
    '-': 0,
    '*': 1,
    '/': 1,
}

const UNARY_PRECEDENCE = {
    '+': 10,
    '-': 10,
}

/**
 * Given an array of tokens in reverse order, return binary expression tree
 * 
 * @param tokens {string[]} tokens
 * @param minPrec {number} stop at operators with precedence smaller than this
 */
function parseTokens(tokens, minPrec) {
    if (!tokens.length) {
        throw new Error('Unexpected end of expression');
    }

    // get the left operand
    let leftToken = tokens.pop();
    let leftVal;
    if (leftToken === '(') {
        leftVal = parseTokens(tokens, 0);
        if (tokens.pop() !== ')') {
            throw new Error('Unmatched (');
        }
    } else if (UNARY_PRECEDENCE[leftToken] != undefined) {
        const operand = parseTokens(tokens, UNARY_PRECEDENCE[leftToken]);
        if (typeof operand === 'number' && leftToken === '-') {
            leftVal = -operand;
        } else if (typeof operand === 'number' && leftToken === '+') {
            leftVal = operand;
        } else {
            leftVal = {
                operation: leftToken,
                values: [operand]
            }
        }
    } else {
        leftVal = Number(leftToken);
        if (isNaN(leftVal)) {
            throw new Error(`invalid number ${leftToken}`);
        }
    }

    // Parse binary operators until we hit the end or a stop
    while (tokens.length) {
        // end of expression
        const opToken = tokens.pop();
        const opPrec = BINARY_PRECEDENCE[opToken];
        if (opToken === ')' || (opPrec != undefined && opPrec < minPrec)) {
            // We have to stop here.  put the token back and return
            tokens.push(opToken);
            return leftVal;
        }
        if (opPrec == undefined) {
            throw new Error(`invalid operator ${opToken}`)
        }

        // we have a binary operator.  Get the right operand
        const operand = parseTokens(tokens, opPrec + 1);
        if (typeof leftVal === 'object' && leftVal.operation === opToken) {
            // Extend the existing operation
            leftVal.values.push(operand);
        } else {
            // Need a new operation
            leftVal = {
                values: [leftVal, operand],
                operation: opToken
            }
        }
    }
    return leftVal;
}