parsing - 如何构建数学表达式的解析树？

Question

我正在学习如何编写标记器、解析器，并且作为练习，我正在用 JavaScript 编写一个计算器。

我正在使用短语树方法(我希望我正确理解了这个术语)来构建我的计算器。我正在根据运算符优先级构建一棵标记树。

例如，给定表达式a*b+c*(d*(g-f))，正确的树将是:

         +
        / \
       *   \
      / \   \
     a   b   \
              *
             / \
            c   *
               / \
              d   -
                 / \
                g   f

一旦获得了树，我就可以向下遍历它并递归地在左右节点的每个根节点处应用操作来查找表达式的值。

然而，最大的问题是实际构建这棵树。我只是不知道如何正确地做到这一点。我不能只拆分运算符 +、-、/ 和 * 并从左侧创建树和正确的部分，因为优先级。

到目前为止我所做的是对表达式进行标记。因此，给定 a*b+c*(d*(g-f))，我最终得到一个标记数组:

[a, Operator*, b, Operator+, c, Operator*, OpenParen, d, Operator*, OpenParen, g, Operator-, f, CloseParen, CloseParen]

但是，我无法弄清楚下一步如何从这个 token 数组转到我可以遍历并计算出值的树。谁能帮我想出如何做到这一点的想法吗？

Answer 1

对了，我不知道如何让它看起来漂亮

我用 C 语言编写了一个类似的程序，但我的树是颠倒的，这意味着新的运算符成为根。

C code, but read the readme 中的计算器解析树

例如:输入 2 + 3 - 4

从空节点开始

{}

规则1:当你读取一个数字时，在当前节点的左侧或右侧添加一个子节点，以空节点为准

      {}
     /
   {2}

规则2:然后你读到一个运算符，你要从当前节点{2}开始爬到一个空节点，当找到一个时，将其值更改为+，如果没有空节点，则必须创建然后将其作为树的根

      {+}
     /
   {2}

您遇到另一个数字，请转到规则 1，我们目前在 {+} 处找到空的一边(这次是对的)

      {+}
     /   \
   {2}   {3}

现在我们有了新的操作数“-”，但由于 {3} 的父节点已满，因此您必须创建新节点并使其成为所有节点的根

        {-}
        /
      {+}
     /   \
   {2}   {3}

哦，看看那个，另一个数字，因为我们当前指向根，让我们找到一个空的 {-} 子代，(提示右侧)

         {-}
        /   \
      {+}   {4}
     /   \
   {2}   {3}

构建树后，查看函数 getresult() 来计算所有内容

您可能想知道括号是如何工作的。我是这样做的:

每次遇到“(”时，我都会创建全新的树，并将其余输入构建到该树中。如果我读到另一个“(”，我会创建另一个树并继续使用新树构建。

读取输入后，我将所有树的根相互连接以形成一棵最终树。查看代码和自述文件，我必须画图来解释一切。

希望这也能帮助 future 的读者