Consider the expression for sum of A and B- normally we represents
it with the expression A+B. A and B are two operands and ‘+’ is the operator.
This particular representation is called infix. There are two alternate
notations for expressing the sum of A and B :-
AB+ called postfix notation
+AB called prefix notation.
We will deal with infix and postfix notations.
Conversion from infix to postfix
notation
Let us consider some additional examples, A + B * C is an
mathematical expression and it is written using infix notation. Now we will see
how we can convert it to postfix notation.
In a left to right scan of the expression, the first item
encountered is A which may be directly displayed. Next the operator + is
encountered and it should be pushed into a stack of operators. Next the operand B is
encountered and is displayed. Next comes the second operator * and it is pushed
in the stack. Last item of the expression is displayed. So upto this point we
will get the out as :- ABC. Now start popping the items of the stack and display them .So the final output
will be ABC*+.
# include< stdio.h >
# include< malloc.h >
int b=0;
struct link
{
char ch;
struct link *next;
};
struct link *push(char c,struct link *rec)
{
struct link *new1;
new1 = (struct link *)malloc(sizeof(struct link));
new1->ch=c;
new1->next = rec;
rec = new1;
return rec;
}
struct link * pop(struct link *rec)
{
if(rec != NULL)
{
struct link *temp;
char x;
x=rec->ch;
printf("%c",x);
temp=rec->next;
free(rec);
rec=temp;
}
return rec;
}
void main()
{
struct link *start ;
int i=0;
char ch='a';
clrscr();
start = NULL;
printf("\nEnter the expression:-");
while(ch!='\n')
{
ch=getchar();
if((ch=='+')||(ch=='-')||(ch=='*')||(ch=='/'))
{
start=push(ch,start);
i++;
}
else
{
if(ch!='\n')
printf("%c",ch);
}
}
while(i>0)
{
start=pop(start);
i--;
}
getch();
}
The above program is suitable for expressions like 7+2*3 , where
the operators are of same precedence or precedences increase(s) from left to
right. For the above expression , postfix notation will be 723*+.Evaluation of
this postfix expression will be –
723*+
72*3+
76+
7+6
13
But what would happen if the expression is 7*2*3-2 ? The postfix
notation of this expression would be 72*3*2-. If the postfix notation were
7232-** (which will be obtained if the conversion is done through the above
program ) then the result would be 14 instead of 40.When operators other than
the first operator is found in a expression it should be compared with the
previous operator of the stack. If the operator in the stack is found of
greater precedence over the current operator then the operator should be
displayed.
Some examples of infix and postfix expressions are given below:-
Infix A+B-C Postfix AB+C-
Infix A+B*C postfix ABC*+
Infix (A+B)C postfix AB+C*
Infix (A+B)*(C-D) postfix AB+ CD-*
Follow my next post for the solution of these type of expression.
Conversion of infix to postfix expression
# include< stdio.h>
# include< stdlib.h>
struct link
{
char ch;
struct link *next;
};
struct link * pop2(struct link *rec)
{
char ch='a';
struct link *temp;
char x;
while((ch!='(')&&(rec!=NULL))
{
x=rec->ch;
if(x!='(')
printf("%c",x);
temp=rec->next;
free(rec);
rec=temp;
}
return rec;
}
struct link * pop(struct link *rec)
{
if(rec != NULL)
{
struct link *temp;
char x;
x=rec->ch;
if(x!='(')
printf("%c",x);
temp=rec->next;
free(rec);
rec=temp;
}
return rec;
}
struct link * pop1(char z,struct link *rec)
{
struct link *temp;
char x;
x=rec->ch;
if(((x=='+')||(x=='-'))&&((z=='*')||(z=='/')||(z=='%')))
{
}
else
{
if(x!='(')
printf("%c",x);
temp=rec->next;
free(rec);
rec=temp;
}
return rec;
}
struct link *push(char c,struct link *rec)
{
if(c==')')
{
rec=pop2(rec);
}
if((rec!=NULL)&&(c!='('))
{
rec=pop1(c,rec);
}
if(c!=')')
{
struct link *new1;
new1 = (struct link *)malloc(sizeof(struct link));
new1->ch=c;
new1->next = rec;
rec = new1;
}
return rec;
}
void main()
{
struct link *start ;
int i=0;
char ch='a';
clrscr();
start = NULL;
printf("\nEnter the expression:-");
while(ch!='\n')
{
ch=getchar();
if((ch=='+')||(ch=='-')||(ch=='*')||(ch=='/')||(ch=='(')||(ch=='%')||(ch==')'))
{
start=push(ch,start);
i++;
}
else
{
if(ch!='\n')
printf("%c",ch);
}
}
while(i>0)
{
start=pop(start);
i--;
}
getch();
}
No comments:
Post a Comment