parsing - 从中缀转换为后缀然后在数学评估器上构建 AST 是否习惯？

Question

我正在做一个数学表达式解析器，它将文本解析成一个抽象的语法树(我不太了解这样做)。

我在维基百科上读到可以使用 Shunting-yard algorithm将标记的线性序列解析为 Reverse Polish notation 或 到 AST 本身，但我找不到任何使用 Shunting-yard 直接中缀到 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)