/*****************************************************************************/
/*                                                                           */
/*  Evaluating an Expression in Reverse Polish Notation: Graphical Version   */
/*                                                                           */
/*                     January 1999, Toshimi Minoura                         */
/*                                                                           */
/*****************************************************************************/

// The expression stored in exp[] defined in class Expression is evaluated.
// An element of exp[] is an Integer or Op.
// When an expression is incorrect, an error message is displayed.

import java.awt.*;
import java.awt.event.*;
import java.util.*;

class Expression {
  private Object exp[] =  { new Integer(10), new Integer(25), new Integer(2),
//      new Op('*'), new Op('+'), new Integer(40), new Op('+') };
        new Op('*'), new Op('+'), new Integer(40), new Op('+'), new Op('+') };
  int currentIdx = -1;                   // -1 indicates evaluation not started

  public Object getElement(int i) {      // return i-th element of exp[]
    currentIdx = i;                      // show element last accessed
    return exp[i];
  };

  public int length() {                  // return length of exp[]
    return exp.length;
  };

  public void reset() {                  // reset pointer location
    currentIdx = -1;                     // evaluation not started yet
  }

  public void set(Object[] newExp) {     // set new expression
    exp = newExp;
  }
  
  // Draw an up arrow from (x1, y1) to tip at (x1, y2) where y1 > y2
  public void drawUpArrow(Graphics g, int x1, int y1, int y2) {
    Polygon poly = new Polygon();        // create a Polygon object
    poly.addPoint(x1 - 2, y1);           // lower-left of arrow shaft
    poly.addPoint(x1 + 2, y1);           // rlower-ight of arrow shaft
    poly.addPoint(x1 + 2, y2 + 6);       // upper-right of arrow shaft
    poly.addPoint(x1 + 6, y2 + 6);       // lower-right of arrow tip
    poly.addPoint(x1, y2);               // tip of arrow
    poly.addPoint(x1 - 6, y2 + 6);       // lower-left of arrow tip
    poly.addPoint(x1 - 2, y2 + 6);       // upper-left of arrow shaft
    g.fillPolygon(poly);                 // draw arrow
  }

  static final Color ExpressionColor = new Color(0, 0, 200);
  static final Color UpArrowColor = new Color(0, 150, 150);

  public void paint(Graphics g) {        // redraw expression and pointer
    System.out.println("Expression.paint() entered");
    final int x1 = 50;                   // left position for expression
    final int y1 = 35;                   // top position of expression
    final int width = 30;                // width of value field
    final int height = 23;               // height of value field
    final int arrowHeight = 25;          // height of up arrow

    g.setColor(ExpressionColor);         // set color for expression
    int x = x1;                          // x position of element of exp
    for (int i = 0; i < exp.length; i ++) {
      g.drawString(String.valueOf(exp[i]), x, y1 + 14); //draw value
      x += width;                        // update x position of next element
    }
    if (currentIdx >= 0) {               // evaluation started?
      int x2 = x1 + currentIdx * width + 5;  // calculate x location
      g.setColor(UpArrowColor);              // set up arrow color
      drawUpArrow(g, x2, y1 + height + arrowHeight, y1 + height); 
    }
  }
}
 
class StackG {
  private int data[];           // storage for data stacked
  private int top;              // index to top of stack
  private int depth;            // stack size

  private int yLoc;             // y location of top of stack

  public StackG(int yLoc) {     // constructor
    data = new int[100];
    top = -1;                   // initially, stack is empty
    depth = 0;
    this.yLoc = yLoc;
  }

  public void push(int x) {
    top++;                      // update number of elements in stack
    data[top] = x;              // store data item at top of stack
    depth++;                    // update number of elements in stack
  }

  public int pop() {
    depth--;                    // update number of elements in stack
    return data[top--];         // remove data item at top and return
  }

  public void clear() {         // make stack empty
    top = -1;
    depth = 0;
  }

  public int depth() {          // return the number of elements in stack
    return depth;
  }

  public void drawRightArrow(Graphics g, int x1, int y1, int x2) {
    Polygon poly = new Polygon();     // arrow from (x1, y1) to (x2, y1)
    poly.addPoint(x1, y1 - 2);
    poly.addPoint(x1, y1 + 2); 
    poly.addPoint(x2 - 6, y1 + 2);
    poly.addPoint(x2 - 6, y1 + 6);
    poly.addPoint(x2, y1);             // tip of right arrow
    poly.addPoint(x2 - 6, y1 - 6);
    poly.addPoint(x2 - 6, y1 - 2);
    g.fillPolygon(poly);               // draw arrow
  }

  static final Color BoxColor = new Color(50, 0, 100);      // for outline box
  static final Color FillColor = new Color(150, 255, 0);    // for filling box
  static final Color LetterColor = new Color(80, 0, 80);    // for value in box
  static final Color RightArrowColor = new Color(0, 100, 100);

  public void paint(Graphics g) {
    final int x1 = 250;             // left position for stack elements
    final int StackHeight = 150;    // stack height
    final int BoxWidth = 60;        // width of stack element
    final int BoxHeight = 32;       // height of stack element
    int y = yLoc + StackHeight;     // y position of stack bottom element

    g.setColor(RightArrowColor);    // set right arrow color

    if (top == - 1) {
      g.drawString("Empty Stack", x1 - BoxWidth * 2 / 3, y);
      return;
     };

    int y2 = y - top * BoxHeight + 10;                  // y position of arrow
    drawRightArrow(g, x1 - BoxWidth * 2 / 3, y2, x1 - 3);  // draw pointer

    for (int i = 0; i <= top; i ++)  {            // draw stack elements
      g.setColor(BoxColor);                       // set box outline color
      g.drawRect(x1, y, BoxWidth, BoxHeight - 8); // draw outline box
      g.setColor(FillColor);                      // set box fill color
      g.fillRect(x1 + 1 , y + 1 , BoxWidth - 2 , BoxHeight - 10); // fill box
      g.setColor(LetterColor);                    // set letter color
      g.drawString(String.valueOf(data[i]), x1 + 20, y + 18); //draw value
      y -= BoxHeight;               // update y position of next stack element
    }
  }

  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("");
  }
}

public class PolishG extends StepTestCanvas {
  Expression expression;             // expression to be evaluated
  StackG stack;                      // graphical stack used for evaluation
  private int currentIdx;       // index pointing to current element in exp

  public PolishG() {                 // constructor
    expression = new Expression();   // create expression
    stack = new StackG(80);          // create stack at y location 200
  }

  Font f = new Font("TimesRoman", Font.BOLD, 18);

  public void paint(Graphics g) {    // called when window need be redrawn
    g.setFont(f);                    // set font for letters
    expression.paint(g);             // draw expression
    stack.paint(g);                  // draw stack
  }   

  public static void main(String[] args) {
    new StepTestFrame("Evaluating Polish Expression", new PolishG(),
                       580, 400).show();  // set width and height of frame
  }
   
  public void runMain() {             // execute thread
    System.out.println("runMain() entered");
    expression.reset();               // reset expression pointer
    stack.clear();                    // clear stack
    currentIdx = 0;                   // set index to start of expression
    repaintStep("You may provide another expression in the input area," +
                " then press the Step button.");

    StringTokenizer inputTokens = getInputTokens();  // read from input area
    int inputSize = inputTokens.countTokens();     
    if (inputSize > 0) {   // if expression is provided, construct newExp
      Object newExp[] = new Object[inputSize];   // for expression constructed
      int i = 0;
      while (inputTokens.hasMoreTokens()) {      // input not exhausted
        String token = inputTokens.nextToken();  // get next token
        if (token.equals("+") || token.equals("*")) {   // operator?
          newExp[i++] = new Op(token.charAt(0)); // create operator
        } else {                                 // int operand
          newExp[i++] = new Integer(Integer.parseInt(token));  // get int value
        }
      }
      expression.set(newExp);         // set expression read from input area
    }
    // Evaluation of expression will start.
    for ( ; currentIdx < expression.length(); currentIdx++) { 
      System.out.println("exp[" + currentIdx + "] = " +       // print element
                          expression.getElement(currentIdx));
      if (expression.getElement(currentIdx) instanceof Integer) { // operand?
         System.out.println("Integer found");             
         int value = ((Integer) expression.getElement(currentIdx)).intValue();
         repaintStep("Value " + value + " will be pushed onto stack.");
         stack.push(value);           // push operand onto stack
         repaintStep("Value " + value + " pushed onto stack.");
         System.out.println( value + " pushed onto stack"); 
      } else if (((Op) expression.getElement(currentIdx)).symbol == '+' ) {
         System.out.println("+ found");   // + operator found
         repaintStep("Two elements at stack top will be added.");
         if (stack.depth() < 2) {
           System.out.println("Too Few Operands for +");
           repaintStep("Too Few Operands for +." +
                       "  You may press the Restart button.");
           stop();
         }
         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"); 
         repaintStep(value1 + " and " + value2 + " added.");
      } else if (((Op) expression.getElement(currentIdx)).symbol == '*') {
         System.out.println("* found");   // * operator found
         repaintStep("Two elements at stack top will be multiplied.");
         if (stack.depth() < 2) {
           System.out.println("Too Few Operands for *" );
           repaintStep("Too Few Operands for *." +
                       "  You may press the Restart button.");
           stop();
         }
         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"); 
         repaintStep(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");
  }  
}