java 从代数表达式创建二叉树
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/7866587/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Create a binary tree from an algebraic expression
提问by Anila
I have to create an arithmetic evaluator in Java. To do this I have to parse an algebric expression in binary tree and then calculate and return the result. So for the first step how can I parse an expression in a binary tree? I know the theory but my prob is how to do it in Java. I read the following post create recursive binary tree
我必须在 Java 中创建一个算术评估器。为此，我必须解析二叉树中的代数表达式，然后计算并返回结果。那么第一步我如何解析二叉树中的表达式？我知道这个理论，但我的问题是如何在 Java 中做到这一点。我阅读了以下帖子 创建递归二叉树
But I'm missing the basic trick or method. I know how to create a node (I have a class with methods like returnNodeValue, isLeaf, isDoubleNode, isSingleNode etc) but I think I'll need a method to insert a node in a binary tree to acheive what I want. Any ideas?
但我缺少基本的技巧或方法。我知道如何创建一个节点（我有一个带有 returnNodeValue、isLeaf、isDoubleNode、isSingleNode 等方法的类），但我想我需要一种方法来在二叉树中插入一个节点来实现我想要的。有任何想法吗？
回答by blackcompe
Tree construction for prefix expressions
前缀表达式的树构造
def insert
Insert each token in the expression from left to right:
(0) If the tree is empty, the first token in the expression (must
be an operator) becomes the root
(1) Else if the last inserted token is an
operator, then insert the token as the left child of the last inserted
node.
(2) Else if the last inserted token is an operand, backtrack up the
tree starting from the last inserted node and find the first node with a NULL
right child, insert the token there. **Note**: don't insert into the last inserted
node.
end def
Let's do an example: + 2 + 1 1
让我们做一个例子： + 2 + 1 1
Apply (0).
应用 (0)。
+
Apply (1).
应用 (1)。
+
/
2
Apply (2).
应用 (2)。
+
/ \
2 +
Apply (1).
应用 (1)。
+
/ \
2 +
/
1
Finally, apply (2).
最后，应用（2）。
+
/ \
2 +
/ \
1 1
This algorithm has been tested against - * / 15 - 7 + 1 1 3 + 2 + 1 1
该算法已经过测试 - * / 15 - 7 + 1 1 3 + 2 + 1 1
So the Tree.insertimplementation is those three rules.
所以Tree.insert实施就是这三个规则。
insert(rootNode, token)
//create new node with token
if (isLastTokenOperator)//case 1
//insert into last inserted's left child
else { //case 2
//backtrack: get node with NULL right child
//insert
}
//maintain state
lastInsertedNode = ?, isLastTokenOperator = ?
Evaluating the tree is a little funny, because you have to start from the bottom-right of the tree. Perform a reverse post-ordertraversal. Visit the right child first.
评估树有点有趣，因为您必须从树的右下角开始。执行反向后序遍历。首先拜访正确的孩子。
evalPostorder(node)
if (node == null) then return 0
int rightVal = evalPostorder(node.right)
int leftVal = evalPostorder(node.left)
if(isOperator(node.value))
return rightVal <operator> leftVal
else
return node.value
Given the simplicity of constructing a tree from a prefix expression, I'd suggest using the standard stack algorithmto convert from infix to prefix. In practice you'd use a stack algorithm to evaluate an infix expression.
鉴于从前缀表达式构造树的简单性，我建议使用标准堆栈算法将中缀转换为前缀。在实践中，您会使用堆栈算法来评估中缀表达式。
回答by Stephen C
I think you might be a bit confused about what you are supposed to be doing:
我想你可能对你应该做的事情有点困惑：
... but I think I'll need a method to insert a node in a binary tree ...
...但我想我需要一种在二叉树中插入节点的方法......
The binary tree you are talking about is actually a parse tree, and it is not strictly a binary tree (since not all tree nodes are binary). (Besides "binary tree" has connotations of a binary searchtree, and that's not what you need here at all.)
你说的二叉树实际上是一棵解析树，它并不是严格意义上的二叉树（因为不是所有的树节点都是二叉树）。（除了“二叉树”具有二叉搜索树的含义，这根本不是你在这里需要的。）
One you have figured out to parse the expression, the construction of the parse tree is pretty straight-forward. For instance:
您已经想出解析表达式的方法，解析树的构造非常简单。例如：
Tree parseExpression() {
// ....
// binary expression case:
Tree left = parseExpression();
// parse operator
Tree right = parseExpression();
// lookahead to next operator
if (...) {
} else {
return new BinaryNode(operator, left, right);
}
// ...
}
Note: this is not working code ... it is a hint to help you do your homework.
注意：这不是工作代码......它是帮助您做功课的提示。
