/*
   infixStart.cpp
   CIS 250
   Replace this comment block with your own documentation comments.
*/

#include <map>
#include <stack>
#include <deque>
#include <iostream>
#include <string>
#include <cmath>
using std::map;
using std::deque;
using std::cin;
using std::cout;
using std::string;

/*
   FSM: Finite state machine class - used to hold, and then provide
        rules for extended finite state machine.
*/
class FSM {
public:
   // an internal class used to hold a specific rule based
   //     on a state and character type
   class FSMRule {
   public:
      int actions;
      int nextState;
      FSMRule() {}
      FSMRule(int a, int ns) { actions=a; nextState=ns; }
   };
   // associative array which holds rules for finite state machine
   typedef map<int, FSMRule> MapIntToRule;
   typedef map<int, MapIntToRule> MapStateToRuleset;
   MapStateToRuleset fsm;
public:
   // types of characters allowed in input
   static const 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 const int ERROR=1, CLEAR_OPERAND=2, ACCUM_OPERAND=4,
      APPEND_OPERATOR=8, APPEND_OPERAND=16, NONE=0;
   static const FSMRule invalidRule;

   // used to enter a rule into the finite state machine
   void put(int state, int charType, int actions, int nstate) {
      FSMRule frule(actions, nstate);
      fsm[state].insert(MapIntToRule::value_type(charType, frule));
   }
   
   // used to get a rule from the finite state machine
   FSMRule get(int state, int charType) {
      MapIntToRule tmp = fsm[state];
      if (tmp.count(charType) == 0) return invalidRule;
      else return tmp[charType];
   }
   
   // used to get a rule from the finite state machine
   FSMRule get(int state, char ch) {
      MapIntToRule tmp = fsm[state];
      if (tmp.count(getCharType(ch)) == 0) return invalidRule;
      else return tmp[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;
   }
};

const FSM::FSMRule FSM::invalidRule(ERROR,0);

/*
   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 {
public:
   // constants for type of token being stored
   static const int OPERATOR = 0, OPERAND = 1, OPENPAREN = 2, CLOSEPAREN = 3;
   int type;        // type of token
   string data;     // token text
   int precedence;  // token's precedence
   bool leftToRightAssociative;  // token's associativity

   // constructor
   Token(int typ, string d, int prec, bool 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
   string toString() {
      char buf[10];
      string s = "";
      switch (type) {
         case OPERATOR: s = "oper (" + data + "), ";
              sprintf(buf, "%d, ", precedence);
              s += buf;
              if (leftToRightAssociative) s += "true";
              else s+= "false";
              break;
         case OPERAND: s = "operand (" + data + ")"; break;
         case OPENPAREN: s = "open parenthesis"; break;
         case CLOSEPAREN: s = "close parenthesis"; break;
      }
      return s;
   }
};

// HERE IS WHERE YOU PLACE YOUR CODE
//   GLOBAL VARIABLE DECLARATIONS
//   FUNCTION PROTOTYPES
//   int main(int argc, char* argv[])
//   bool isLeftAssociative(string oper)
//   int getPrecedence(string oper)
//   void initPrecedences()
//   void initAssociativities()
//   void errorExit(string msg)
//   void initFSM()