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

#define STACK_OVERFLOW  -100
#define STACK_UNDERFLOW -101
#define OUT_OF_MEMORY   -102
#define alph "qwertyuiopasdfghjklzxcvbnm"
#define s1 "+*^"
#define s2 "-/^"



struct Stack {
    char element;
    struct Stack *next;
};

void push(struct Stack **head, char element) {
    struct Stack *tmp = malloc(sizeof(struct Stack));
    if (tmp == NULL) {
        exit(STACK_OVERFLOW);
    }
    (*tmp).next = *head;
    (*tmp).element = element;
    *head = tmp;
}

char pop(struct Stack **head) {
    struct Stack *out;
    char element;
    if (*head == NULL) {
        exit(STACK_UNDERFLOW);
    }
    out = *head;
    *head = (**head).next;
    element = (*out).element;
    free(out);
    return element;
}

int findins(char elem) {
    int pos = -1;
    for (int i = 0; i < 3; i++) {
        if (elem == s1[i]) {
            pos = i;
            break;
        }
    }
    if (pos == -1) {
        for (int i = 0; i < 3; i++) {
            if (elem == s2[i]) {
                pos = i;
                break;
            }
        }
    }
    return pos;
}

void Check(char elem, struct Stack **stack){
    bool letter = false;
    for (int i = 0; i < 26; i++) {
        if (elem == alph[i]) {
            letter = true;
            break;
        }
    }
    char tmp;
    if (letter) {
        printf("%c", elem);
    }
    else {
        if (*stack == NULL) {
            push(stack, elem);
        } else {
            switch (elem) {
                case '_':
                    tmp = pop(stack);
                    while (*stack != NULL) {
                        printf("%c", tmp);
                        tmp = pop(stack);
                    }
                    break;
                case '(':
                    push(stack, elem);
                    break;
                case ')':
                    tmp = pop(stack);
                    while (tmp != '(') {
                        printf("%c", tmp);
                        tmp = pop(stack);
                    }
                    break;
                default:
                    tmp = pop(stack);
                    if (tmp == '(') {
                        push(stack, tmp);
                        push(stack, elem);
                    } else {
                        if ( (findins(elem) > findins(tmp)) || ((elem == '^') && (tmp == '^')) ) {
                            push(stack, tmp);
                            push(stack, elem);
                        } else {
                            printf("%c", tmp);
                            tmp = pop(stack);
                            while ((findins(elem) <= findins(tmp)) && (tmp != '(') && (tmp != '_')) {
                                printf("%c", tmp);
                                tmp = pop(stack);
                            }
                            push(stack, tmp);
                            push(stack, elem);
                        }
                    }
                    break;
            }
        }
    }
}

int main() {
    char s[] = "w*(a+b+c*(y-g*d)^n^k+s*l)/(x-f*t*p+w)^e_";
    struct Stack *stack = NULL;
    push(&stack, '_');
    for (int i = 0; i < strlen(s); i++) {
        Check(s[i], &stack);
    }
    return 0;
}