#include <iostream>
#include <vector>
#include <math.h>
using namespace std;

class Token
{
    private:
    double value;
    char kind;

    public:
    void set(double v)  // set num token
    {
        (*this).value = v;
        this->kind = 'n';
    }
    void set(char c) // set char token
    {
        switch (c)
        {
            case '(': case ')': case '^': case '*': case '/':
            case '+': case '-': case 'q': case ';':
            {
                kind = c;
                value = 0;
                break;
            }
            default:
                cout << "Operator \'" << c << "\' is invalid.\n";

        }
    }
    double getvalue() const   // for functions that do not modify this
    {
        return value;
    }
    char getkind() const
    {
        return kind;
    }
    friend ostream& operator<<(ostream& out, const Token& t)
    {
        if (t.kind == 'n')
            out << t.value;
        else
            out << t.kind;
        return out;
    }

};


Token gettoken()  // this function reads one Token at a time
{
    Token t;
    double v;
    char c;

    cin >> c;
    switch(c)
    {
        case '(': case ')': case '^': case '*': case '/':
        case '+': case '-': case 'q': case ';':
        {
            t.set(c);
            return t;
        }
        case '.': case '0': case '1': case '2': case '3':
        case '4': case '5': case '6': case '7': case '8':
        case '9':
        {
            cin.putback(c);  // put it back into out stream
            cin >> v;
            t.set(v);
            return t;
        }
        default:
            cout << "Invalid character: \'" << c << "\'.\n";
            return t;
    }
}

double evaluate(vector<Token>& expr, size_t beg, size_t end)
{
    // regularization of -
    for (size_t i = beg; i < end; i++)
    {
        if (expr[i].getkind() == '-')
        {
            if ( i == beg )
            {
                expr[i].set(-expr[i+1].getvalue());
                expr.erase(expr.begin()+i+1);
            }
            else if ( expr[i-1].getkind() != 'n')
            {
                expr[i].set(-expr[i+1].getvalue());
                expr.erase(expr.begin()+i+1);
            }
        }
    }

    for (size_t i = end-1 ; i > beg; i--)
    {
        if (expr[i].getkind() == '^')
        {
            expr[i-1].set( pow(expr[i-1].getvalue(),expr[i+1].getvalue())  );
            expr.erase(expr.begin()+i); // removes ^
            expr.erase(expr.begin()+i); // removes right term
            end-=2;
        }
    }
    // handle mul and div
    for (size_t i = beg; i < end; i++)
    {
        if (expr[i].getkind() == '*')
        {
            expr[i-1].set( expr[i-1].getvalue() * expr[i+1].getvalue()  );
            expr.erase(expr.begin()+i); // removes *
            expr.erase(expr.begin()+i); // removes right term
            i--;
            end-=2;
        }
        else if (expr[i].getkind() == '/')
        {
            expr[i-1].set( expr[i-1].getvalue() / expr[i+1].getvalue()  );
            expr.erase(expr.begin()+i); // removes /
            expr.erase(expr.begin()+i); // removes right term
            i--;
            end-=2;
        }
    }

    // handle add and sub
    for (size_t i = beg; i < end; i++)
    {
        if (expr[i].getkind() == '+')
        {
            expr[i-1].set( expr[i-1].getvalue() + expr[i+1].getvalue()  );
            expr.erase(expr.begin()+i); // removes +
            expr.erase(expr.begin()+i); // removes right term
            i--;
            end-=2;
        }
        else if (expr[i].getkind() == '-')
        {
            expr[i-1].set( expr[i-1].getvalue() - expr[i+1].getvalue()  );
            expr.erase(expr.begin()+i); // removes -
            expr.erase(expr.begin()+i); // removes right term
            i--;
            end-=2;

        }
    }

    return expr[beg].getvalue();

}
double evaluate( vector<Token>& expr )
{
  while(expr.size() > 1)
  {
    for (size_t i = expr.size()-1; i > 1; i--)
    {
        if (expr[i].getkind() == ')')
        {
          size_t rparenpos = i;
          for (size_t i = 0; i < rparenpos; i++)
          {
              if (expr[i].getkind() == '(')
              {
                size_t lparenpos = i;
                evaluate(expr, lparenpos+1, rparenpos);
                expr.erase(expr.begin()+lparenpos);
                expr.erase(expr.begin()+lparenpos+1);
                i--;
              }
              else
              {
                  cout << "Invalid expression: parentheses not matched";
                  return 0;
              }
          }
        }
          else
          {
            evaluate(expr, 0, expr.size());
          }
      }
  }
  return expr[0].getvalue();
}
int main()
{
    vector<Token> expr;
    Token t;
    double exprval;

    cout << "Enter an algebraic expression such as (1+12.5)*4^2\n"
        << "For now we can handle only: +,-,*,/.\n"
        << "Finish expression with character \';\'"
        << endl;
    while (true)
    {
        t = gettoken();
        if (t.getkind()=='q')
            break;

        if ( t.getkind() == ';')
        {
            for(size_t i = 0; i < expr.size(); i++)
                cout << expr[i];
            exprval = evaluate(expr);
            cout << " = " << exprval << endl;
            expr.clear();
        }
        else
        {
            expr.push_back(t);
        }

    }

    cout << endl;
    return 0;
}