Solving Binary Tree

Question

Can anyone explain how I Solve a expression Tree when I'm given x as a parameter?

For example, I have the equation ((2*x)) + 4and let's say in the parameter, x = 3. This would give us 10 and the method would return this.

The way I thought about doing this was to do it recursively but I can't really do it because the parameter has to be the double x.

Any thoughts?

Here's the code I have so far.

  public double evaluate(double x) throws ExpressionTreeNodeException {
    ExpressionTreeNode n = new ExpressionTreeNode();
    n.setValue(getValue());
    n.setType(getType());
    if ( n.getRightChild() == null && n.getLeftChild() == null){
        double RootLeaf = Double.parseDouble(n.getValue());
        return RootLeaf;
    } else {
        double operand1 = 
        return ()
    }
}

Could you care to explain how to do it recursively? If I wanted to do it, I thought I would need the parameter to be the root so I can keep on going through the tree. — John Smith, Nov 29 '11 at 04:59

score 1 · Answer 1 · answered Nov 29 '11 at 05:00

1

Wouldn't you just say something on the order of:

if ( n.getRightChild() == null && n.getLeftChild() == null){
    double RootLeaf = Double.parseDouble(n.getValue());
    return RootLeaf;
} else if (n.getLeftChild() == null) {
    // Evaluate prefix operator -- assume no postfix operators
    double operand1 = n.getRightChild().evaluate(x);
    double result = n.getType().evaluateMonadic(operand1);
    return result;
} else {
    // Evaluate diadic operator
    double operand1 = n.getLeftChild().evaluate(x);
    double operand2 = n.getRightChild().evaluate(x);
    double result = n.getType().evaluateDiadic(operand1, operand2);
    return result;
}

(Taking liberties with your structure because I don't know the full intent of everything.)

(I'm assuming your structure is defined to be evaluating a function of only one variable, which is why you pass in x rather than passing in a dictionary of variable values.)

answered Nov 29 '11 at 05:00

Hot Licks

47,103
17
93
151

Could you explain what evaluateMonadic(double) does? It doesn't work for this since getType() returns a int – John Smith Nov 29 '11 at 19:21
I was assuming that "type" would be the type of operator, and `evaluateMonadic` would evaluate that operator. Could just as well be `evaluateMonadic(n.getType(), operand1)` or whatever. And, of course, `evaluateDiadic` would be similar but for a diadic, two-operand operator. – Hot Licks Nov 29 '11 at 21:10
Is there any other way to do this without using Monadics? I'm not exactly sure how to use them. – John Smith Nov 29 '11 at 21:32
A monadic operator is, eg the `-` in front of `-x`. In fact, for your purposes likely `-` would be the only one. – Hot Licks Nov 29 '11 at 23:30

Solving Binary Tree

1 Answers1

Linked