/*****************************************************************************/
/*                                                                           */
/*                 Postfix Enumeration of an Expression Tree                  */
/*                                                                           */
/*                    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 deacha non-leaf node, the subexpression represented
// by the subtree under the non-leaf node is computed.
// This program generates the postfix representation for an agebraic
// expression represented by a systax tree.

class Postfix {                       // class for Java application

  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 String toPostfix() {  // enumerate subexpression below this node
      String exp;                // subexpression in reverse Polish notation
      if (operator == null) {    // is this a leaf node?
        exp = " " + value;       // yes, return value stored in this node
      } else {                   // non-leaf, compose subexpression in RPN
        exp = leftChild.toPostfix() + rightChild.toPostfix() + 
              " " + operator.symbol;
      }
      System.out.println("Subexpression evaluated for " + name + ": " + exp);
      return exp;
    }
  
    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 + ")";
      }
    } 
  }

  Node root;                    // root node of tree
   
  public void initialize() {
    System.out.println("Postfix.initialize() entered");
    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
    root = node7;                // set new root node
  }

  public static void main(String argv[]) {     // application main function
    Postfix postfix = new Postfix();
    postfix.initialize();
    System.out.println("Expression: " + postfix.root.toString());
    System.out.println("Postfix enumeration: " + postfix.root.toPostfix());
  }  
}