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

using namespace std;

// Wyrażenia //////////////////////////////////////////////////////

typedef map<string, int> Memory;

class Expression
{
  public:
    virtual int eval(Memory& m) = 0;
    virtual ~Expression() {}
};

class Constant : public Expression
{
    int value;

  public:
    Constant(int v) : value(v) {}

    virtual int eval(Memory& m)
    {
      return value;
    }
};

class Unknown_operator { };

class Binary_operator : public Expression
{
    char symbol;
    Expression *left, *right;

  public:
    Binary_operator(char s, Expression* l, Expression* r)
      : symbol(s), left(l), right(r) {}

    virtual ~Binary_operator()
    {
      delete left;
      delete right;
    }

    virtual int eval(Memory& m)
    {
      switch (symbol)
      {
        case '*': return left->eval(m) * right->eval(m);
        case '+': return left->eval(m) + right->eval(m);
        case '-': return left->eval(m) - right->eval(m);
        case '/': return left->eval(m) / right->eval(m);
        case '%': return left->eval(m) % right->eval(m);
        default : throw Unknown_operator();
      }
    }
};

class Variable_not_found { };

class Variable : public Expression
{
    string name;

  public:
    Variable(string n) : name(n) { }
  
    virtual int eval(Memory& m)
    {
      Memory::iterator it = m.find(name);
      if (it == m.end())
        throw Variable_not_found();
      return it->second;
    }
};

// Parser ///////////////////////////////////////////////////////////

const char EOS = NULL;

class Not_parsed { };

class Parser
{
    string input;    // analizowany tekst
    size_t position; // aktualnie "oglądany" znak

  public:

    Parser(string input);

    void skip_whitespace(); // pomija wszystkie białe znaki i przesuwa wskaźnik na pierwszy znak, który nie jest biały
    char look_ahead();      // pomija białe znaki i informuje jaki znak "oglądamy"

    Expression* parse_Expression(); // parsuje wyrażanie
    Expression* parse_sum();        // parsuje "sumę"
    Expression* parse_mult();       // parsuje skłądnik
    Expression* parse_term();       // parsuje czynnik
    Expression* parse_Constant();   // parsuje liczbę
    Expression* parse_Variable();   // parsuje nazwę zeminnej
    Expression* parse_paren();      // parsuje "sumę" w nawiasie
};

Parser::Parser(string input) : input(input), position(0)
{
  input.push_back(EOS);
}

void Parser::skip_whitespace()
{
  while (isspace(input[position]))
    position++;
}

char Parser::look_ahead()
{
  skip_whitespace();
  return input[position];
}

Expression* Parser::parse_Expression()
{
  Expression* e = parse_sum();
  if (look_ahead() == EOS)
    return e;
  else
  {
    delete e;
    throw Not_parsed();
  }
}

Expression* Parser::parse_sum()
{
  Expression* e = NULL;

  try
  {
    e = parse_mult();
    char c = look_ahead();

    while(c == '+' || c == '-')
    {
      position++;
      e = new Binary_operator(c, e, parse_mult());
      c = look_ahead();
    }
  }
  catch (Not_parsed)
  {
    delete e;
    throw Not_parsed();
  }

  return e;
}

Expression* Parser::parse_mult()
{
  Expression* e = NULL;
  
  try
  {
    e = parse_term();
    char c = look_ahead();
  
    while(c == '*' || c == '/' || c == '%')
    {
      position++;
      e = new Binary_operator(c, e, parse_term());
      c = look_ahead();
    }
  }
  catch (Not_parsed)
  {
    delete e;
    throw Not_parsed();
  }

  return e;
}

Expression* Parser::parse_term()
{
  char c = look_ahead();
  if (c == '(')
    return parse_paren();
  else if (isdigit(c))
    return parse_Constant();
  else if (isalpha(c))
    return parse_Variable();
  else
    throw Not_parsed();
}

Expression* Parser::parse_Constant()
{
  int n = 0;
  while (isdigit(input[position]))
  {
    n *= 10;
    n += input[position] - '0';
    position++;
  }
  return new Constant(n);
}

Expression* Parser::parse_Variable()
{
  string s;
  while (isalnum(input[position]))
  {
    s.push_back(input[position]);
    position++;
  }
  return new Variable(s);
}

Expression* Parser::parse_paren()
{
  position++; // parse_term zapewnia, że wskaznik stoi na nawiasie otwierajacym '('
  Expression* e = parse_sum();
  if (look_ahead() == ')')
  {
    position++;
    return e;
  }
  else
  {
    delete e;
    throw Not_parsed();
  }
}

// Main /////////////////////////////////////////////////////////////

int main()
{
  cout << "Wpisz wyrażenie: ";

  string input;
  getline(cin, input);
  
  try
  {
    Parser parser(input);
    Expression* e = parser.parse_Expression();

    Memory m;
    cout << "wynik: " << e->eval(m) << endl;
  }
  catch (Not_parsed)
  {
    cout << "BŁĄD: Wyrażenie się nie parsuje" << endl;
  }
  catch (Variable_not_found)
  {
    cout << "BŁAD: Kalkulator nie używa zmiennych" << endl;
  }

  return 0;
}