//
// simple-expr.cpp: illustrates parsing and evaluating simple
//      arithmetic expressions over integers, +, *
//      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
//

#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 Multiply : public BinaryExpression
{
public:
  Multiply(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 is_num(const string&) const;
  int  num_value(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 at_end() 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::is_num(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::num_value(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 ( is_num(next_word) )
  {
    tokens.push_back("i");
    tokens.push_back(next_word);
  }
  else
    throw string("Invalid token: " + next_word);
}

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

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

char Tokenizer::next() const
{
  if ( at_end() )
    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 = num_value(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() == '+' )
  {
    char op = tok.next();
    tok.advance();
    Expression *next_term = term(tok);
    result = new Add(result, next_term);
  }
  return result;
}

Expression *term(Tokenizer &tok)
{
  Expression *result = factor(tok);
  while ( tok.next() == '*' )
  {
    char op = tok.next();
    tok.advance();
    Expression *next_factor = factor(tok);
    result = new Multiply(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 ( false ) // can comment out this line for demos of the core classes
  {
    // Hardcoded examples of expressions
    // compute 13 + 21:
    Expression *random = new Add(new Value(13), new Value(21));
    cout << "Adding: " << random->toString() << " gives " << random->value() << endl;
    // compute ((3 + 4) + 5) * 8
    Expression *left_part = new Add(new Add(new Value(3), new Value(4)), new Value(5));
    Expression *right_part = new Value(8);
    Expression *full = new Multiply(left_part, right_part);
    cout << "Full expression with parens: " + full->toString() << endl;
    cout << "Value of full expression: " << full->value() << endl;
    cout << endl;
    return 0;
  }

  cout << "Enter expression: ";
  string input_text;
  getline(cin, input_text);
  istringstream sstext(input_text);
  Tokenizer tok;
  string word;
  while ( sstext >> word ) {
    tok.add(word);
  }
  try
  {
    Expression *e = expression(tok);
    if ( !tok.at_end() )
      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;
}