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

Question

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

我在 Wikipedia 上读到，可以使用Shunting-yard 算法将标记的线性序列解析为逆波兰表示法 或本身的 AST，但我找不到任何直接中缀到 AST解析的示例与调车场。

现在我正在使用 Shunting-yard 将中缀表示法转换为后缀表示法，然后使用此类输出来构建 AST。

将表达式转换为后缀表示法，然后从中构建 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)