我正在做一个数学表达式解析器，将文本解析成抽象语法树（但我对此并不了解）。
我在维基百科上看到可以使用Shunting-yard算法将标记的线性序列解析为逆波兰表达式或直接解析为AST，但我找不到任何使用Shunting-yard进行中缀转换为AST的示例。
目前，我正在使用Shunting-yard将中缀表达式转换为后缀表达式，然后使用该输出构建AST。
将表达式转换为后缀表达式，然后从中构建AST是一种好的实践方法吗？还是我有点笨拙？
将中缀表达式转换为后缀表达式并在数学求值器上构建抽象语法树是否是惯用做法？
6
- Gark Garcia
1
2对我来说，这听起来不太对，你应该能够一次性创建AST。你写下了一些例子吗？从概念上讲，将表达式解析为AST很简单，你只需要找到一个运算符（比如二元运算符），然后它就成为两侧表达式的父节点。 - Countingstuff
1个回答
7
要使Shunting Yard直接生成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)
- Salix alba
2
在这种情况下，我该如何处理括号？ - Gark Garcia
1对于括号，AST 中没有特定的运算符，而是树的结构决定了求值顺序，这总是深度优先。代码基本上没有改变。当输入中遇到左括号时，将其推入操作符堆栈。当遇到右括号时，使用上述方法不断弹出操作符，直到遇到匹配的左括号为止。只需弹出此括号，但不对输出树进行任何操作。 - Salix alba
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接