如何创建一个抽象的树，而不是一个后缀表达式与调车场算法？

Question

我在Wikipedia上找到了以下伪代码，它展示了如何使用调车场算法来创建修复后表达式：

While there are tokens to be read:
    Read a token.
    If the token is a number, then push it to the output queue.
    If the token is a function token, then push it onto the stack.
    If the token is a function argument separator (e.g., a comma):
    Until the token at the top of the stack is a left parenthesis, pop              operators off the stack onto the output queue. If no left parentheses are encountered, either the separator was misplaced or parentheses were mismatched.
    If the token is an operator, o1, then:
        while there is an operator token o2, at the top of the operator stack and either
    o1 is left-associative and its precedence is less than or equal to that of o2, or
    o1 is right associative, and has precedence less than that of o2,
            pop o2 off the operator stack, onto the output queue;
    at the end of iteration push o1 onto the operator stack.
If the token is a left parenthesis (i.e. "("), then push it onto the stack.
If the token is a right parenthesis (i.e. ")"):
    Until the token at the top of the stack is a left parenthesis, pop operators off the stack onto the output queue.
Pop the left parenthesis from the stack, but not onto the output queue.
If the token at the top of the stack is a function token, pop it onto the output queue.
If the stack runs out without finding a left parenthesis, then there are mismatched parentheses.
When there are no more tokens to read:
    While there are still operator tokens in the stack:
        If the operator token on the top of the stack is a parenthesis, then there are mismatched parentheses.
        Pop the operator onto the output queue.
Exit.

如何修改此算法以生成抽象语法树，我应该做什么而不是将运算符或操作数推送到输出？在

Answer 1

我想描述使用调车场算法构建AST的最简单方法，但不是最有效的方法。 我们的想法是使用该算法构建一个后缀字符串，然后从后缀字符串构建AST，这非常简单。表达式，例如：a * (b + c) + d

它的后缀字符串：

a b c + * d +

让我们从后缀字符串中逐个读取令牌。如果令牌是变量，则将其推送到具有节点的堆栈中。如果它是一个操作数，让我们从包含节点的堆栈中弹出两个最高的元素，创建另一个包含当前操作数的节点，并将两个提取的节点作为它的子节点。然后在节点堆栈中推送新节点。在

最后，我们将只剩下一个节点在节点堆栈中，即树的根。树已经建好了。在

这种算法需要读取两次字符串，这是一个明显的缺点。另一方面，它非常简单。在

更有效的算法，不需要构建后缀字符串，而是使用调车场立即构建AST，这里描述了but it's in C++。在