/*****************************************************************************/
/*                                                                           */
/*             Evaluating an Expression in Reverse Polish Notation           */
/*                                                                           */
/*                    December 1997, Toshimi Minoura                         */
/*                                                                           */
/*****************************************************************************/

// The expression stored in exp[] defined in class Polish is evaluated.
// An element of exp[] is an Integer or Op.
 
class Stack  {
  private int data[];           // storage for data stacked
  private int top;              // index to top of stack

  public Stack() {              // constructor
    data = new int[100];
    top = -1;                   // initially, stack is empty
  }

  public void push(int x) {
    top++;
    data[top] = x;
  }

  public int pop() {
    return data[top--];
  }

  public void clear() {
    top = -1;
  }

  public void dataPrint() {                    // print stack content
     System.out.print("Stack: top = " + top + ", data = ");
      for (int i = 0; i <= top; i++) {
        System.out.print(data[i]);    // print every value in data[]
        if (i < top) System.out.print(", ");
      };
      System.out.println("");
  }
}
 
class Polish {
  static Object exp[] =  { new Integer(1), new Integer(2), new Integer(3),
                    new Op('*'), new Op('+'), new Integer(4), new Op('+') };
  static Stack stack = new Stack();
   
  public static void main(String argv[]) {          
    System.out.println("Evaluation (re)started");
    stack.clear();                        // clear stack
    int currentIdx = 0;                   // set index to start of expression
    for ( ; currentIdx < exp.length; currentIdx++) { 
      System.out.println("exp[" + currentIdx + "] = " +       // print element
                          exp[currentIdx]);
      if (exp[currentIdx] instanceof Integer) { 
         System.out.println("Integer found");             
         int value = ((Integer) exp[currentIdx]).intValue();
         stack.push(value);               // push operand onto stack
         System.out.println( value + " pushed onto stack"); 
      } else if (((Op) exp[currentIdx]).symbol == '+' ) {
         System.out.println("+ found");   // + operator found
         int value1 = stack.pop();        // get 1st operand from stack
         int value2 = stack.pop();        // get 2nd operand from stack
         stack.push(value1 + value2);     // put sum on to stack
         System.out.println( value1 + " and " + value2 + " added"); 
      } else if (((Op) exp[currentIdx]).symbol == '*') {
         System.out.println("* found");   // * operator found
         int value1 = stack.pop();        // get 1st operand from stack
         int value2 = stack.pop();        // get 2nd operand from stack
         stack.push(value1 * value2);     // put product onto stack
         System.out.println( value1 + " and " + value2 + " multiplied"); 
      } else {
         System.out.println("no match");
      }
      System.out.println("One element processed");
      stack.dataPrint();                  // print stack content
    }
    System.out.println("Evaluation completed");
  }  
}