#include <ctype.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
typedef struct {
  char key;
} element;
element stack[100];
int top = -1;
bool isfull() {
  if (top == 99) {
    return true;
  }
  return false;
}
bool isempty() {
  if (top < 0) {
    return true;
  }
  return false;
}

void push(char key) {
  if (isfull()) {
    printf("stack overflow \n");
    return;
  }
  stack[++top].key = key;
}

char pop() {
  if (isempty()) {
    printf("staxk is empyyt");
    return '\0';
  }
  return stack[top--].key;
}

int precedence(char op) {
  switch (op) {
  case '^':
    return 3;
  case '*':
  case '/':
    return 2;
  case '+':
  case '-':
    return 1;
  default:
    return 0;
  }
}
bool isRight(char op) {
  if (op == '^') {
    return true;
  }
  return false;
}
char peek() {
  if (isempty()) {
    printf("stack is empty");
  }
  return stack[top].key;
}

int main() {
  char infix[100];
  char postfix[100];
  printf("enter infix\n");
  scanf("%s", infix);

  int k = 0;
  int i = 0;

  while (infix[i] != '\0') {
    char current = infix[i];

    if (isalpha(current)) {
      postfix[k++] = current;
    } else if (current == '(') {
      push(current);
    } else if (current == ')') {
      while (!isempty() && peek() != '(') {
        postfix[k++] = pop();
      }
      if (!isempty() && peek() == '(') {
        pop(); // Remove '(' from stack
      }
    } else { // Operator
      int currPrec = precedence(current);
      while (!isempty() && peek() != '(') {
        char topOp = peek();
        int topPrec = precedence(topOp);

        if (topPrec > currPrec || (topPrec == currPrec && !isRight(current))) {
          postfix[k++] = pop();
        } else {
          break;
        }
      }
      push(current);
    }
    i++;
  }

  while (!isempty()) {
    postfix[k++] = pop();
  }

  postfix[k] = '\0';
  printf("Postfix: %s\n", postfix);

  return 0;
}