从中缀转换为后缀然后在数学评估器上构建 AST 是否符合惯例？

Question

我正在做一个数学表达式解析器，将文本解析为抽象语法树（我不太了解这样做）。

我在维基百科上读到可以将 Shunting-yard algorithm to parse a linear sequence of tokens into Reverse Polish notation 或用于自身的 AST，但我无法找到任何使用 Shunting-yard 直接 infix-to-AST 解析的示例。

现在我正在使用 Shunting-yard 将 infix 转换为 postfix 表示法，然后使用这样的输出来构建 AST .

将表达式转换为 postfix 表示法然后从中构建 AST 是一种好习惯还是我有点笨拙？

Answer 1

为了让调车场直接产生一个AST输出应该改为一堆节点。

当输入中遇到数字、变量或其他终端时，将其转换为叶节点，并推入输出堆栈。当遇到运算符时，它会像往常一样被推入运算符堆栈。

最大的变化是当运算符从运算符堆栈中弹出时发生的情况。如果它是二元运算符，那么输出堆栈上的最后两个节点将被弹出，一个新的二元节点将以这些节点作为子节点构建并推回输出堆栈。

伪代码

Stack<Node> output
Stack<Operator> operators

function popOperator
    Operator op = operators.pop()
    Node right = output.pop()
    Node left = output.pop()
    Node n = makeNode( op, left, right )
    output.push(n)

从中缀转换为后缀然后在数学评估器上构建 AST 是否符合惯例？

Is it custumary to convert from infix to postfix and then build an AST on math evaluators?

parsing

math

evaluation