#include<stdio.h>
#include<conio.h>
#define SIZE 50
char stack[SIZE];
int top=-1;
void main()
{
char ch,x;
//infix expression and postfix expression(output expression)
char *ifxexpr,pfxexpr[50];
//functions to calculate in-stack priority and in-coming priority
int ISP(char);
int ICP(char);
void push(char);
char pop();
int i,size=0;
clrscr();
printf("\nEnter Valid Infix Expression : ");
gets(ifxexpr);
//push '(' to the stack
push('(');
//Append ')' to mark end of the expression
strcat(ifxexpr,")");
i=0;
while(top>-1)
{
x=pop();
ch=ifxexpr[i];
if(isalpha(ch)) //check if the character is operand
{
//append to the output postfix expression
pfxexpr[size]=ch;
pfxexpr[size+1]='\0';
size++;
push(x);
}
else if(ch==')')
{
//pop the items and add it to output untill '(' appears
while(x!='(')
{
pfxexpr[size]=x;
pfxexpr[size+1]='\0';
size++;
x=pop();
}
}
else if(ISP(x)>=ICP(ch))
{
//pop the items and add it to the output untill we get lower priority symbol in stack
while(ISP(x)>ICP(ch))
{
pfxexpr[size]=x;
pfxexpr[size+1]='\0';
size++;
x=pop();
}
push(x);
push(ch);
}
else if(ISP(x)<ICP(ch))
{
push(x);
push(ch);
}
else
{
printf("\nInvalid Expression");
exit(0);
}
i++;
}
printf("\nPostfix Expression : ");
puts(pfxexpr);
getch();
}
void push(char item)
{
if(top>=SIZE)
{
printf("\nStack is Full");
getch();
}
else
{
top++;
stack[top]=item;
}
}
char pop()
{
char item;
if(top<0)
{
item='\0';
}
else
{
item=stack[top];
top--;
}
return(item);
}
int ISP(char ch)
{
int p;
switch(ch)
{
case '+':
case '-':
p=2;
break;
case '*':
case '/':
p=4;
break;
case '^':
p=5;
break;
case '(':
p=0;
break;
}
return(p);
}
int ICP(char ch)
{
int p;
switch(ch)
{
case '+':
case '-':
p=1;
break;
case '*':
case '/':
p=3;
break;
case '^':
p=6;
break;
case '(':
p=9;
break;
case ')':
p=0;
break;
}
return(p);
}
