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());
}
精彩评论