//
// 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;
  }
}

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

// if command line arguments given, use those for string, otherwise
//   prompt user for expression and use that
//   (the prompt for an expression is important in Windows where
//   one apparently can't escape a '*')
Tokenizer *build_tokenizer(int argc, char *args[])
{
  Tokenizer *tok = new Tokenizer();
  if ( argc >= 2 ) {
    for(int i = 1; i < argc; ++i)
      tok->add(args[i]);
  } else {
    cout << "Enter expression (with spaces around tokens):" << endl;
    string input_text;
    getline(cin, input_text);
    istringstream sstext(input_text);
    string word;
    while ( sstext >> word ) {
      tok->add(word);
    }
  }
  return tok;
}

int main(int argc, char* args[])
{
  try
  {
    Tokenizer *tok = build_tokenizer(argc, args);
    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;
}