Conversion of Infix to Post fix Expression using stack
Example:
Infix : a + b * c - d
Complete Program Infix to Post fix Conversion:
#include <stdio.h>
#include <conio.h>
#define size 50
char stack[size];
int TOS=-1;
//USED FUNCTION
//push();
//pop();
//isoperand();
//isempty();
//stacktop();
//prec();
//FUNCTION FOR INSERT ELEMENT INTO STACK
void PUSH (char x)
{
if(TOS == size-1)
{
printf("Stack Overflow");
}
else
{
TOS++;
stack[TOS]=x;
//printf("stack:%c\n",stack[TOS]);
}
//return(TOS);
}
//FUNCTION FOR DELETING ELEMENT FROM STACK
int POP( )
{
int x;
if(TOS==-1)
{
printf("Stack under flow");
}
else
{
x=stack[TOS];
TOS--;
//printf("POP element is %d\n",x);
}
return(x);
}
//FUNCTION TO CHECK STACK IS EMPTY OR NOT
int ISEMPTY ( )
{
if (TOS==-1)
{
return(1);
}
else
{
return(0);
}
}
//FUNCTION TO RETURN TOP OF STACK
char STACKTOP( )
{
//printf("%c",stack[TOS]);
return(stack[TOS]);
}
//FUNCTION FOR FIND SYMBOL IS OPERAND OR OPERATOR
int ISOPERAND(char O)
{
if(O=='+'||O=='-'||O=='*'||O=='/'||O=='%'||O=='^'||O=='('||O==')')
{
return(0);
}
else
{
return(1);
}
}
//FUNCTION FOR FIND PRECEDENCE
int PREC(char O1,char O2)
{
int p1,p2;
if(O1=='('||O2=='(')
{
return(0);
}
if(O2==')')
{
return(1);
}
if(O1=='+'||O1=='-')
{
p1=1;
}
if(O1=='*'||O1=='/',O1=='%')
{
p1=2;
}
if(O1=='^')
{
p1=3;
}
if(O2=='+'||O2=='-')
{
p2=1;
}
if(O2=='*'||O2=='/',O2=='%')
{
p2=2;
}
if(O2=='^')
{
p2=3;
}
if(p1>=p2)
{
return(1);
}
else
{
return(0);
}
}
void main( )
{
char infix[50],postfix[50],symbol;
//"(a+b)*(c+d)"
printf("Enter infix expression:");
scanf("%s",infix);
//printf("Infix:%s",infix);
int i,j;
i=0;
j=0;
while (infix[i]!='\0')
{
symbol=infix[i];
//printf("Symbol:%c\n",symbol);
if(ISOPERAND(symbol)==1)
{
postfix[j]=symbol;
j++;
//printf("%s is Operand\n",postfix);
}
else
{
while(ISEMPTY()!=1 && PREC(STACKTOP(),symbol)==1)
{
postfix[j]=POP();
//printf("%s:is Operator\n",postfix);
j++;
}
if(symbol!=')')
{
PUSH(symbol);
}
else
{
POP();
}
}
i++;
}
while(ISEMPTY()!=1)
{
postfix[j]=POP();
j++;
//printf("Postfix=%s",postfix[j]);
}
postfix[j]='\0';
printf("Postfix:%s\n",postfix);
getch();
}
Out Put:
No comments:
Post a Comment