java - Create a binary tree from an algebraic expression

Question

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

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?

Answer 1

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

Apply (0).

  +

Apply (1).

  +
 /
2 

Apply (2).

  +
 / 
2   +

Apply (1).

  +
 / 
2   +
   /
  1 

Finally, apply (2).

  +
 / 
2   +
   / 
  1   1

This algorithm has been tested against - * / 15 - 7 + 1 1 3 + 2 + 1 1

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.