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.");
}

Community · Accepted Answer · 2017-05-23 12:06:33Z

2

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.

edited May 23, 2017 at 12:06

CommunityBot

11 silver badge

answered May 10, 2015 at 7:58

Anirudh Ramanathan

46.8k24 gold badges137 silver badges195 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

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

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related