/* Program to convert partially (or fully) parenthesized infix expression
to postfix (reverse Polish) format */

#include <stdio.h>
#include <conio.h>
#define MAX 40

struct Stack
{
  int top;
  char ele[MAX];
};

typedef struct Stack lifo;

void Push(lifo *t, char ch)
{
  if (t -> top == MAX)
    printf("\nERR: Stack overflow.");
  else
    t -> ele[++t -> top] = ch;
}

char Pop(lifo *t)
{
  if (t -> top == -1)
    printf("\nERR: Stack underflow.");
  else
    return (t -> ele[t -> top--]);
}

char Peep(lifo *t)  /* returns top element from stack without removing it */
{
  return (t -> ele[t -> top]);
}

int Precedence(char ch)
{
if ((ch == '+') || (ch == '-'))
  return 1;
else if ((ch == '*') || (ch == '/'))
  return 3;
else if (ch == '$')
  return 6;
else if ((ch >= 97) && (ch <= 122))
  return 7;
else if (ch == '(')
  return 9;
else
  return 0;
}

int StackPrecedence(char ch)
{
if ((ch == '+') || (ch == '-'))
  return 2;
else if ((ch == '*') || (ch == '/'))
  return 4;
else if (ch == '$')
  return 5;
else if ((ch >= 97) && (ch <= 122))
  return 8;
else
  return 0; /* stack precedence of '(' */
}

int Rank(char ch)
{
if ((ch == '+') || (ch == '-') || (ch == '*') || (ch == '/') || (ch == '$'))
  return -1;
else if ((ch >= 97) && (ch <= 122))
  return 1;
}

char NextChar(char *infix)
{
  static int indx = 0;
  return *(infix + indx++);
}

int IsValidParen(char *infix)
{
static int arr[2];

while (*infix)
{
	if (*infix == '(')
	{
		arr[0]++;
		infix++;
	}
	else if (*infix == ')')
	{
		arr[1]++;
		infix++;
	}
	else
		infix++;
}
if (arr[0] == arr[1])
	return 1;	/* Valid parenthesized infix */
else
	return 0;	/* Invalid parenthesized infix */
}

main()
{
char infix[MAX], polish[MAX];
char tempin[MAX];
char next, temp;
int rank, indx = 0;
lifo *stack;
int i;

clrscr();

stack -> top = -1;  /* stack initialized */
printf("Enter the un-parenthesized infix expression : ");
scanf("%s", infix);

strcpy(tempin, infix);
if (IsValidParen(infix) == 0)
{
    printf("\nInvalid parenthesized infix.");
    printf("\n\nPress any key to exit...");
    getch();
    exit(-1);
}
strcpy(infix, tempin);
strcat(infix, ")");

Push(stack, '(');
rank = 0;
next = NextChar(infix);

while (next)
{
  if (stack -> top < 0)
  {
    printf("\nInvalid infix.");
    printf("\n\nPress any key to exit...");
    getch();
    exit(-1);
  }
  while (Precedence(next) < StackPrecedence(Peep(stack)))
  {
    temp = Pop(stack);
    polish[indx++] = temp;
    rank = rank + Rank(temp);
    if (rank < 1)
    {
      printf("\nInvalid infix.");
      printf("\n\nPress any key to exit...");
      getch();
      exit(-1);
    }
  }
  if (Precedence(next) != StackPrecedence(Peep(stack)))
	Push(stack, next);
  else
	Pop(stack);
  next = NextChar(infix);
}

if ((stack -> top != -1) || (rank != 1))
{
    printf("\nInvalid infix.");
    printf("\n\nPress any key to exit...");
    getch();
    exit(-1);
}

if (rank == 1)
{
  printf("\nValid infix.");
  printf("\nReverse Polish (suffix) equivalent is : ");
  for (i = 0; i < indx; i++)
	printf("%c", polish[i]);
}
else
  printf("\nInvalid infix.");

printf("\n\nProgram over. Press any key to exit...");
getch();
}