#include <bits/stdc++.h>
using namespace std;

int Operator(char ch)
{
    if (ch == '^' || ch == '*' || ch == '/' || ch == '+' || ch == '-')
    {
        return 1;
    }
    return 0;
}
int operator_val(char ch)
{
    if (ch == '^')
        return 3;
    else if (ch == '*' || ch == '/')
        return 2;
    else if (ch == '+' || ch == '-')
        return 1;

    return 0;
}

int main()
{
    stack<char> st;
    char q[500], p[500];
    int i, j, top = 0, p_idx = 0;

    st.push('(');
    printf("Enter the expression (no space): ");
    gets(q);

    strcat(q, ")");

    for (i = 0; i < strlen(q); i++)
    {
        char ch = q[i];
        if (isdigit(ch))
        {
            p[p_idx++] = ch;
        }
        else if (ch == '(')
        {
            st.push(ch);
        }
        else if (Operator(ch) == 1)
        {
            char temp = st.top();
            st.pop();

            while (Operator(temp) == 1 && operator_val(temp) >= operator_val(ch) && top > 0)
            {
                p[p_idx++] = temp;
                temp = st.top();
                st.pop();
            }
            st.push(temp);
            st.push(ch);
        }
        else if (ch == ')')
        {
            char temp;
            temp = st.top();
            st.pop();
            while (temp != '(')
            {
                p[p_idx++] = temp;
                temp = st.top();
                st.pop();
            }
        }
    }



    // evaluating the postfix expression

    int a, b, size, item, k = 0, l = 0;
    j = 0, top = 0;
    char ch, temp[100];

    stack<int> st1;


    while (k < p_idx * 2 - 1)
    {
        if (k % 2 == 1) ch = ',';
        if (k % 2 == 0) ch = p[l++]; // inserting the elements from the user

        if (ch == ')') // checking the end of the expression.
        {
            break;
        }
        else if (ch == '*' || ch == '/' || ch == '+' || ch == '-') // checking for operator
        {
            a = st1.top(); // getting the last element of the stack
            st1.pop();

            b = st1.top(); // getting the second last element of the stack
            st1.pop();

            if (ch == '*')  // doing operation according to the operator
            {
                item = b * a;
            }
            else if (ch == '/')
            {
                item = b / a;
            }
            else if (ch == '+')
            {
                item = b + a;
            }
            else
            {
                item = b - a;
            }

            st1.push(item); // pushing the new value after the operation
        }
        else if (ch != ',') // inserting the digits of an operand to a temporary array
        {
            temp[j++] = ch;
        }
        else // after inserting all the digits of an operand , I converted it to an integer
        {
            if (j != 0)
            {
                char temp1[j];
                for (int k = 0; k < j; k++)
                {
                    temp1[k] = temp[k]; // inserting the elements of the temporary array to another array for integer conversion
                }
                item = atoi(temp1); // converting the temporary array to integer format
                st1.push(item);
            }
            j = 0;
        }

        k++;
    }

    cout << "\nThe result is: " << st1.top() << endl << endl;
}