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

void Push_op(char stack[], int* top, char ch)
{
    *top += 1;
    stack[*top] = ch;
}
char Pop_op(char stack[], int* top)
{
    char ch;
    ch = stack[*top];
    *top -= 1;

    return ch;
}
void push_op(int Stack[], int* top, int item)  // for puhing any element in the stack
{
    *top += 1;
    Stack[*top] = item;

    return;
}
int pop_op(int Stack[], int* top) // for popping top element from the stack
{
    int a;
    a = Stack[*top];
    *top -= 1;

    return a; // returning the top element of the stack
}
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()
{
    char stack[500], q[500], p[500];
    int i, j, top = 0, p_idx = 0;

    Push_op(stack, &top, '(');
    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 == '(')
        {
            Push_op(stack, &top, ch);
        }
        else if (Operator(ch) == 1)
        {
            char temp;
            temp = Pop_op(stack, &top);
            while (Operator(temp) == 1 && operator_val(temp) >= operator_val(ch) && top > 0)
            {
                p[p_idx++] = temp;
                temp = Pop_op(stack, &top);
            }
            Push_op(stack, &top, temp);
            Push_op(stack, &top, ch);
        }
        else if (ch == ')')
        {
            char temp;
            temp = Pop_op(stack, &top);
            while (temp != '(')
            {
                p[p_idx++] = temp;
                temp = Pop_op(stack, &top);
            }
        }
    }
    // printf ("The postfix expression is: ");
    // for (i = 0; i < p_idx; i++)
    // {
    //     printf("%c", p[i]);
    // }

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

    // printf("Enter the arithmetic expression (postfix) : ");
    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 = pop_op(Stack, &top); // popping the last element of the stack
            b = pop_op(Stack, &top); // popping the second last element of the stack

            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;
            }

            push_op(Stack, &top, 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
                push_op(Stack, &top, item); // pushing the integer value to the stack
            }
            j = 0;
        }

        k++;
    }

    int value = Stack[top];

    printf("\nThe result is : %d\n\n", value);// << value << endl << endl; // printing the result of the arithmetic expression
}