是从infix转换到后缀，然后在数学评估器上构建AST吗？

Question

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

我在维基百科上读到过，人们可以使用调车码算法将一个线性的令牌序列解析成反向波兰表示法 ，或者将解析成AST本身，但是我无法找到任何使用分流码直接插入到AST解析的例子。

现在，我正在使用调车场从infix转换为后缀符号，然后使用这样的输出来构建AST。

将表达式转换为后缀符号，然后从它构建AST是很好的做法，还是我有点笨拙？

Answer 1

为了使调车场直接产生AST，应将输出更改为节点堆栈。

当输入中遇到数字、变量或其他终端时，将其转换为叶节点，并推送到输出堆栈。当遇到运算符时，其按常规推送到运算符堆栈。

最大的变化是当操作符从操作符堆栈中弹出时会发生什么。如果它是一个二进制操作符，那么输出堆栈上的最后两个节点被弹出，一个新的二进制节点作为子节点被构造，并被推回输出堆栈上。

在psudo代码中

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)