#include <stdio.h>
#include <string.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 2;
else if (ch == '$')
  return 3;
else if ((ch >= 97) && (ch <= 122))
  return 4;
else
  return 0;
}

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++);
}

main()
{
char infix[MAX], polish[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(infix, strrev(infix));

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

while (next)
{
  while (Precedence(next) < Precedence(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);
    }
  }
  Push(stack, next);
  next = NextChar(infix);
}

while (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 (rank == 1)
{
  printf("\nValid infix.");
  printf("\nPolish (prefix) equivalent is : ");
  for (i = (indx - 1); i >= 0; i--)
	printf("%c", polish[i]);
}
else
  printf("\nInvalid infix.");

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