Build Binary Expression Tree

Question

Could someone explain how to build a binary expression tree.

For example I have a string 2*(1+(2*1)); How to convert this into a binary expression tree.

 *
 | \
 |  \
 2  +
    |\
    1 *
      |\
      2 1

Answer 1

Convert infix to postfix or prefix

The postfix input is: a b + c d e +**

1. Consider first character if it is not symbol then create node add it to stack
2. If character is symbol then create node with symbol pop elements and add to left and right of symbol
3. Push symbol node in to the stack.
4. Repeat 1, 2 and 3 till iterator has no more elements

Java Implementation

public Tree.TreeNode createExpressionTree(){
    Iterator<Character>itr = postOrder.iterator();
    Tree tree = new Tree();
    NodeStack nodeStack = new NodeStack();
    Tree.TreeNode node;
    while (itr.hasNext()) {
        Character c = itr.next();
        if(!isDigit(c)){
            node = tree.createNode(c);
            node.right = nodeStack.pop();
            node.left = nodeStack.pop();
            nodeStack.push(node);
        }else{
            node = tree.creteNode(c);
            nodeStack.push(node);
        }
    }
    node = nodeStack.pop();
    return node;
}

More info: http://en.wikipedia.org/wiki/Binary_expression_tree