/**
 * This traversal specializes EulerTour to compute the
 * value of an arithmetic expression stored in the tree. It assumes
 * that the elements stored at the external nodes are Integer objects
 * and that the elements stored at the internal nodes are of type
 * OperatorInfo, supporting method operation(Integer x, Integer y), which
 * returns the result of applying an arithmetic operation to x and y.
 */
public class EvaluateExpressionTour extends EulerTour {

  public Object execute(BinaryTree T) {
      super.execute(T); // calls method of superclass
    System.out.print("The value is: ");
    System.out.println(eulerTour(tree.root()));
    return null;  // nothing interesting to return
  }

  protected void visitExternal(Position p, TraversalResult r) {
    r.finalResult = (Integer) p.element();
  }

  protected void visitRight(Position p, TraversalResult r) {
    OperatorInfo op = (OperatorInfo) p.element();
    r.finalResult = op.operation((Integer) r.leftResult,
                                 (Integer) r.rightResult); 
  }

}