#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>

#define MAX 10005

// precedence of operators
int precedence(char c) {
    if (c == '^') return 3;
    if (c == '*' || c == '/') return 2;
    if (c == '+' || c == '-') return 1;
    return -1;
}

// check if character is operator
int isOperator(char c) {
    return (c == '+' || c == '-' || c == '*' || c == '/' || c == '^');
}

// check if expression contains valid chars
int isValidChar(char c) {
    return (isalpha(c) || isOperator(c) || c == '(' || c == ')' || isspace(c));
}

// reverse a string
void reverseStr(char *str) {
    int n = strlen(str);
    for (int i = 0; i < n / 2; i++) {
        char tmp = str[i];
        str[i] = str[n - i - 1];
        str[n - i - 1] = tmp;
    }
}

// convert infix to postfix
void infixToPostfix(char *exp, char *result) {
    char stack[MAX];
    int top = -1, k = 0;

    for (int i = 0; exp[i]; i++) {
        char c = exp[i];

        if (isspace(c)) continue;

        if (isalpha(c)) {
            result[k++] = c;
        } else if (c == '(') {
            stack[++top] = c;
        } else if (c == ')') {
            while (top >= 0 && stack[top] != '(') {
                result[k++] = stack[top--];
            }
            if (top >= 0 && stack[top] == '(') top--; // pop '('
        } else if (isOperator(c)) {
            while (top >= 0 && precedence(stack[top]) >= precedence(c)) {
                if (c == '^' && stack[top] == '^') break; // right-associative
                result[k++] = stack[top