/* Program to convert postfix expression to prefix without infix */
/* 71gh73n3d by 5kull_m4c1n705h */

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

enum boolean {false, true};

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

typedef struct Stack lifo;

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

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

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

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

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

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

enum boolean IsOperator(char op)
{
if ((op == '+') || (op == '-') || (op == '*') || (op == '/') || (op == '$'))
	return true;
else
	return false;
}

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

clrscr();

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

strcpy(postfix, strrev(postfix));
rank = 0;
/* a prefix or postfix expression is valid iff rank is 1 */
for (i = 0; i < strlen(postfix); i++)
	rank = rank + Rank(*(postfix + i));

if (rank != 1)
{
	printf("\nInvalid prefix expression.");
	printf("\n\nProgram over. Press any key to exit...");
	getch();
	exit(-1);
}

Push(stack, '#', 'F');	/* F = false, T = true */
next = NextChar(postfix);

while (next)
{
  if (IsOperator(next) == true)
      Push(stack, next, 'F');
  else
  {
      polish[indx++] = next;
      if (PeepFlg(stack) == 'F')
	stack -> flag[stack -> top] = 'T';
      else
      {
	while (PeepFlg(stack) == 'T')
		polish[indx++] = Pop(stack);
      }
  }
next = NextChar(postfix);
}

while (PeepEle(stack) != '#')
  polish[indx++] = Pop(stack);

printf("\nValid postfix.");
printf("\nPolish (prefix) equivalent is : ");
for (i = (indx - 1); i >= 0; i--)
	printf("%c", polish[i]);

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