Calculator Algorithm - Using Iteration instead of Recursion on Binary Search Tree

Question

I've seen approaches on how to iterate through binary trees and find the sum of all nodes, except I'm evaluating expression inputs for a calculator. The nodes are arranged in the proper order according to order of operations and the nodes are either operators or operands. I think recursion is slower than iteration for this so I wanted to figure out how to go through the binary tree and find the result of the expression inputed without recursion.

An example of the tree:

      +
  *       /
3   4   4   2

The recursive method I have so far (I used an enum for the operator):

public static float evaluate(BETNode root)
{
    if (root == null)
    {
        throw new IllegalArgumentException("Error: Root is null!");
    }

    if (root.getType() == BETNodeType.OPERAND)
    {
        return root.getOperand();
    }

    float leftValue = evaluate(root.getLeft());
    float rightValue = evaluate(root.getRight());

    switch (root.getOperator())
    {
        case '+':
            return leftValue + rightValue;

        case '-':
            return leftValue - rightValue;

        case '*':
            return leftValue * rightValue;

        case '/':
            return leftValue/rightValue;
    }

    throw new IllegalArgumentException("Error.");
}

score 2 · Accepted Answer · edited May 23 '17 at 12:06

As I mentioned in my comment above, if you did an iterative post-order traversal, you'd get nodes in the order:

3, 4, *, 4, 2, /, +.

From this, you'd simply need a stack to evaluate the expression.

Push 3
Push 4
Push (pop() * pop())

Push 4
Push 2
Push (pop() / pop())
Push (pop() + pop())
//Result

Also interesting would be the Shunting Yard Algorithm which does the evaluation from an infix expression.

Calculator Algorithm - Using Iteration instead of Recursion on Binary Search Tree

1 Answers1