/*
   Infix tokenizer template
   CIS 260
   Replace this comment block with your own documentation comments.
*/

import java.util.*;

/*
   FSM: Finite state machine class - used to hold, and then provide
        rules for extended finite state machine.
*/
class FSM {
   // types of characters allowed in input
   static final int SIGN=0, DIGIT=1, PERIOD=2, OPEN=3, CLOSE=4, OPERATOR=5,
      BLANK=6, OTHER=7;
   // operations allowed in finite state machine
   // powers of two are used so operations can be combined
   static final int ERROR=1, CLEAR_OPERAND=2, ACCUM_OPERAND=4,
      APPEND_OPERATOR=8, APPEND_OPERAND=16, NONE=0;
   // associative array which holds rules for finite state machine
   HashMap<Integer, HashMap<Integer, FSMRule>> fsm;
   
   // an internal class used to hold a specific rule based
   //     on a state and character type
   class FSMRule {
      int actions;
      int nextState;
      FSMRule(int a, int ns) { actions=a; nextState=ns; }
   }
   
   // used to enter a rule into the finite state machine
   void put(int state, int charType, int actions, int nstate) {
      HashMap<Integer, FSMRule> tmp = fsm.get(state);
      if (tmp == null) {
         tmp = new HashMap<Integer, FSMRule>();
         fsm.put(state, tmp);
      }
      tmp.put(charType, new FSMRule(actions, nstate));
   }

   // used to get a rule from the finite state machine
   FSMRule get(int state, int charType) {
      HashMap<Integer, FSMRule> tmp = fsm.get(state);
      if (tmp == null) return null;
      else return tmp.get(charType);
   }
   
   // used to get a rule from the finite state machine
   FSMRule get(int state, char ch) {
      HashMap<Integer, FSMRule> tmp = fsm.get(state);
      if (tmp == null) return null;
      else return tmp.get(getCharType(ch));
   }
   
   // used to easily determine a character's type
   static int getCharType(char c) {
      if (c>='0' && c<='9') return DIGIT;
      else if (c=='+' || c=='-') return SIGN;
      else if (c=='.') return PERIOD;
      else if (c=='(') return OPEN;
      else if (c==')') return CLOSE;
      else if (c=='*' || c=='/' || c=='%' || c=='^') return OPERATOR;
      else if (c==' ') return BLANK;
      else return OTHER;
   }
   
   // constructor
   FSM() {
      fsm = new HashMap<Integer, HashMap<Integer, FSMRule>>();
   }
}

/*
   Token class
   
   This class defines the tokens that will be parsed from the input,
   stored in the infix queue, stored in the postfix queue, and stored
   on the stacks used for translation and evaluation.
*/
class Token {
   // constants for type of token being stored
   final static int OPERATOR = 0, OPERAND = 1, OPENPAREN = 2, CLOSEPAREN = 3;
   int type;        // type of token
   String data;     // token text
   int precedence;  // token's precedence
   boolean leftToRightAssociative;  // token's associativity
   
   // constructor
   Token(int typ, String d, int prec, boolean ltr) {
      type = typ;
      data = d;
      precedence = prec;
      leftToRightAssociative = ltr;
   }
   
   // returns type of token for single character tokens
   static int getType(char c) {
      if (c=='(') return OPENPAREN;
      if (c==')') return CLOSEPAREN;
      if (c=='+' || c=='-' || c=='*' || c=='/' || c=='%' || c=='^') return OPERATOR;
      return -1;
   }
   
   // very handy for debugging purposes
   public String toString() {
      String s = "";
      switch (type) {
         case OPERATOR: s = "operator (" + data + "), " + precedence + ", " + leftToRightAssociative; break;
         case OPERAND: s = "operand (" + data + ")"; break;
         case OPENPAREN: s = "open parenthesis"; break;
         case CLOSEPAREN: s = "close parenthesis"; break;
      }
      return s;
   }
}

public class Infix {
   // here is where you place your code
}