#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>

using namespace std;

#include <stack>

const int MAX=50;
/////////////////////////////////
void addSpace(char *ch,int &i)
{
    ch[i]='_';
    i++;
}
/////////////////////////////////
void addChar(char *ch,int &i, char tp)
{
    ch[i]=tp;
    i++;
}
/////////////////////////////////
bool isOperator(char op1) // calculate
{
    if (op1=='+' || op1=='-' || op1=='*' || op1=='/' || op1=='^')
        return true;
    return false;
}
/////////////////////////////////
bool compPrior(char op1, char op2) // compare
{
    const int Op=6;
    char opers[Op]={'+', '-', '*', '/', '(', '^'};
    int priors[Op]={ 1 ,  1 ,  2 ,  2 ,  0 ,  3 };
    int op1p=0, op2p=0, i;
    for (i=0; i<Op; i++)
    {
        if(op1==opers[i])
            op1p=i;
        if(op2==opers[i])
            op2p=i;
    }
    if(priors[op1p]<=priors[op2p])
        return 1;
    return 0;
}
/////////////////////////////////
void convertPolish(char *ex, char *pl)
{
    //STACK//

    stack <char> stk;

    //CONVERTING//
    unsigned long int ln=strlen(ex);
    int k=0; //counter for pl
    int i=0; //counter for ex
    while (ln!=i)
    {
        if (isdigit(ex[i]))
        {
            addSpace(pl, k);
            while(isdigit(ex[i]))
            {
                addChar(pl, k, ex[i]);
                i++;
            }
        }
        else if (ex[i]=='(') //   (
        {
            stk.push(ex[i]);
            i++;
        }
        else if (ex[i]==')') //   )
        {
            char elem;
            do
            {
                elem=stk.top();
                stk.pop();
                if (elem!='(')
                {
                    addChar(pl, k, elem);
                }
            } while (elem!='(');
            i++;
        }
        else if (isOperator(ex[i]))  // operation
        {
            char temp=ex[i];
            char a;
            if(!stk.empty())
            {
                a=stk.top();
                while (compPrior(temp, a) && !stk.empty())
                {
                    char elem=stk.top();
                    if(!stk.empty())
                        stk.pop();
                    addSpace(pl, k);
                    addChar(pl, k, elem);
                    if(!stk.empty())
                        a=stk.top();
                }
            }
            stk.push(temp);
            i++;
        }
    }
    while (!stk.empty())
    {
        char elem=stk.top();
        stk.pop();
        addSpace(pl, k);
        addChar(pl, k, elem);
    }
}
/////////////////////////////////
int calculatePolish(char *pl)
{
    //STACK//

    stack<int> stk;

    //CALCULATING//
    unsigned long int pllen=strlen(pl);
    int i=0; // counter
    while (i<=pllen) //
    {
        if (stk.size()==1 && i>=pllen-1)
            return stk.top();
        else if(pl[i]=='_')
            i++;
        else if (isdigit(pl[i]))
        {
            char tempnum [pllen];
            int v=0; // counter
            while(isdigit(pl[i]))
            {
                tempnum[v]=pl[i];
                v++;
                i++;
            }
            stk.push(atoi(tempnum));
            v=0;
        }
        else if (isOperator(pl[i]))
        {
            if(pl[i]=='+')
            {
                int a= stk.top();
                stk.pop();
                a+=stk.top();
                stk.pop();
                i+=2;
                stk.push(a);
            }
            else if(pl[i]=='-')
            {
                int a= stk.top();
                stk.pop();
                a=stk.top()-a;
                stk.pop();
                i+=2;
                stk.push(a);
            }
            else if(pl[i]=='*')
            {
                int a= stk.top();
                stk.pop();
                a*=stk.top();
                stk.pop();
                i+=2;
                stk.push(a);
            }
            else if(pl[i]=='/')
            {
                int a= stk.top();
                stk.pop();
                a=stk.top()/a;
                stk.pop();
                i+=2;
                stk.push(a);
            }
            else if(pl[i]=='^')
            {
                int a= stk.top();
                stk.pop();
                a=pow(stk.top(), a);
                stk.pop();
                i+=2;
                stk.push(a);
            }
        }


    }
    return stk.top();
}
/////////////////////////////////
bool checkBrckts(char *ex)
{
    //STACK//

    stack<char> stk;

    //CHECKING//
    unsigned long int ln=strlen(ex);
    for (int i=0; i<ln ; i++)
    {
        if (ex[i]=='(')
            stk.push(ex[i]);
        if (ex[i]==')')
        {
            char tempchar = stk.top();
            stk.pop();
            if (tempchar!='(')
                return false;
        }
    }
    if (stk.empty())
        return true;
    else
        return false;
}
/////////////////////////////////
bool checkChar(char *ex)
{
    //CHECKING//
    unsigned long int ln=strlen(ex);
    for (int i=0; i<ln ; i++)
    {
        if (isOperator(ex[i]) || isdigit(ex[i]) || ex[i]=='(' || ex[i]==')')
            i++;
        else
            return false;
    }
    return true;
}
/////////////////////////////////
int main()
{
    //EXPRESSION//

    char expr [MAX];
    cout<<"Input your expression: ";
    cin.getline(expr, MAX);

    //EXPRESSION CONTROL//

    if(!checkChar(expr))
    {
        cout<<"Check the correctness of your expression"<<endl;;
        return 0;
    }

    if(!checkBrckts(expr))
    {
        cout<<"Check brackets int your expression"<<endl;;
        return 0;
    }

    //INITIALIZATION//

    char *polish = new char [MAX];

    //CONVERTING//

    convertPolish(expr, polish);
    cout<<"Your expression in polish notation: "<<polish<<endl;

    //CALCULATING//

    cout<<"Calculating your expression..."<<endl;
    cout<<"Your result is: "<<calculatePolish(polish)<<endl;

    //DElETING//
    delete [] polish;

    return 0;
}