//
// expr.cpp: illustrates parsing and evaluating simple
//      arithmetic expressions over integers, +, -, *, and /
//      All operations are left-associative.
//
//   To build: g++ expr.cpp -o expr
//
// grammar:
//    Expression -> Term { (+|-) Term }*
//    Term       -> Factor { (*|/) Factor }*
//    Factor     -> Constant | '(' Expression ')'
//    Constant   -> [0-9]+
//
// Input: tokens separated by spaces:
//      ( 32 + 45 ) * 108 + -12 / 13
// All input appears on the command line; for example:
//      expr 3 + 4 * 2
//

#include <string>
#include <iostream>
#include <cassert>
#include <cctype>
#include <sstream>
#include <deque>
#include <set>
#include <string.h>
using namespace std;

class Expression
{
public:
   virtual int value() const = 0;
   virtual string toString() const = 0;
};

class Value : public Expression
{
   int val;
public:
   Value(int v) : val(v) { }
   int value() const { return val; }
   string toString() const
   {
      ostringstream o;
      o << val;
      return o.str();
   }
};

class BinaryExpression : public Expression
{
protected:
   Expression *left, *right;
   virtual char opAsChar() const = 0;
public:
   BinaryExpression(Expression *l, Expression *r) : left(l), right(r) { }
   string toString() const
   {
      return "(" + left->toString() + " " + opAsChar()
           + " " + right->toString() + ")";
   }
};

class Add : public BinaryExpression
{
public:
   Add(Expression *l, Expression *r) : BinaryExpression(l, r) { }
   int value() const { return left->value() + right->value(); }
protected:
   char opAsChar() const { return '+'; }
};

class Subt : public BinaryExpression
{
public:
   Subt(Expression *l, Expression *r) : BinaryExpression(l, r) { }
   int value() const { return left->value() - right->value(); }
protected:
   char opAsChar() const { return '-'; }
};

class Mult : public BinaryExpression
{
public:
   Mult(Expression *l, Expression *r) : BinaryExpression(l, r) { }
   int value() const { return left->value() * right->value(); }
protected:
   char opAsChar() const { return '*'; }
};

class Div : public BinaryExpression
{
public:
   Div(Expression *l, Expression *r) : BinaryExpression(l, r) { }
   int value() const { return left->value() / right->value(); }
protected:
   char opAsChar() const { return '/'; }
};

//
//----------------------------------------------------------

class Tokenizer
{
   deque<string> tokens;
   set<string> valid_tokens;
   bool isNum(const string&) const;
   int  numValue(const string&) const;
public:
   Tokenizer();
   // add next word to end of token list; throws string
   //   if not valid
   void add(const string &next_word);
   // are there more tokens?
   bool atend() const;
   // advance token to next item
   void advance();
   // return token type or '$' if at end of input
   char next() const;
   // return value for integer token; throws string if
   //   there is no integer
   int next_value();
};

Tokenizer::Tokenizer()
{
   string expected[6] = {"+", "-", "*", "/", "(", ")"};
   valid_tokens = set<string>(&expected[0], &expected[6]);
}

bool Tokenizer::isNum(const string& s) const
{
   if ( s.size() == 0 )
      return false;
   int i = 0;
   if ( s[0] == '-' )
      ++i;
   while ( i < int(s.size()) && isdigit(s[i]) )
      ++i;
   return i >= int(s.size());
}

int Tokenizer::numValue(const string& s) const
{
   istringstream i(s);
   int result;
   i >> result;
   return result;
}

void Tokenizer::add(const string &next_word)
{
   if ( valid_tokens.count(next_word) != 0 )
      tokens.push_back(next_word);
   else if ( isNum(next_word) )
   {
      tokens.push_back("i");
      tokens.push_back(next_word);
   }
   else
      throw string("Invalid token: " + next_word);
}

bool Tokenizer::atend() const { return tokens.empty(); }

void Tokenizer::advance()
{
   if ( tokens.front() == "i" )
      tokens.pop_front();
   tokens.pop_front();
}

char Tokenizer::next() const
{
   if ( atend() )
      return '$';
   else
      return tokens.front()[0];
}

int Tokenizer::next_value()
{
   if ( tokens.front() != "i" )
      throw string("Integer expected");
   assert(tokens.size() > 1);
   tokens.pop_front();
   int res = numValue(tokens.front());
   tokens.push_front("i");
   return res;
}

//
//----------------------------------------------------------

Expression *term(Tokenizer &tok);
Expression *factor(Tokenizer &tok);

Expression *expression(Tokenizer &tok)
{
   Expression *result = term(tok);
   while ( tok.next() == '+' || tok.next() == '-' )
   {
      char op = tok.next();
      tok.advance();
      Expression *next_term = term(tok);
      if ( op == '+' )
         result = new Add(result, next_term);
      else
         result = new Subt(result, next_term);
   }
   return result;
}

Expression *term(Tokenizer &tok)
{
   Expression *result = factor(tok);
   while ( tok.next() == '*' || tok.next() == '/' )
   {
      char op = tok.next();
      tok.advance();
      Expression *next_factor = factor(tok);
      if ( op == '*' )
         result = new Mult(result, next_factor);
      else
         result = new Div(result, next_factor);
   }
   return result;
}

Expression *factor(Tokenizer &tok)
{
   if ( tok.next() == 'i' )     // an (integer) number
   {
      int num = tok.next_value();
      tok.advance();
      return new Value(num);
   }
   else
   {
      if ( tok.next() != '(' )
         throw string("Unexpected token: ") + tok.next();
      tok.advance();
      Expression *e = expression(tok);
      if ( tok.next() != ')' )
         throw string("Expected ), got ") + tok.next();
      tok.advance();
      return e;
   }
}

//----------------------------------------------------------

int main(int argc, char* args[])
{
   if ( argc < 2 )
   {
      cerr << "Usage: " << args[0] << " expression" << endl;
      return 1;
   }
   try
   {
      Tokenizer tok;
      for(int i = 1; i < argc; ++i)
         tok.add(args[i]);
      Expression *e = expression(tok);
      if ( !tok.atend() )
         throw string("Extra terms in expression.");
      cout << "Parsed expression: " << e->toString() << endl;
      int val = e->value();
      cout << val << endl;
   }
   catch ( string err )
   {
      cerr << "Expression error: " << err << endl;
      return 2;
   }
   return 0;
}