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 +**
- Consider first character if it is not symbol then create node add it to stack
- If character is symbol then create node with symbol,
pop
elements and add to left and right of symbol Push
symbol node in to the stack.- 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;
}