/*****************************************************************************/
/*                                                                           */
/*                  Evaluating an Expression in Tree Form                    */
/*                                                                           */
/*                    December 1997, Toshimi Minoura                         */
/*                                                                           */
/*****************************************************************************/

// An expression is represented by a tree.
// Each node in this tree can store an operator and a value.
// For a leaf node, only its value is relevant.
// For each non-leaf node, the value for the subexpression represented
// by the subtree under the non-leaf node is computed.

class Operator {                       // class for operators
  public char symbol;                  // +, *, etc.

  Operator(char x) { symbol = x; }     // constructor for an Operator object

  public int eval(int x, int y) {      // apply this operator to two integers
    if (symbol == '+') {               // this operator is addition
      return x + y;
    }
    if (symbol == '*') {               // this operator is multiplication
      return x * y;
    }
    return -1;                         // illegal operator encountered
  }
  public String toString() {
    return "" + symbol;                // convert char to String and return it
  }
}

class Node {
  String name;                         // name of this node, for debugging
  public Operator operator;            // operator represented by this node
  public int value;                    // value associated with this node
  Node leftChild;                      // left subexpression
  Node rightChild;                     // right subexpression

  Node(String name, int val) {         // constructor for a leaf node
    this.name = name;                  // set name
    operator = null; 
    value = val;                       // set value for this leaf node
    leftChild = null;                  // no left subexpression
    rightChild = null;                 // no right subexpression
    System.out.println("leaf node " + name + " created with value = " + value);
  }

  Node(String name, char opCode, Node leftNode, Node rightNode) {
    this.name = name;                  // set name
    operator = new Operator(opCode);   // create operator for given symbol
    value = -1;                        // no initial value
    leftChild = leftNode;              // set left subexpression
    rightChild = rightNode;            // set right subexpression
    System.out.println("operator node " + name + " created for " +
               leftChild.name +" " + operator + " " + rightChild.name);
  }

  public int eval() {          // evaluate subexpression below this node
    if (operator == null) {    // is this a leaf node?
      return value;            // yes, return value stored in this node
    } else {                   // non-leaf, calculate value for subexpression
      value = operator.eval(leftChild.eval(), rightChild.eval());
      System.out.println("Subexpression evaluated for " + name + ": " + value);
      return value;
    }
  }

  public String toString() {     // convert an expression tree to String
    if (operator == null) {      // leaf node?
      return "" + value;         // yes, convert int to String and return
    } else {                     // return String for subexpression
      return "(" + leftChild + operator + rightChild + ")";
    }
  } 
}
 
class ExpressTree {                             // class for Java application
  public static void main(String argv[]) {      // application main function
    Node node1 = new Node("n1", 1);             // leaf node with value 1
    Node node2 = new Node("n2", 2);             // leaf node with value 2
    Node node3 = new Node("n3", 3);             // leaf node with value 3
    Node node4 = new Node("n4", 4);             // leaf node with value 4
    Node node5 = new Node("n5", '*', node2, node3);  // non-leaf, n2 + n3
    Node node6 = new Node("n6", '+', node1, node5);  // non-leaf, n1 * n5
    Node node7 = new Node("n7", '+', node6, node4);  // non-leaf, n6 + n4
    System.out.println("Evaluation of expression: " + node7);
    node7.eval();
    System.out.println("Evaluation completed, node7.value = " + node7.value);
  }  
}