从代数表达式创建二叉树 [英] Create a binary tree from an algebraic expression

问题描述

我必须在Java中创建算术求值程序。为此，我必须解析二叉树中的代数表达式，然后计算并返回结果。因此，对于第一步，我如何解析二叉树中的表达式？我知道这个理论，但我的问题是如何用Java做到这一点。我阅读了以下帖子
创建递归二叉树

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

但我错过了基本的技巧或方法。我知道如何创建一个节点（我有一个类，其中包含returnNodeValue，isLeaf，isDoubleNode，isSingleNode等方法），但我想我需要一个方法在二叉树中插入一个节点来实现我想要的东西。任何想法？

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?

推荐答案

前缀表达式的树构造

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

此算法已针对<$进行了测试c $ c> - * / 15 - 7 + 1 1 3 + 2 + 1 1

所以树.insert 实现是这三个规则。

So the Tree.insert implementation is those three rules.

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-order traversal. 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 algorithm to convert from infix to prefix. In practice you'd use a stack algorithm to evaluate an infix expression.

这篇关于从代数表达式创建二叉树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！