#include <iostream>
#include <stack>
#include <string>
#include <cstdlib>

using namespace std;

/**
   Sprawdza, czy token jest operatorem.
   @param token token
   @return wartość true, jeśli token jest jednym ze znaków: + - * / ^
*/
bool is_operator(string token)
{  
   return token == "+" || token == "-" || token == "*" || token == "/";
}

/**
   Sprawdza, czy token jest cyfrą.
   @param token token
   @return wartość true, jeśli token jest jedną z cyfr: 0 1 2 3 4 5 6 7 8 9
*/
bool is_digit(string token)
{  
   return token.length() == 1 && "0" <= token && token <= "9";
}

/**
   Oblicza priorytet operatora.
   @param op operator
   @return priorytet (1 = najniższy, 3 = najwyższy)
*/
int precedence(string op)
{  
   if (op == "+" || op == "-") { return 1; }
   else if (op == "*" || op == "/") { return 2; }
   else { return 0; }
}

/**
   Wyświetla komunikat o błędzie i wychodzi.
   @param message informacja o błędzie
*/
void error(string message)
{  
   cout << "BLAD: " << message << "." << endl;
   exit(1);
}

class ExpressionCalculator
{
public:
   /**
      Oblicza wartość podanego wyrażenia.
      @param expression wyrażenie zawierające liczby całkowite,
      operatory arytmetyczne i nawiasy
   */
   int evaluate(string expression);
   /** 
      Oblicza nową wartość i odkłada ją na stos.
   */
   void evaluate_top();
private:
   stack<int> numstack;
   stack<string> opstack;
};

void ExpressionCalculator::evaluate_top()
{
   if (opstack.size() == 0) { error("Błąd składni"); }
   string op = opstack.top();
   opstack.pop();
   if (numstack.size() == 0) { error("Błąd składni"); }
   int y = numstack.top();
   numstack.pop();
   if (numstack.size() == 0) { error("Błąd składni"); }
   int x = numstack.top();
   numstack.pop();
   int z = 0;
   if (op == "*") { z = x * y; }
   else if (op == "/")
   {  
      if (y == 0) { error("Dzielenie przez 0"); }
      else { z = x / y; }
   }
   else if (op == "+") { z = x + y; }
   else if (op == "-") { z = x - y; }
   else { error("Błąd składni"); }
   numstack.push(z);
}

int ExpressionCalculator::evaluate(string expression)
{
   int pos = 0;
   while (pos < expression.length())
   {  
      string ch = expression.substr(pos, 1);
      pos++;
      if (is_operator(ch))
      {
         while (opstack.size() > 0 &&
            precedence(opstack.top()) >= precedence(ch))
         {
            evaluate_top();
         }
         
         opstack.push(ch);
      }
      else if (ch == "(") { opstack.push(ch); }
      else if (ch == ")")
      {  
         bool done = false;
         while (!done)
         {  
            if (opstack.size() == 0) { error("Brak pasującego znaku ("); }
            if (opstack.top() == "(") { opstack.pop(); done = true; }
            else { evaluate_top(); }
         }
      }
      else if (is_digit(ch))
      {
         int start = pos - 1;
         while (pos < expression.length() 
            && is_digit(expression.substr(pos, 1))) { pos++; }
         string num = expression.substr(start, pos - start);
         numstack.push(stoi(num));
      }
      else if (ch != " ")
      {
         error ("Oczekiwana liczba, operator lub nawias.");
      }
   }
   while (opstack.size() > 0)
   {  
      if (opstack.top() == "(") { error("Brak pasującego znaku )"); }
      else { evaluate_top(); }
   }
   if (numstack.size() != 1) { error("Błąd składni"); }
   int result = numstack.top();
   numstack.pop();
   return result;
}

/*
   Program ten oblicza wartość wyrażeń arytmetycznych przy użyciu dwóch stosów.
*/
int main()
{  
   cout << "Wprowadź wyrażenie arytmetyczne, np. (3+4)*5: ";
   string expr;
   getline(cin, expr);
   ExpressionCalculator calc;
   cout << calc.evaluate(expr) << endl;
  
   return 0;
}

