CONVERSION OF
INFIX EXPRESSION TO POSTFIX
Aim
To write a C-program to convert the
given infix expression to its postfix format.
Algorithm
STEP 1: Start
STEP 2: Initialize the stack.
STEP 3: While (INSTR!= NULL)
STEP 4: CH= get the character from
INSTR.
STEP 5: If( CH= = operand) then
append CH int POSTSTR
else if(CH = = ‘(‘) then
push CH into stack
else if(CH = =’)’) then
pop the data from the stack and
append the data into POSTSTR until we get
‘(‘ from the stack
else
while(precedence (TOP) >=
precedence (CH))
pop the data from stack and
append the data into POSTSTR.
[End of while structure]
[End of if structure]
STEP 6: Push CH into the stack.
STEP 7: [End of second while structure]
STEP 8: pop all the data from stack and
append data into POSTSTR.
STEP 9: Stop
Coding:
#include<stdio.h>
#include<conio.h>
int stack[20],top=0;
char inf[40],post[40];
void push(int);
void postfix();
char pop();
void main(void)
{
clrscr();
printf("\t\t\t****INFIX TO
POSTFIX****\n\n");
printf("Enter the infix expression
:: ");
scanf("%s",inf);
postfix();
getch();
}
void postfix()
{
int
i,j=0;
for(i=0;inf[i]!=NULL;i++)
{
switch(inf[i])
{
case
'+':
while(stack[top]>=1)
post[j++]=pop();
push(1);
break;
case
'-':
while(stack[top]>=1)
post[j++]=pop();
push(2);
break;
case
'*':
while(stack[top]>=3)
post[j++]=pop();
push(3);
break;
case
'/':
while(stack[top]>=3)
post[j++]=pop();
push(4);
break;
case
'^':
while(stack[top]>=4)
post[j++]=pop();
push(5);
break;
case
'(':
push(0);
break;
case
')':
while(stack[top]!=0)
post[j++]=pop();
top--;
break;
default:
post[j++]=inf[i];
}
}
while(top>0)
post[j++]=pop();
printf("\nPostfix
Expression is :: %s",post);
}
void push(int ele)
{
top++;
stack[top]=ele;
}
char pop()
{
char
e;
e=stack[top];
top--;
switch(e)
{
case
1:
e='+';
break;
case
2:
e='-';
break;
case
3:
e='*';
break;
case
4:
e='/';
break;
case
5:
e='^';
break;
}
return(e);
}
Output:
Enter the infix expression ::
(a+b)/(c*d)
Postfix Expression is :: ab+cd*/
Manual
Calculation
|
SE EXPRESSION
|
STACK
|
RESULT FIELD
|
|
(
|
(
|
|
|
A
|
|
A
|
|
+
|
+,(
|
A
|
|
B
|
+,(
|
AB
|
|
)
|
),(
|
|
|
/
|
/
|
|
|
(
|
(,/
|
|
|
C
|
(,/
|
AB+C
|
|
-
|
-,(,/
|
AB+C
|
|
D
|
-,(,/
|
AB+CD
|
|
+
|
+,(,/
|
AB+CD-
|
|
E
|
+,(,/
|
AB+CD-E
|
|
)
|
),+,(,/
|
AB+CD-E+
|
|
+
|
+,/
|
AB+CD-E+/
|
|
F
|
+
|
AB+CD-E/F
|
|
-
|
-
|
AB+CD-E/F+
|
|
G
|
-
|
AB+CD-E/F+G
|
|
|
|
AB+CD-E/F+G-
|
No comments:
Post a Comment