Evaluate an expression tree

Question

Hi,

This project that I'm working on requires that an expression tree be constructed from a string of single digit operands and operators both represented as type char. I did the implmentation and the program up to that point works fine. I'm able to print out the inorder, preorder and postorder traversals in the correct way.

The last part calls for evaulating the expression tree. The parameters are an expression tree "t" and its root "root". The expression tree is ((3+2)+(6+2)) which is equal to 13. Instead I get 11 as the answer. Clearly I'm missing something here and I've done everything short of bashing my head against the desk.

I would greatly appreciate it if someone can point me in the right direction.

(Note that at this point I'm only testing addition and will add in the other operators when I get this method working.)

public int evalExpression( LinkedBinaryTree t, BTNode root ) {
    if( t.isInternal( root ) ) {
        int x = 0, y = 0, value = 0;
        char operator = root.element();
        if( root.getLeft() != null )
            x = evalExpression(t, t.left( root ) );
        if( root.getRight() != null )
            y = evalExpression(t, t.right( root ) );
        if( operator == '+' ) {
            value = value + Character.getNumericValue(x) + Character.getNumericValue(y);
        }
        return value;
    } else {
        return root.element();
    }
}

Answer 1

Without the actual tree you're running this on there is very little anyone can do to help you. Did you try to actually DEBUG it for a change?

You know, put some break-points and step by step see what it does?

Answer 2

The x and y values you get from the evalExpression calls in the "internal" case are already integers, so you shouldn't need the calls to Character.getNumericValue there. I think that should be happening in the "leaf" case instead.