#include <iostream>
#include <cmath>
#include <cstdlib>
#include <string>

#define MAX_SIZE 20

using namespace std;

template<class T> class Stack
{
private:
    T item[MAX_SIZE];
    int top;

public:
    Stack()
    {
        top = -1;
    }

    void push(T data)
    {
        if(!this->is_full())
            item[++top] = data;
        else
        {
            cout << "Stack Error" << endl;
            exit(10);
        }
    }

    T pop()
    {
        if(!this->is_empty())
        {
            return item[top--];
        }
        else
        {
            cout << "Stack is Empty" << endl;
            exit(11);
        }
    }

    int size()
    {
        return top + 1;
    }

    bool is_empty()
    {
        if(top == -1)
            return true;
        else
            return false;
    }

    bool is_full()
    {
        if(top == MAX_SIZE - 1)
            return true;
        else
            return false;
    }

    void display()
    {
        for(int i = 0; i < this->size(); i++)
        {
            cout << item[i] << " ";
        }
        cout << endl;
    }

    T return_top()
    {
        return item[top];
    }
};

class Convert
{
private:
    bool num_flag;
    bool two_digit_flag;

public:
    Convert();
    string return_with_bracket(string infix);
    void to_Postfix(string infix,char postfix[]);
    bool prcd(char op1, char op2);
    int isOperand(char op);
    int isOperator(char op);
    bool return_flag()
    {
        return num_flag;
    }
};

Convert::Convert()
{
    this->num_flag = false;
    this->two_digit_flag = false;
}

string Convert::return_with_bracket(string infix)
{
    return("(" + infix + ")");
}

bool Convert::prcd(char op1, char op2)
{
    if((op1 == '+' || op1 == '-' || op1 == '*' || op1 == '/') && op2 == '(')
        return true;
    if(op1=='+' && op2=='+')
        return true;
    if(op1=='-' && op2=='-')
        return false;
    if(op1=='-' && op2=='+')
        return false;
    if(op1=='+' && op2=='-')
        return false;
    if(op1=='/' && op2=='/')
        return false;
    if(op1=='/' && (op2=='-' || op2=='+'))
        return true;
    if(op1=='*' && (op2=='+' || op2=='-'))
        return true;
    if((op1 == '-' || op1 == '+') && (op2 =='*' || op2 == '/'))
        return false;
    if((op1 == '$' || op1 == '+') && (op2 =='*' || op2 == '/' || op2=='-'))
        return true;
    if((op1 == '-' || op1 == '+' || op1 =='*' || op1 == '/')&& op2=='^')
        return false;
    if(op1 == '^' && ( op2 == '+' || op2 =='*' || op2 == '/' || op2=='-'))
        return false;
}

int Convert::isOperand(char op)
{
    return(op >= '0' && op <= '9');
}

int Convert::isOperator(char op)
{
    return(op =='+' || op =='-' || op == '/' || op =='*' || op =='^');
}

void Convert::to_Postfix(string infix, char postfix[])
{
    int position, outpos=0;
    char c;
    int count = 0;
    char temp;
    char stacktop;
    Stack<char> stack;

    for(position = 0; (c = infix[position]) != ''; position++)
    {

        if(this->isOperand(c))
        {
            postfix[outpos++] = c;
            this->num_flag = true;
            count++;

            if(count >= 2)
            {
                this->two_digit_flag = true;
            }
        }
        else if(this->isOperator(c))
        {
            count = 0;
            if(isOperator(infix[position]) && isOperator(infix[position + 1]))
            {
                cout << " '' aMissing argument in between " << infix[position] << " and " << infix[position + 1] << " in column " << position + 1 << endl;
                exit(9);
            }
            if(this->prcd(c, stacktop))
            {
                stacktop = stack.return_top();
                stack.push(c);
                stacktop = c;
            }
            else
            {
                while(true)
                {
                    temp = stack.pop();
                    postfix[outpos++] = temp;
                    stacktop = stack.return_top();

                    if(prcd(c, stacktop) || stacktop == '(')
                        break;
                }
                stack.push(c);
                stacktop = stack.return_top();
            }
        }
        else if(c == '(')
        {
            count = 0;
            stack.push(c);
            stacktop = stack.return_top();
        }
        else if(c == ')')
        {
            count = 0;
            while(1)
            {
                if(stack.size() == 0)
                {
                    cout << "Warning!! Number of ')' is greater than '('" << endl;
                    exit(2);
                }
                temp = stack.pop();
                if(temp != '(')
                {
                    postfix[outpos++] = temp;
                }
                else
                {
                    break;
                }
            }
            stacktop = stack.return_top();
        }
        else
        {
            cout << "Invalid input";
            exit(3);
        }
        if(infix[position] == ')' && infix[position + 1] == '(')
        {
            stack.push('*');
            stacktop = stack.return_top();
        }
    }
    if(stack.size() != 0)
    {
        cout << "Warning!!Number of '(' is greater than ')'" << endl;
        // exit(6);
    }
    if(!this->return_flag())
    {
        cout << "You must Enter Numeric value for calculation" << endl;
        cout << "This program cannot perform operations on variables";
        exit(5);
    }
    if(this->two_digit_flag)
    {
        cout << "Sory! Althoug u may  have entered right string" << endl;
        cout << "this program is only for single digit operation" << endl;
        exit(8);
    }
    postfix[outpos] = '';
}

class Evaluate
{
public:
    double eval(char expr[], Convert &);
    double oper(int symb, double op1, double op2);
};

double Evaluate::oper(int symb, double op1, double op2)
{
    switch(symb)
    {
        case '+': return (op1 + op2);
        case '-': return (op1 - op2);
        case '*': return (op1 * op2);
        case '/': return (op1 / op2);
        case '^': return (pow(op1, op2));
    }
}

double Evaluate::eval(char expr[], Convert &convert)
{
    int c, position;
    char temp1;
    int count = 0;
    double opnd1, opnd2, value;
    Stack<double> stack;
    for(position = 0; (c = expr[position]) != ''; position++)
    {
        if(convert.isOperand(c))
        {
            temp1 = double(c - '0');
            stack.push(temp1);
        }
        else
        {
            opnd2 = stack.pop();
            if(stack.size() == 0)
            {
                cout << "This program cannot process unary operation";
                exit(1);
            }
            opnd1 = stack.pop();
            value = oper(c, opnd1, opnd2);
            stack.push(value);
        }
    }
    if(stack.size() >= 2)
    {
        cout << "Sory! this program cannot calculate this" << endl;
        cout << "Enter +, *, /, - or ^ between bracket" << endl;
        exit(4);
    }
    return (stack.pop());
}

int main()
{
    Convert convert;
    Evaluate evaluate;
    string bracketted_infix;
    char infix[50], postfix[50];
    char choice;

    while(1)
    {
        cout << "Enter string: ";
        cin  >> infix;
        cout << endl;
        cout << "Entered String: " << infix << endl;

        bracketted_infix = convert.return_with_bracket(infix);
        convert.to_Postfix(bracketted_infix, postfix);

        cout << "Equivalent Postfix string: " << postfix << endl;
        cout << "RESULT: ";
        cout << evaluate.eval(postfix, convert);
        cout << "nCalculate another string?(y/n) ";
        cin  >> choice;
        cout << endl;

        if(choice == 'n')
            break;
    }
    return 0;
}