#include <stdio.h>
#include <ctype.h>
#include <math.h>

#define MAX 100

/* ---------- POSTFIX QUEUE ---------- */
char queue[MAX];
int front = 0, rear = -1;

void enqueue(char x) {
    queue[++rear] = x;
}

/* ---------- OPERATOR STACK ---------- */
char opStack[MAX];
int tos = -1;

void stack_push(char x) {
    opStack[++tos] = x;
}

char stack_pop() {
    return opStack[tos--];
}

char stack_peek() {
    return opStack[tos];
}

/* ---------- OPERAND STACK ---------- */
int valStack[MAX];
int top = -1;

void val_push(int x) {
    valStack[++top] = x;
}

int val_pop() {
    return valStack[top--];
}

/* ---------- PRECEDENCE ---------- */
int precedence(char op) {
    if (op == '^') return 3;
    if (op == '*' || op == '/') return 2;
    if (op == '+' || op == '-') return 1;
    return 0;
}

/* ---------- INFIX TO POSTFIX ---------- */
void infixToPostfix(char infix[]) {
    int i = 0, len = 0;
    char ch;

    stack_push('(');

    while (infix[len] != '\0')
        len++;
    infix[len] = ')';
    infix[len + 1] = '\0';

    while ((ch = infix[i++]) != '\0') {

        if (isalnum(ch)) {
            enqueue(ch);
        }
        else if (ch == '(') {
            stack_push(ch);
        }
        else if (ch == ')') {
            while (stack_peek() != '(') {
                enqueue(stack_pop());
            }
            stack_pop();   // discard '('
        }
        else {
            while (precedence(ch) <= precedence(stack_peek())) {
                enqueue(stack_pop());
            }
            stack_push(ch);
        }
    }
}

/* ---------- POSTFIX EVALUATION ---------- */
int evaluatePostfix() {
    for (int i = 0; i <= rear; i++) {
        char ch = queue[i];

        if (isalnum(ch)) {
            int value;
            printf("Enter value for %c: ", ch);
            scanf("%d", &value);
            val_push(value);
        }
        else {
            int b = val_pop();
            int a = val_pop();

            switch (ch) {
                case '+': val_push(a + b); break;
                case '-': val_push(a - b); break;
                case '*': val_push(a * b); break;
                case '/': val_push(a / b); break;
                case '^': val_push(pow(a, b)); break;
            }
        }
    }
    return val_pop();
}

/* ---------- MAIN ---------- */
int main() {
    char infix[MAX];

    printf("Enter infix expression: ");
    scanf("%s", infix);

    infixToPostfix(infix);

    printf("Postfix expression: ");
    for (int i = 0; i <= rear; i++)
        printf("%c", queue[i]);
    printf("\n");

    int result = evaluatePostfix();
    printf("Final result: %d\n", result);

    return 0;
}