开发者

Evaluate an expression tree

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 开发者_Python百科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();
    }
}


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?


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.


I fixed it for you:

Public int evaluate(BSTNode node){
        Int x=0, y=0, val=0;
        char operator =   node.getString().charAt(0);
        If(node.getLeft()!=null)
               x= evaluate(node.getLeft());
        If(node.getRight()!=null)
               x= evaluate(node.getRight());      

        If(operator== '+'){
               val= x+y;
               return val;
         }

        If(operator== '-'){
               val= x-y;
               return val;
         }
        If(operator== '*'){
               val= x*y;
               return val;
         }
        If(operator== '/'){
               val= x/y;
               return val;
         }
        return Integer.parseInt(node.getString());
 }
0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜