JavaScript -- 编写一个可以求解数学表达式的函数(无需 eval)

Question

最终我想拿这个:

2x + 3 = 5

求解 x，方法是首先从两边减去 3，所以 2x = 2，然后将两边除以 2，所以 x = 1。我想了很多应该如何在 JavaScript 中创建这样的函数，它可以返回按顺序完成的步骤数组，包括结果。显然，“eval”不会为此做任何事情，因此似乎必须重新创建方程式。

我最初的想法是首先忽略 X，并尝试创建一个可以求解简单方程的函数，而无需 eval 或任何内置函数。

我认为第一步是使用 .split 拆分术语，但我在这方面遇到了一些麻烦，因为我需要拆分 多个 符号。例如，假设我有一个要计算的简单表达式:3 - 6 * 3/9 + 5。因此，在我们进入操作顺序之前，将每个术语分开(并对它们进行分类)是困难的部分，这是我目前面临的主要具体问题。

我一开始只是一个接一个地拆分，但我遇到了一些问题，尤其是考虑到顺序。

function solve(eq) {
    var minuses = eq.split("-"),
            pluses = minuses.map(x=> x.split("+")),
            timeses = pluses.map(x=>x.map(y=>y.split("*"))),
      dividers = timeses.map(x=>x.map(y=>y.map(z=>z.split("/"))));
            console.log(minuses, pluses, timeses, dividers);
}

solve("3 - 6 * 3 / 9 + 5");

如您所见，对于每个连续的运算符，我需要映射前一个运算符的每个元素以将其拆分，然后剩下一个数组数组等...

那么 1) 我怎样才能更有效地拆分这些术语，而不是为每个术语创建一个新变量，并手动递归地映射每个术语？看起来我应该有某种数组字典来跟踪操作顺序(现在不考虑括号或指数):["*","/","+","-"] -- 并给定该数组，生成类似于上例中最后一个数组(“分隔符”)的内容，它只包含常量，并以某种方式跟踪每个存储数组后面的元素...

和 2) 如何求解给定值数组的表达式？

我只是对逻辑有点困惑，我想我需要从最后一个数组开始，一次求解一个常量，跟踪哪个运算符是当前运算符，但我不确定如何正是。

Answer 1

虽然您的问题不需要构建，binary expression tree是集思广益解决数学问题的逻辑的好方法。

所以对于查询3 - 6 * 3/9 + 5，代表性的二叉表达式树是:

plus
  |_minus
  | |_3
  | |_divide
  |   |_times
  |   | |_3
  |   | |_6
  |   |_9
  |_5

要解决上面的树，您需要从叶级到根递归解决。

同样，您不需要构建树。它只是帮助我们在这里看到解析的逻辑:

• 获取查询中的最后一个减号或加号表达式，并求解该表达式的左右子表达式。
• 如果没有plus/minus，得到最后一次/除法表达式，解决左右 child
• 如果遇到一个数字，返回那个数字值。

鉴于上述逻辑，这里是一个实现:

function solve(str) {
  var expressionIndex = Math.max(str.lastIndexOf("-"), str.lastIndexOf("+"));
  if (expressionIndex === -1) {
    expressionIndex = Math.max(str.lastIndexOf("*"), str.lastIndexOf("/"));
  }
  if (expressionIndex === -1) {
    var num = Number.parseInt(str.trim());
    if (isNaN(num)) {
      throw Exception("not a valid number");
    } else {
      return num;
    }
  } else {
    var leftVal = solve(str.substring(0, expressionIndex).trim());
    var rightVal = solve(str.substring(expressionIndex + 1).trim());
    switch (str[expressionIndex]) {
      case "+":
        return leftVal + rightVal;
      case "-":
        return leftVal - rightVal;
      case "*":
        return leftVal * rightVal;
      case "/":
        return leftVal / rightVal;
    }
  }
}

function parse(str) {
  var expressionIndex = Math.max(str.lastIndexOf("-"), str.lastIndexOf("+"));
  if (expressionIndex === -1) {
    expressionIndex = Math.max(str.lastIndexOf("*"), str.lastIndexOf("/"));
  }
  if (expressionIndex === -1) {
    var num = Number.parseInt(str.trim());
    if (isNaN(num)) {
      throw Exception("not a valid number");
    } else {
      return { type: "number", value: num };
    }
  } else {
    var leftNode = parse(str.substring(0, expressionIndex).trim());
    var rightNode = parse(str.substring(expressionIndex + 1).trim());
    return {
      type: "expression",
      value: str[expressionIndex],
      left: leftNode,
      right: rightNode
    };
  }
}

console.log(solve("3 - 6 * 3 / 9 + 5"));
console.log(parse("3 - 6 * 3 / 9 + 5"));

上面是一个非常简单的查询的解决方案，只有 +、-、*、/(没有括号，例如)。要求解像您的第一个示例这样的方程式，需要做更多的工作。

编辑:添加一个解析函数来返回树。