Generate a Binary Expression Tree

algorithm expression-trees

Question

Could someone please describe the creation of a binary expression tree.

I, for instance, have a string.2*(1+(2*1)); How to create a binary expression tree from this.

 *
 | \
 |  \
 2  +
    |\
    1 *
      |\
      2 1
1
8
2/3/2012 10:07:33 PM

Popular Answer

Infix to postfix or prefix conversion

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

  1. Think about the first character. If it's not a symbol, make a node. it to the stack
  2. Create a node with symbol pop elements and add to the left and right of the symbol if the character is a symbol.
  3. Stack symbol node by pushing it in.
  4. until the iterator has no more items, repeat steps 1 through 3

Java Application

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;
}

Information: 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