/*
 * single digit operant infix to postfix expressions
 * adapted and modified from textbook example
 * HBF
*/
#include <stdio.h>
#include <string.h>

#define MAX 100

void InfixtoPostfix(char source[], char target[]);
int getPriority(char c);
int isOperator(char c);

void push(char stk[], int *top, int val);
void pop(char stk[], int *top);
char peek(char stk[], int top);

int main() {
  char infix[100]="9-((3*4)+8)/4";
  //char infix[100]="9-4+4";
  char postfix[100];
  printf("\nThe given infix expression is: ");
  puts(infix);
  InfixtoPostfix(infix, postfix);
  printf("\nThe postfix expression is: ");
  puts(postfix);
   
  return 0;
}

void InfixtoPostfix(char source[], char target[]) {
  char stk[MAX];
  int top = -1;
  
  char *p = source;
  char *dp = target;
  *dp = '\0';
    
  while (*p) {
    if (*p == '(') {
      push(stk, &top, *p);
    }
    //else if (*p >= '0' && *p <= '9') {
	else if (isdigit(*p) || isalpha(*p)) {
      *dp++ = *p;
    }
    else if (*p == ')') {
      while ((top != -1) && (peek(stk, top) != '(')) { 
        *dp++ = peek(stk, top);
        pop(stk, &top);
      }
    
      if (top == -1) {
        printf("\nINVALID EXPRESSION");
        return;
      }
      pop(stk, &top);
     
    } 
    else if (isOperator(*p)) {
      while ((top != -1) && (isOperator(stk[top])) && (getPriority(stk[top]) >= getPriority(*p))) {
        *dp++ = peek(stk, top);
        pop(stk, &top);
      }
      push(stk, &top, *p);
    } 
    else {
      printf("\nINCORRECT ELEMENT IN EXPRESSION");
      return;
    }
    p++;
  }
  
  while (top != -1) { 	  
    *dp++ = peek(stk, top);
    pop(stk, &top);
  }
  *dp = '\0';
}

int getPriority(char op) {
  if (op == '/' || op == '*' || op == '%')
    return 1;
  else if (op == '+' || op == '-')
    return 0;
}

int isOperator(char op) {
  if (op == '/' || op == '*' || op == '%' || op == '+' || op == '-')
    return 1;
  else
    return 0;
}

void push(char stk[], int *top, int val) {
  if (*top == MAX-1) {
    printf("\n STACK OVERFLOW");
  } else {
    *top = *top + 1;
    stk[*top] = val;
  }
}

void pop(char stk[], int *top) {
  if (*top == -1) {
    printf("\n STACK UNDERFLOW");
  } else {
    *top = *top - 1;
  }
}

char peek(char stk[], int top) {
  if (top == -1) {
    printf("\n STACK IS EMPTY");
    return -1;
  } else
    return (stk[top]);
}


/*
The given infix expression is: 9-((3*4)+8)/4
The corresponding postfix expression is: 934*8+4/-
*/