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

public class Rpn extends Applet implements Runnable,ActionListener,ItemListener {
   Stack myStack = new Stack();
   String inputString;
   String outputString;
   String[] line = new String[20];
   int[] x = new int[20];
   int[] y = new int[20];
   String inputStringLabel = "Input String";
   TextField inputStringField = new TextField(100);
   String outputStringLabel = "Output String";
   TextField outputStringField = new TextField(100);
   Button start = new Button("Start");
   Font plainFont = new Font("Sanserif",Font.PLAIN,11);
   Font boldFont = new Font("Sanserif",Font.BOLD,11);
   Thread algorithmRunner;
   int previous = 0;
   int current = 0;
   String[] stackElement = new String[20];
   int[] stackElementy = new int[20];
   int stackPointer = -1;
   TextField nextCharacter = new TextField();
   Label nextLabel = new Label("Next");
   int delay = 0;

   private int priority(String a) {
      int b = 0;
      if (a.equals("["))
         b = 0;
      else if (a.equals("("))
         b = 1;
      else if (a.equals("+"))
         b = 2;
      else if (a.equals("-"))
         b = 2;
      else if (a.equals("*"))
         b = 3;
      else if (a.equals("/"))
         b = 4;
      else if (a.equals("^"))
         b = 5;
      return(b);
   }    

   public Rpn() {
      line[0]="for every character in the infix expression";
      x[0]=100; y[0]=10;
      line[1]="if next character is closing parenthesis ')'";
      x[1]=120; y[1]=30;
      line[2]="pop operator from stack";
      x[2]=140; y[2]=50;
      line[3]="while operator not opening parenthesis '('";
      x[3]=140; y[3]=70;
      line[4]="store operator in string buffer";
      x[4]=160; y[4]=90;
      line[5]="pop operator from stack";
      x[5]=160; y[5]=110;
      line[6]="else if next character is closing bracket ']'";
      x[6]=120; y[6]=130;
      line[7]="pop operator from stack";
      x[7]=140; y[7]=150;
      line[8]="while operator not opening bracket '['";
      x[8]=140; y[8]=170;
      line[9]="store operator in string buffer";
      x[9]=160; y[9]=190;
      line[10]="pop operator from stack";
      x[10]=160; y[10]=210;
      line[11]="else if next character is opening parenthesis '(' or opening bracket '['";
      x[11]=120; y[11]=230;
      line[12]="push next character on to stack";
      x[12]=140; y[12]=250;
      line[13]="else if next character is arithmetic operator";
      x[13]=120; y[13]=270;
      line[14]="while priority of next character is <= priority of stack top operator";
      x[14]=140; y[14]=290;
      line[15]="pop operator from stack";
      x[15]=160; y[15]=310;
      line[16]="store operator in string buffer";
      x[16]=160; y[16]=330;
      line[17]="push next character on to stack";
      x[17]=140; y[17]=350;
      line[18]="else";
      x[18]=120; y[18]=370; 
      line[19]="store next character in string buffer";
      x[19]=140; y[19]=390;

      setLayout(null);

      inputStringField.setSize(350,30);
      inputStringField.setLocation(120,410);

      outputStringField.setSize(350,30);
      outputStringField.setLocation(120,450);

      start.setSize(50,20);
      start.setLocation(10,10);

      nextLabel.setSize(30,30);
      nextLabel.setLocation(400,10);
      nextLabel.setFont(boldFont);

      nextCharacter.setSize(60,30);
      nextCharacter.setLocation(440,10);

      start.addActionListener(this);

      Choice speedChoice = new Choice();

      speedChoice.add("0");
      speedChoice.add("1");
      speedChoice.add("2");
      speedChoice.add("3");
      speedChoice.add("4");
      speedChoice.add("5");
      speedChoice.add("6");
      speedChoice.add("7");
      speedChoice.add("8");
      speedChoice.add("9");
      speedChoice.add("10");

      speedChoice.setSize(100,20);
      speedChoice.setLocation(200,490);

      speedChoice.addItemListener(this);

      Label speedLabel = new Label("Delay");

      speedLabel.setSize(50,30);
      speedLabel.setLocation(150,490);
      speedLabel.setFont(boldFont);

      add(inputStringField);
      add(outputStringField);
      add(start);
      add(nextLabel);
      add(nextCharacter);
      add(speedLabel);
      add(speedChoice);
   }

   public void init() {
      for (int i=0;i<=19;i++)
         stackElement[i]="";
      for (int i=0;i<=19;i++)
         stackElementy[i]=380-15*i;
      inputStringField.setText("");
      outputStringField.setText("");
      
   }

   public void run() {
      int i = 0;
      String a;
      String b = "";
      String temp;

      inputString = inputStringField.getText();

      int length = inputString.length();

      outputString = "";

      for (i=0;i<=length-1;i++) {
         current = 0;
         repaint();
         try {
            Thread.sleep(delay);
         } catch (InterruptedException e) {
         }
         a = inputString.substring(i,i+1);
         nextCharacter.setText(a);
         temp = inputString.substring(i+1);
         inputStringField.setText(temp);         
         if (a.equals(")")) {
            current = 1;
            repaint();
            try {
               Thread.sleep(delay);
            } catch (InterruptedException e) {
            }
            stackPointer--;
            b = (String)myStack.pop();
            current = 2;
            repaint();
            try {
               Thread.sleep(delay);
            } catch (InterruptedException e) {
            }
            current = 3;
            repaint();
            try {
               Thread.sleep(delay);
            } catch (InterruptedException e) {
            }
            while (!b.equals("(")) {
               outputString = outputString + b;
               outputStringField.setText(outputString);
               current = 4;
               repaint();
               try {
                  Thread.sleep(2000);
               } catch (InterruptedException e) {
               }
               stackPointer--;
               repaint();
               b = (String)myStack.pop();
               current = 5;
               repaint();
               try {
                  Thread.sleep(delay);
               } catch (InterruptedException e) {
               }
            }
         } else if (a.equals("]")) {
            current = 1;
            repaint();
            try {
               Thread.sleep(delay);
            } catch (InterruptedException e) {
            }
            current = 6;
            repaint();
            try {
               Thread.sleep(delay);
            } catch (InterruptedException e) {
            }
            stackPointer--;
            b = (String)myStack.pop();
            current = 7;
            repaint();
            try {
               Thread.sleep(delay);
            } catch (InterruptedException e) {
            }
            current = 8;
            repaint();
            try {
               Thread.sleep(delay);
            } catch (InterruptedException e) {
            }
            while (!b.equals("[")) {
               outputString = outputString + b;
               outputStringField.setText(outputString);
               current = 9;
               repaint();
               try {
                  Thread.sleep(delay);
               } catch (InterruptedException e) {
               }
               stackPointer--;
               b = (String)myStack.pop();
               current = 10;
               repaint();
               try {
                  Thread.sleep(delay);
               } catch (InterruptedException e) {
               }
            }
         } else if (a.equals("(") || a.equals("[")) {
            current = 1;
            repaint();
            try {
               Thread.sleep(delay);
            } catch (InterruptedException e) {
            }
            current = 6;
            repaint();
            try {
               Thread.sleep(delay);
            } catch (InterruptedException e) {
            }
            current = 11;
            repaint();
            try {
               Thread.sleep(delay);
            } catch (InterruptedException e) {
            }
            stackElement[++stackPointer]=a;
            repaint();
            myStack.push(a);
            nextCharacter.setText("");
            current = 12;
            repaint();
            try {
               Thread.sleep(delay);
            } catch (InterruptedException e) {
            }
         } else if (a.equals("+") ||
                    a.equals("-") ||
                    a.equals("*") ||
                    a.equals("/") ||
                    a.equals("^")) {
            current = 1;
            repaint();
            try {
               Thread.sleep(delay);
            } catch (InterruptedException e) {
            }
            current = 6;
            repaint();
            try {
               Thread.sleep(delay);
            } catch (InterruptedException e) {
            }
            current = 11;
            repaint();
            try {
               Thread.sleep(delay);
            } catch (InterruptedException e) {
            }
            current = 13;
            repaint();
            try {
               Thread.sleep(delay);
            } catch (InterruptedException e) {
            }
            b = (String)myStack.peek();
            current = 14;
            repaint();
            try {
               Thread.sleep(delay);
            } catch (InterruptedException e) {
            }
            while (priority(a) <= priority(b)) {
               stackPointer--;
               b = (String)myStack.pop();
               current = 15;
               repaint();
               try {
                  Thread.sleep(delay);
               } catch (InterruptedException e) {
               }
               outputString = outputString + b;
               outputStringField.setText(outputString);
               current = 16;
               repaint();
               try {
                  Thread.sleep(delay);
               } catch (InterruptedException e) {
               }
               b = (String)myStack.peek();
            }
            stackElement[++stackPointer]=a;
            repaint();
            myStack.push(a);
            nextCharacter.setText("");
            current = 17;
            repaint();
            try {
               Thread.sleep(delay);
            } catch (InterruptedException e) {
            }
         } else { 
            current = 1;
            repaint();
            try {
               Thread.sleep(delay);
            } catch (InterruptedException e) {
            }
            current = 6;
            repaint();
            try {
               Thread.sleep(delay);
            } catch (InterruptedException e) {
            }
            current = 11;
            repaint();
            try {
               Thread.sleep(delay);
            } catch (InterruptedException e) {
            }
            current = 13;
            repaint();
            try {
               Thread.sleep(delay);
            } catch (InterruptedException e) {
            }
            current = 18;
            repaint();
            try {
               Thread.sleep(delay);
            } catch (InterruptedException e) {
            }
            outputString = outputString + a;
            outputStringField.setText(outputString);
            current = 19;
            repaint();
            try {
               Thread.sleep(delay);
            } catch (InterruptedException e) {
            }
         }

         try {
            Thread.sleep(delay);
         } catch (InterruptedException e) {
         }
      }

      current = -1;
      repaint();

      nextCharacter.setText("");

      outputStringField.setText(outputString);

      algorithmRunner.stop();
   }

   public void drawStack(Graphics g) {
      for (int i=0;i<=stackPointer;i++)
         g.drawString(stackElement[i],40,stackElementy[i]);
   }

   public void actionPerformed(ActionEvent e) {
      if (e.getSource() == start) {
         outputStringField.setText("");
         if (algorithmRunner == null) {
            algorithmRunner = new Thread(this);
            algorithmRunner.start();
         } else {
            algorithmRunner = null;
            algorithmRunner = new Thread(this);
            algorithmRunner.start();
         }
      }
   }

   public void destroy() {
      if (algorithmRunner != null) {
         algorithmRunner.stop();
         algorithmRunner = null;
      }
   }

   public void paint(Graphics g) {
      drawStack(g);
      if (current == 0)
         g.setFont(boldFont);
      else
         g.setFont(plainFont);
      g.drawString(line[0],x[0],y[0]);
      if (current == 1)
         g.setFont(boldFont);
      else
         g.setFont(plainFont);
      g.drawString(line[1],x[1],y[1]);
      if (current == 2)
         g.setFont(boldFont);
      else
         g.setFont(plainFont);
      g.drawString(line[2],x[2],y[2]);
      if (current == 3)
         g.setFont(boldFont);
      else
         g.setFont(plainFont);
      g.drawString(line[3],x[3],y[3]);
      if (current == 4)
         g.setFont(boldFont);
      else
         g.setFont(plainFont);
      g.drawString(line[4],x[4],y[4]);
      if (current == 5)
         g.setFont(boldFont);
      else
         g.setFont(plainFont);
      g.drawString(line[5],x[5],y[5]);
      if (current == 6)
         g.setFont(boldFont);
      else
         g.setFont(plainFont);
      g.drawString(line[6],x[6],y[6]);
      if (current == 7)
         g.setFont(boldFont);
      else
         g.setFont(plainFont);
      g.drawString(line[7],x[7],y[7]);
      if (current == 8)
         g.setFont(boldFont);
      else
         g.setFont(plainFont);
      g.drawString(line[8],x[8],y[8]);
      if (current == 9)
         g.setFont(boldFont);
      else
         g.setFont(plainFont);
      g.drawString(line[9],x[9],y[9]);
      if (current == 10)
         g.setFont(boldFont);
      else
         g.setFont(plainFont);
      g.drawString(line[10],x[10],y[10]);
      if (current == 11)
         g.setFont(boldFont);
      else
         g.setFont(plainFont);
      g.drawString(line[11],x[11],y[11]);
      if (current == 12)
         g.setFont(boldFont);
      else
         g.setFont(plainFont);
      g.drawString(line[12],x[12],y[12]);
      if (current == 13)
         g.setFont(boldFont);
      else
         g.setFont(plainFont);
      g.drawString(line[13],x[13],y[13]);
      if (current == 14)
         g.setFont(boldFont);
      else
         g.setFont(plainFont);
      g.drawString(line[14],x[14],y[14]);
      if (current == 15)
         g.setFont(boldFont);
      else
         g.setFont(plainFont);
      g.drawString(line[15],x[15],y[15]);
      if (current == 16)
         g.setFont(boldFont);
      else
         g.setFont(plainFont);
      g.drawString(line[16],x[16],y[16]);
      if (current == 17)
         g.setFont(boldFont);
      else
         g.setFont(plainFont);
      g.drawString(line[17],x[17],y[17]);
      if (current == 18)
         g.setFont(boldFont);
      else
         g.setFont(plainFont);
      g.drawString(line[18],x[18],y[18]);
      if (current == 19)
         g.setFont(boldFont);
      else
         g.setFont(plainFont);
      g.drawString(line[19],x[19],y[19]);
      g.setFont(plainFont);
      g.drawLine(20,60,20,400);
      g.drawLine(10,60,20,60);
      g.drawLine(20,400,60,400);
      g.drawLine(60,60,60,400);
      g.drawLine(60,60,70,60);
      g.drawString(inputStringLabel,50,430);
      g.drawString(outputStringLabel,40,470);
   }

   public void itemStateChanged(ItemEvent e) {
      delay = (Integer.valueOf((String)e.getItem())).intValue()*1000;
   }   
}