Build a Binary Expression Tree for this expression

Technology CommunityCategory: Binary TreeBuild a Binary Expression Tree for this expression
VietMX Staff asked 3 years ago
Problem

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

 *
 | \
 |  \
 2  +
    |\
    1 *
      |\
      2 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
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;
}