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

#define MAX 100

typedef struct {
    char *items[MAX];
    int top;
} Stack;

// Stack functions
void init(Stack *s) {
    s->top = -1;
}

int isEmpty(Stack *s) {
    return s->top == -1;
}

int isFull(Stack *s) {
    return s->top == MAX - 1;
}

void push(Stack *s, char *str) {
    if (!isFull(s)) {
        s->items[++(s->top)] = str;
    }
}

char* pop(Stack *s) {
    if (!isEmpty(s)) {
        return s->items[(s->top)--];
    }
    return NULL;
}

int isOperator(char c) {
    return c == '+' || c == '-' || c == '*' || c == '/';
}

int isOperand(char c) {
    return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
}

char* invalidInput() {
    char *inv = (char*)malloc(13);
    strcpy(inv, "Invalid input");
    return inv;
}

char* prefixToInfix(char *prefix) {
    Stack s;
    init(&s);
    int len = strlen(prefix);

    // Process from right to left
    for (int i = len - 1; i >= 0; i--) {
        char c = prefix[i];
        if (isOperand(c)) {
            // Operand, push it as string
            char *operand = (char*)malloc(2);
            operand[0] = c;
            operand[1] = '\0';
            push(&s, operand);
        } else if (isOperator(c)) {
            // Operator, pop two operands
            char *op1 = pop(&s);
            char *op2 = pop(&s);
            if (op1 == NULL || op2 == NULL) {
                // Not enough operands
                while (!isEmpty(&s)) free(pop(&s));
                if (op1) free(op1);
                if (op2) free(op2);
                return invalidInput();
            }
            // Create new string "(op1 operator op2)"
            int size = strlen(op1) + strlen(op2) + 4; // 4 for operator and parentheses and null terminator
            char *expr = (char*)malloc(size);
            snprintf(expr, size, "(%s%c%s)", op1, c, op2);
            free(op1);
            free(op2);
            push(&s, expr);
        } else {
            // Invalid character
            while (!isEmpty(&s)) free(pop(&s));
            return invalidInput();
        }
    }

    if (s.top != 0) {
        // More than one element means incomplete expression
        while (!isEmpty(&s)) free(pop(&s));
        return invalidInput();
    }

    return pop(&s);
}