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?

What have you tried so far? The psuedocode is there (and there are a ton of implementations on the web, for better or worse). — Dave Newton, Oct 23 '11 at 14:15
I've already written the functions to read a tree in postfix, infix and prefix order. And I know there are a lot of examples but I can't find what I'm looking for. I need a little starting help on how to create a tree from an algebric expression (I mean how to take the expression and test the priorities and store the values etc). I know what I'm asking for is basic but I'm just stuck. Any link or help will be appreciated. Thanks. — Anila, Oct 23 '11 at 14:25
Generally, to write a parser you need a grammar. Then there are many kinds of parsers. Search the web for "recursive descent" parsers -- it's easy to understand how to code them. By the way, is this homework? — Ted Hopp, Oct 23 '11 at 14:29

blackcompe · Accepted Answer · 2014-01-12T21:06:49.180

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.

Finally found all the steps thanks to you. Convert from infix to prefix (see [Shunting-yard algorithm](https://en.wikipedia.org/wiki/Shunting-yard_algorithm) : better explained than provided link) -> create the tree -> evaluate with a reverse post-order traversal. Thank you! — Fitz, Jul 28 '16 at 07:44
_If the tree is empty, the first token in the expression (must be an operator)_ Unless the whole expression consists of one operand. — Fitz, Jul 28 '16 at 13:30
Could you give an example code for backtracking to the right null node ? — nevzatseferoglu, Apr 22 '20 at 17:50

score 5 · Answer 2 · answered Oct 23 '11 at 14:39

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 search tree, 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.

Create a binary tree from an algebraic expression

2 Answers2

Linked