Algorithm to convert INFIX to POSTFIX
1. Add
“(”
at the beginning and “)” at the end of the expression (Q)
2. Scan
Q from the left to right and repeat step
3 to step 5 until completed
3. If
an operand is encountered , add to p
4. If
an operator is encountered , check TOS
·
If TOS contains left-parenthesis or an
operator with lower precedence, POP the operator from stack and PUSH to the
stack
·
If TOS contain an operator with same or
higher precedence , POP the operator from stack and PUSH to the stack
5. If
the right parenthesis is encountered
·
POP from stack and add to p until left parenthesis
is encountered
·
Remove left parenthesis from stack
Program to convert infix to postfix
#include<stdio.h>
#include<string.h>
#define max 5
int stack[max],top=-1;
void push(char sym)
{
if(top== max-1)
{
printf("Stack Overflow:\n");
}
else
{
top++;
stack[top]=sym;
}
}
char pop()
{
char x;
if(top==-1)
{
printf("Stack Underflow\n");
return(0);
}
else
{
x=stack[top];
top--;
return x;
}
}
int set_precedence(char ch)
{
if(ch=='^')
return (5);
else if(ch=='*'||ch=='/')
return (4);
else if(ch=='+'||ch=='-')
return (3);
}
void convert(char infix[])
{
int length;
static int index=0,pos=0;
char symbol,temp;
char postfix[50];
length=strlen(infix);
while(index<length)
{
symbol=infix[index];
switch(symbol)
{
case'(':push(symbol);
break;
case ')':temp=pop();
while(temp!='(')
{
postfix[pos]=temp;
pos++;
temp=pop();
}
break;
case'+':
case'-':
case'*':
case'/':
while(set_precedence(stack[top])>=set_precedence(symbol))
{
temp=pop();
postfix[pos]=temp;
pos++;
}
push(symbol);
break;
default:
postfix[pos++]=symbol;
break;
}
index++;
}
while(top>=0)
{
temp=pop();
postfix[pos++]=temp;
}
postfix[pos++]='\0';
printf("Post fix exp. is:\t");
puts(postfix);
return;
}
int main()
{
char str[20];
printf("\n Enter the infix
expn.:\n");
gets(str);
convert(str);
return 0;
}
No comments:
Post a Comment