CODEWITHSUNDEEP
javaalgorithmbinary-tree
David Arce
David Arce

Reputation: 45

Evaluating an Expression in a Binary Tree Java

I created a Binary Tree of an expression and has the operators (+, -, /, *) as roots and operands (values) as the children left/right. I need to evaluate that expression in the Binary Tree taking the parameters (T, v) where 'T' is the binary tree and 'v' is a node where postorder traversal starts.

I have searched on how postorder traversal works and all of that which I understand. But I don't know how to implement the code using a node 'v' for the postorder traversal.

My method looks like this...

public int evaluateExpression (LinkedBinaryTree<T> tree, Position<T> v) {

}

This should return the operator being used on its operators (children of the root). So, I understand what to do, I am stuck on how to actually do it. -.-

Upvotes: 0

Views: 4755

Answers (2)

user207421
user207421

Reputation: 310885

You don't need to provide the entire tree, and you don't need a separate Position class. Every subtree is a tree. You just need something of this kind:

public class <T extends Number> ExpressionTree<T> {
    private ExpressionTree<T> left, right;
    private T value;
    private int operator;

    // constructors, getters, setters, etc. elided

    public T evaluateExpression() {
        // Here I am assuming a <T> value field that is set if the node
        // is a literal value rather than an expression subtree with left and right children.
        if (this.value != null)
            return this.value;
        // Evaluate the subtree
        switch (this.operator) {
        case '+':
            return left.evaluateExpression()+right.evaluateExpression();
        // etc for the other operators
        }
    }

You should not use the LinkedBinaryTree class mentioned in comments below. It is not designed for this purpose in any way, and appears to me to be needlessly complex even for its own purpose.

Upvotes: 3

Stefan Haustein
Stefan Haustein

Reputation: 18793

Normally, in the real world, you would do this as EJP suggests.

That said, a postorder iterator will give you the the values and the operators stored in the tree in the right order to do basically this:

  • If the element is a number, push it on a number stack
  • If the element is an operation, pop two elements from the number stack, process them according to the operation and push the result

After the traversal, return the only element on the stack

Upvotes: 0

Related Questions