#include <cctype>
#include <iostream>
#include <iomanip>
#include <map>
#include <string>
#include <sstream>
#include <vector>

namespace TinyCalc { 

// storage of variables

class Var {
  private:
    double _value;
  public:
    Var(): _value() { }
    ~Var() = default;
    double get() const { return _value; }
    void set(double value) { _value = value; }
};

typedef std::map<std::string, Var> VarTable;

// abstract syntax tree -> storage of "executable"

namespace AST {

class Expr {
  protected:
    Expr() = default;
  public:
    virtual ~Expr() = default;
  public:
    virtual double solve() const = 0;
};

class ExprConst: public Expr {
  private:
    double _value;
  public:
    ExprConst(double value): Expr(), _value(value) { }
    virtual ~ExprConst() = default;
    virtual double solve() const { return _value; }
};

class ExprVar: public Expr {
  private:
    Var *_pVar;
  public:
    ExprVar(Var *pVar): Expr(), _pVar(pVar) { }
    virtual ~ExprVar() = default;
    virtual double solve() const { return _pVar->get(); }
};

class ExprUnOp: public Expr {
  protected:
    Expr *_pArg1;
  protected:
    ExprUnOp(Expr *pArg1): Expr(), _pArg1(pArg1) { }
    virtual ~ExprUnOp() { delete _pArg1; }
};

class ExprUnOpNeg: public ExprUnOp {
  public:
    ExprUnOpNeg(Expr *pArg1): ExprUnOp(pArg1) { }
    virtual ~ExprUnOpNeg() = default;
    virtual double solve() const
    {
      return -_pArg1->solve();
    }
};

class ExprBinOp: public Expr {
  protected:
    Expr *_pArg1, *_pArg2;
  protected:
    ExprBinOp(Expr *pArg1, Expr *pArg2):
      Expr(), _pArg1(pArg1), _pArg2(pArg2)
    { }
    virtual ~ExprBinOp() { delete _pArg1; delete _pArg2; }
};

class ExprBinOpAdd: public ExprBinOp {
  public:
    ExprBinOpAdd(Expr *pArg1, Expr *pArg2): ExprBinOp(pArg1, pArg2) { }
    virtual ~ExprBinOpAdd() = default;
    virtual double solve() const
    {
      return _pArg1->solve() + _pArg2->solve();
    }
};

class ExprBinOpSub: public ExprBinOp {
  public:
    ExprBinOpSub(Expr *pArg1, Expr *pArg2): ExprBinOp(pArg1, pArg2) { }
    virtual ~ExprBinOpSub() = default;
    virtual double solve() const
    {
      return _pArg1->solve() - _pArg2->solve();
    }
};

class ExprBinOpMul: public ExprBinOp {
  public:
    ExprBinOpMul(Expr *pArg1, Expr *pArg2): ExprBinOp(pArg1, pArg2) { }
    virtual ~ExprBinOpMul() = default;
    virtual double solve() const
    {
      return _pArg1->solve() * _pArg2->solve();
    }
};

class ExprBinOpDiv: public ExprBinOp {
  public:
    ExprBinOpDiv(Expr *pArg1, Expr *pArg2): ExprBinOp(pArg1, pArg2) { }
    virtual ~ExprBinOpDiv() = default;
    virtual double solve() const
    {
      return _pArg1->solve() / _pArg2->solve();
    }
};

} // namespace AST

// token class - produced in scanner, consumed in parser
struct Token {
  // tokens
  enum Tk {
    Plus, Minus, Star, Slash, LParen, RParen, Semicolon,
    Number, Id,
    EOT, Error
  };
  // token number
  Tk tk;
  // lexem as floating point number
  double number;
  // lexem as identifier
  std::string id;
  
  // constructors.
  explicit Token(Tk tk): tk(tk), number() { }
  explicit Token(double number): tk(Number), number(number) { }
  explicit Token(const std::string &id): tk(Id), number(), id(id) { }
};

// the scanner - groups characters to tokens
class Scanner {
  private:
    std::istream &_in;

  public:
    // constructor.
    Scanner(std::istream &in): _in(in) { }

    /* groups characters to next token until the first character
     * which does not match (or end-of-file is reached).
     */
    Token scan()
    {
      char c;
      // skip white space
      do {
        if (!(_in >> c)) return Token(Token::EOT);
      } while (isspace(c));
      // classify character and build token
      switch (c) {
        case '+': return Token(Token::Plus);
        case '-': return Token(Token::Minus);
        case '*': return Token(Token::Star);
        case '/': return Token(Token::Slash);
        case '(': return Token(Token::LParen);
        case ')': return Token(Token::RParen);
        case ';': return Token(Token::Semicolon);
        default:
          if (isdigit(c)) {
            _in.unget(); double value; _in >> value;
            return Token(value);
          } else if (isalpha(c) || c == '_') {
            std::string id(1, c);
            while (_in >> c) {
              if (isalnum(c) || c == '_') id += c;
              else { _in.unget(); break; }
            }
            return Token(id);
          } else {
            _in.unget();
            return Token(Token::Error);
          }
      }
    }
};

/* parser
 *
 * This is a recursive descent parser with a look-ahead of one symbol
 * and without back-tracking.
 * The parser implements the following grammar:
 *
 * program
 *   : expr Semicolon program
 *   | <empty>
 *   ;
 *
 * expr
 *   : addExpr
 *   ;
 * 
 * addExpr
 *   : mulExpr addExprRest
 *   ;
 *   
 * addExprRest
 *   : addOp mulExpr addExprRest
 *   | <empty>
 *   ;
 *   
 * mulExpr
 *   : unaryExpr mulExprRest
 *   ;
 *   
 * mulExprRest
 *   : mulOp unaryExpr mulExprRest
 *   | <empty>
 *   ;
 * 
 * mulOp
 *   : Star | Slash
 *   ;
 *   
 * unaryExpr
 *   : unOp unaryExpr
 *   | primExpr
 *   ;
 * 
 * unOp
 *   : Plus | Minus
 *   ;
 *   
 * primExpr
 *   : Number
 *   | Id
 *   | LParen expr RParen
 *   ;
 */
class Parser {
  private:
    Scanner _scanner;
    VarTable &_varTable;
    Token _lookAhead;

  private:
    // constructor.
    Parser(std::istream &in, VarTable &varTable):
      _scanner(in), _varTable(varTable), _lookAhead(Token::EOT)
    {
      scan(); // load look ahead initially
    }

    // calls the scanner to read the next look ahead token.
    void scan() { _lookAhead = _scanner.scan(); }

    // consumes a specific token.
    bool match(Token::Tk tk)
    {
      if (_lookAhead.tk != tk) {
        std::cerr << "SYNTAX ERROR! Unexpected token!" << std::endl;
        return false;
      }
      scan();
      return true;
    }

    // the rules:

    std::vector<AST::Expr*> parseProgram()
    {
      // right recursive rule
      // -> can be done as iteration
      std::vector<AST::Expr*> pExprs;
      for (;;) {
        if (AST::Expr *pExpr = parseExpr()) {
          pExprs.push_back(pExpr);
        } else break;
        // special error checking for missing ';' (usual error)
        if (_lookAhead.tk != Token::Semicolon) {
          std::cerr << "SYNTAX ERROR: Semicolon expected!" << std::endl;
          break;
        }
        scan(); // consume semicolon
        if (_lookAhead.tk == Token::EOT) return pExprs;
      }
      // error handling
      for (AST::Expr *pExpr : pExprs) delete pExpr;
      pExprs.clear();
      return pExprs;
    }
    
    AST::Expr* parseExpr()
    {
      return parseAddExpr();
    }

    AST::Expr* parseAddExpr()
    {
      if (AST::Expr *pExpr1 = parseMulExpr()) {
        return parseAddExprRest(pExpr1);
      } else return nullptr; // ERROR!
    }

    AST::Expr* parseAddExprRest(AST::Expr *pExpr1)
    {
      // right recursive rule for left associative operators
      // -> can be done as iteration
      for (;;) {
        switch (_lookAhead.tk) {
          case Token::Plus:
            scan(); // consume token
            if (AST::Expr *pExpr2 = parseMulExpr()) {
              pExpr1 = new AST::ExprBinOpAdd(pExpr1, pExpr2);
            } else {
              delete pExpr1;
              return nullptr; // ERROR!
            }
            break;
          case Token::Minus:
            scan(); // consume token
            if (AST::Expr *pExpr2 = parseMulExpr()) {
              pExpr1 = new AST::ExprBinOpSub(pExpr1, pExpr2);
            } else {
              delete pExpr1;
              return nullptr; // ERROR!
            }
            break;
          case Token::Error:
            std::cerr << "SYNTAX ERROR: Unexpected character!" << std::endl;
            delete pExpr1;
            return nullptr;
          default: return pExpr1;
        }
      }
    }
    
    AST::Expr* parseMulExpr()
    {
      if (AST::Expr *pExpr1 = parseUnExpr()) {
        return parseMulExprRest(pExpr1);
      } else return nullptr; // ERROR!
    }
    
    AST::Expr* parseMulExprRest(AST::Expr *pExpr1)
    {
      // right recursive rule for left associative operators
      // -> can be done as iteration
      for (;;) {
        switch (_lookAhead.tk) {
          case Token::Star:
            scan(); // consume token
            if (AST::Expr *pExpr2 = parseUnExpr()) {
              pExpr1 = new AST::ExprBinOpMul(pExpr1, pExpr2);
            } else {
              delete pExpr1;
              return nullptr; // ERROR!
            }
            break;
          case Token::Slash:
            scan(); // consume token
            if (AST::Expr *pExpr2 = parseUnExpr()) {
              pExpr1 = new AST::ExprBinOpDiv(pExpr1, pExpr2);
            } else {
              delete pExpr1;
              return nullptr; // ERROR!
            }
            break;
          case Token::Error:
            std::cerr << "SYNTAX ERROR: Unexpected character!" << std::endl;
            delete pExpr1;
            return nullptr;
          default: return pExpr1;
        }
      }
    }

    AST::Expr* parseUnExpr()
    {
      // right recursive rule right recursive operators
      // -> must be done as recursion
      switch (_lookAhead.tk) {
        case Token::Plus:
          scan(); // consume token
          // as a unary plus has no effect it is simply ignored
          return parseUnExpr();
        case Token::Minus:
          scan();
          if (AST::Expr *pExpr = parseUnExpr()) {
            return new AST::ExprUnOpNeg(pExpr);
          } else return nullptr; // ERROR!
        default:
          return parsePrimExpr();
      }
    }
    
    AST::Expr* parsePrimExpr()
    {
      AST::Expr *pExpr = nullptr;
      switch (_lookAhead.tk) {
        case Token::Number:
          pExpr = new AST::ExprConst(_lookAhead.number);
          scan(); // consume token
          break;
        case Token::Id: {
          Var &var = _varTable[_lookAhead.id]; // find or create
          pExpr = new AST::ExprVar(&var);
          scan(); // consume token
        } break;
        case Token::LParen:
          scan(); // consume token
          if (!(pExpr = parseExpr())) return nullptr; // ERROR!
          if (!match(Token::RParen)) {
            delete pExpr; return nullptr; // ERROR!
          }
          break;
        case Token::EOT:
          std::cerr << "SYNTAX ERROR: Premature EOF!" << std::endl;
          break;
        case Token::Error:
          std::cerr << "SYNTAX ERROR: Unexpected character!" << std::endl;
          break;
        default:
          std::cerr << "SYNTAX ERROR: Unexpected token!" << std::endl;
      }
      return pExpr;
    }
    
  public:

    // the parser function
    static std::vector<AST::Expr*> parse(
      std::istream &in, VarTable &varTable)
    {
      Parser parser(in, varTable);
      return parser.parseProgram();
    }
};

} // namespace TinyCalc

// a sample application

using namespace std;
using namespace TinyCalc;

int main()
{
  // the program:
  const char *sourceCode =
    "1 + 2 * 3 / 4 - 5;\n"
    "a + b;\n"
    "a - b;\n"
    "a * b;\n"
    "a / b;\n"
    "a * (b + 3);\n";
  // the variables
  const char *vars[] = { "a", "b" };
  enum { nVars = sizeof vars / sizeof *vars };
  // the data
  const double data[][nVars] = {
    { 4.0, 2.0 },
    { 2.0, 4.0 },
    { 10.0, 5.0 },
    { 42, 6 * 7 }
  };
  // compile program
  stringstream in(sourceCode);
  VarTable varTable;
  vector<AST::Expr*> program = Parser::parse(in, varTable);
  if (program.empty()) {
    cerr << "ERROR: Compile failed!" << endl;
    string line;
    if (getline(in, line)) {
      cerr << "Text at error: '" << line << "'" << endl;
    }
    return 1;
  }
  // apply program to the data
  enum { nDataSets = sizeof data / sizeof *data };
  for (size_t i = 0; i < nDataSets; ++i) {
    const char *sep = "";
    cout << "Data Set:" << endl;
    for (size_t j = 0; j < nVars; ++j, sep = ", ") {
      cout << sep << vars[j] << ": " << data[i][j];
    }
    cout << endl;
    // load data
    for (size_t j = 0; j < nVars; ++j) varTable[vars[j]].set(data[i][j]);
    // perform program
    cout << "Compute:" << endl;
    istringstream in(sourceCode);
    for (const AST::Expr *pExpr : program) {
      string line; getline(in, line);
      cout << line << ": " << pExpr->solve() << endl;
    }
    cout << endl;
  }
  // clear the program
  for (AST::Expr *pExpr : program) delete pExpr;
  program.clear();
  // done
  return 0;  
}