//
// expr.cpp: illustrates parsing and evaluating simple
//      arithmetic expressions over integers, +, -, *, and /
//      All operations are right-associative.
// grammar:
//    Expression -> Term + Expression | Term - Expression | Term
//    Term       -> Factor * Term | Factor / Term | Factor
//    Factor     -> number | ( Expression )
//    (where number is a terminal capturing the RE [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 Expr
{
public:
   virtual int value() const = 0;
   virtual string toString() const = 0;
};

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

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

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

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

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

class Div : public BinaryExpr
{
public:
   Div(Expr *l, Expr *r) : BinaryExpr(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;
}

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

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

Expr *expr(Tokenizer &tok)
{
   Expr *t = term(tok);
   if ( tok.next() == '+' )
   {
      tok.advance();
      return new Add(t, expr(tok));
   }
   else if ( tok.next() == '-' )
   {
      tok.advance();
      return new Subt(t, expr(tok));
   }
   else
      return t;
}

Expr *term(Tokenizer &tok)
{
   Expr *f = factor(tok);
   if ( tok.next() == '*' )
   {
      tok.advance();
      return new Mult(f, term(tok));
   }
   else if ( tok.next() == '/' )
   {
      tok.advance();
      return new Div(f, term(tok));
   }
   else
      return f;
}

Expr *factor(Tokenizer &tok)
{
   if ( tok.next() == 'i' )
   {
      int num = tok.next_value();
      tok.advance();
      return new Value(num);
   }
   else
   {
      if ( tok.next() != '(' )
         throw string("Unexpected token: ") + tok.next();
      tok.advance();
      Expr *e = expr(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]);
      Expr *e = expr(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;
}