#include <iostream>
#include <stack>
#include <cmath>
#include <string>
using namespace std;



string convertInfixToPostfix(string infix);
int operatorPrecedence(char ch);
int evaluatepostfExp(string postfix);
int calculate(int a, int b, char operatorSign);

int main()
{
    string infExp, postfExp;
    int result;


    infExp = "8*(3+4)/2-3*5";

    postfExp = convertInfixToPostfix(infExp);

    cout<<"Infix Expression: "<<infExp<<endl;
    cout<<"Postfix Expression: "<<postfExp<<endl;

    result = evaluatepostfExp(postfExp);

    cout<<"\nResult is: "<<result<<endl;

    return 0;
}

//INFIX to POSTFIX conversion
string convertInfixToPostfix(string infix)
{
    string postfix = "";
    stack <char> myStack;
    char ch;

    for(int i=0; infix[i]; i++)
    {
        ch = infix[i];

        if(ch=='(') //if found opening bracket
            myStack.push(ch);
        else if(ch==')') //if found closing bracket
        {
            while(!myStack.empty() && myStack.top()!='(')
            {
                postfix = postfix + myStack.top();
                myStack.pop();
            }

            if(!myStack.empty() && myStack.top()=='(')
               myStack.pop();

        }
        else //found operator or operand
        {
            int priority = operatorPrecedence(ch);                  //^ is highest, then * and /. then + and -

            if(priority==0)                                         //found operand
                postfix = postfix + ch;
            else                                                    //found operator
            {
                if(myStack.empty())
                    myStack.push(ch);
                else
                {
                    while(!myStack.empty()
                          && myStack.top()!='('
                            && priority<=operatorPrecedence(myStack.top()))
                    {
                        postfix = postfix + myStack.top();
                        myStack.pop();
                    }
                    myStack.push(ch);
                }

            }
        }
    }

    while(!myStack.empty())
    {
        postfix += myStack.top();
        myStack.pop();
    }

    return postfix;
}


// POSTFIX evaluation to get result
int evaluatepostfExp(string postfix)
{
    stack <int> StackSaya;
    char ch;
    //1 2 3 ^ 4 * + 3 /
    for(int i=0; postfix[i]; i++)
    {
        ch = postfix[i];
        if(ch>='0' && ch<='9') //found operand
            StackSaya.push(ch-'0'); //char to int conversion
        else //found operator
        {
            int a,b;
            b = StackSaya.top();
            StackSaya.pop();

            a = StackSaya.top();
            StackSaya.pop();

            StackSaya.push(calculate(a, b, ch));
        }
    }

    return StackSaya.top();
}


// Calculation, according to arithmetic operator sign
int calculate(int a, int b, char operatorSign)
{
    if(operatorSign=='+')
        return a+b;
    else if(operatorSign=='-')
        return a-b;
   else if(operatorSign=='*')
        return a*b;
   else if(operatorSign=='/')
        return a/b;
     else if(operatorSign=='^')
        return pow(a,b);

}


// Operator precedence. You can add more operator like % (MOD)
int operatorPrecedence(char ch)
{
    if(ch=='^')
        return 3; //highest priority for exponential operator
    else if(ch=='/' || ch=='*')
        return 2; //high priority than + or - operator
    else if(ch=='+' || ch=='-')
        return 1; //lowest priority among operators
    else
        return 0; //works for operands

}