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

Answer 2

you will need to:

1. define a grammar that describes your language
2. write a lexical analyzer that reads the tokens from your string
3. write a parser that builds a tree from the tokens

for example, take a look at this approach: http://en.wikipedia.org/wiki/Recursive_descent_parser

there are others

Answer 3

Convert the expression to prefix or postfix notation. From there it should be pretty straightforward. Algorithms are mentioned in the following wiki links.

http://en.wikipedia.org/wiki/Polish_notation

http://en.wikipedia.org/wiki/Reverse_Polish_notation

Answer 4

It can be divided into two steps:

1. Calculate priority value for each token.

   For example: '+': 1, 'x': 2, number: inf, '(': add 10 to base, ')': subtract 10 from base)

2. Build Cartesian tree based on priority by using a stack (approx 5 lines of code)

You can do it in one scan.