Infix to postfix Conversion
ALGORITHM
ALGORITHM
1. Scan the
Infix expression left to right
2. If the
character x is an operand
1. Output
the character into the Postfix Expression array
3.
If the character x is a left or right
parenthesis
1. If the
character is “(“
1. Push it
into the stack
2. if the
character is “)”
2. Repeatedly
pop and output all the operators/characters until “(“ is popped from the stack.
4.
If the character x is a is a regular operator
1: Check
the character y currently at the top of the stack.
2: If Stack is empty or y=‘(‘ or y is an operator
of lower precedence than x, then push x into stack.
5: If y is
an operator of higher or equal precedence than x, then pop and output y into
postfix array repeat step 3 until priority of y is lower to x
then push x into the stack.
6. When all
characters in infix expression are processed repeatedly pop the character(s)
from the stack and output them until the stack is empty.
PROGRAM
#include
#include
#include
char arr[100];
int top;
void push(char c)
{
top++;
arr[top]=c;
}
char pop()
{
if(top==-1)
{
return -1;
}
else
{
char c;
c=arr[top];
top--;
return c;
}
}
int prec(char c)
{
if(c=='+'||c=='-')
{
return 1;
}
else if(c=='*'||c=='/')
{
return 2;
}
else
{
return -1;
}
}
int main()
{
top=-1;
char postfix[100],infix[100];
char c;
int i;
int k=0;
printf("Enter the infix
expression:");
scanf("%s",infix);
for(i=0;i
{
switch(infix[i])
{
case '(':
push(infix[i]);
break;
case')':
while((c=pop())!='(')
{
postfix[k++]=c;
}
break;
case'+':
case'-':
case'*':
case'/':
if(top==-1)
{
push(infix[i]);
}
else
{
while(prec(arr[top])>=prec(infix[i]))
{
postfix[k++]=pop();
}
push(infix[i]);
}
break;
default:postfix[k++]=infix[i];
break;
}
}
while(top!=-1)
{
postfix[k++]=pop();
}
postfix[k]='\0';
printf(" The corresponding postfix expression is: ");
printf("%s",postfix);
getch();
}
Posts
0 comments:
Post a Comment