我必须用 Java 创建一个算术计算器。为此,我必须解析二叉树中的代数表达式,然后计算并返回结果。那么对于第一步,我如何解析二叉树中的表达式?我知道这个理论,但我的概率是如何用 Java 来实现。我阅读了以下帖子 create recursive binary tree
但我缺少基本技巧或方法。我知道如何创建一个节点(我有一个带有 returnNodeValue、isLeaf、isDoubleNode、isSingleNode 等方法的类)但我认为我需要一种方法来在二叉树中插入一个节点来实现我想要的。有什么想法吗?
最佳答案
前缀表达式的树结构
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
举个例子:+ 2 + 1 1
应用 (0)。
+
应用 (1)。
+
/
2
应用 (2)。
+
/ \
2 +
应用 (1)。
+
/ \
2 +
/
1
最后,应用(2)。
+
/ \
2 +
/ \
1 1
此算法已针对 - */15 - 7 + 1 1 3 + 2 + 1 1
进行了测试
所以 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 = ?
评估树有点滑稽,因为你必须从树的右下角开始。执行反向 post-order遍历。先访问正确的 child 。
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
鉴于从前缀表达式构建树的简单性,我建议使用标准 stack algorithm从中缀转换为前缀。在实践中,您会使用堆栈算法来评估中缀表达式。
https://stackoverflow.com/questions/7866587/
相关文章:
c#-4.0 - Dataset/datatable是值类型还是引用类型
wordpress - 如何检查它是哪个级别的 wordpress 类别?
common-lisp - sbcl 上的 undefined variable ,而不是 clis
facebook - 通过 Facebook 的 Api 编辑个人资料封面
perl - reverse 不在列表上下文中隐式使用 $_,这是一个错误吗?
fonts - Safari 放大/缩小破坏页面布局(不能很好地改变字体大小)