Generate a Binary Expression Tree

algorithm expression-trees

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
1
8
2/3/2012 10:07:33 PM

Popular Answer

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

11
1/16/2017 5:10:36 PM


Related Questions





Licensed under: CC-BY-SA with attribution
Not affiliated with Stack Overflow
Licensed under: CC-BY-SA with attribution
Not affiliated with Stack Overflow