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

zd287kbt 于 2023-01-01 发布在 Java

关注(0)|答案(2)|浏览(127)

- bounty将在7天后过期**。此问题的答案可获得+200声望奖励。stackdeveloper希望奖励现有答案：非常感谢@Matt Timmermans，我想奖励你更多

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

输入特性：

是包含公式的字符串
这个公式没有=，所以它不是一个方程
没有浮点数只有整数
整数可以是正的或负的
没有像x y z这样的变量
可以包含括号

测试用例

示例1：基础数学（相同操作）

| 数量|输入（字符串）|输出（对象）|
| - ------| - ------| - ------|
| 1个|1个|{ values: [1], operation: null }|
| 第二章|一加一|{ values: [1,1], operation: "+" }|
| 三个|1 + 2 + 3| { values: [1,2,3], operation: "+" }|
| 四个|三、二、一|{ values: [3,2,1], operation: "-" }|
| 五个|10 * 80| { values: [10,80], operation: "*" }|
| 六个|100/10| x1米10英寸1x|

示例2：2次运算公式

➡️ + and - samples

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: "+",
};

➡️ + and / samples

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: "+",
};

➡️ / and - samples

N8

输入：1-2/3
输出：

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

➡️ / and * samples

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: "-",
};

...

JavaScript

来源：https://stackoverflow.com/questions/74909107/convert-a-string-with-a-math-formula-to-an-object-tree

2条答案

按热度按时间

twh00eeo1#

这里有一个函数似乎通过了所有的测试用例。
我写了很多表达式解析器，最后我决定在几乎所有的情况下都这样做，这是一个recursive descent解析器，它就像一个功能齐全的表达式解析器一样简单。
秘密在于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;
}

赞(0）回复(0）举报 2023-01-01

cnwbcb6i2#

我将发布我的解决方案，这是基于这个答案类似的问题。
该解决方案基于一个正则表达式，该表达式使用命名的捕获组对输入进行标记化。因此，代码的其余部分不必处理字符比较，而可以专注于语法规则。该实现没有显示优先级规则的显式概念，因为它们是由语法隐含的。
我在此重复语法规则，但也可参见上述答案中的解释：

<literal>    ::= [ '-' ] <digit> { <digit> } [ '.' { <digit> } ] ; no white space allowed
<operator2>  ::= '*' | '/'
<operator1>  ::= '+' | '-'
<factor>     ::= '-' <factor> | '(' <expression> ')' | <literal>
<term>       ::= [ <term> <operator2> ] <factor>
<expression> ::= [ <expression> <operator1> ] <term>

在此，我将通过以下细节扩展该解决方案：

它生成树节点格式而不是嵌套数组
当多个操作数可以与同一个二元运算符组合时，它保持节点平坦
它解析双重否定：例如，-(-(1+2))将生成与1+2相同的树。

您可以在下面的代码片段中尝试不同的输入。
x一个一个一个一个x一个一个二个一个x一个一个三个一个