Here in this program the user will enter an infix expression , the infix will be displayed in postfix notation and the evaluated value of the postfix notation will be displayed.
# include< stdio.h>
# include< stdlib.h>
struct link
{
char ch;
struct link *next;
};
/*This structure is defined to store the operators of the infix notation.The operands of the infix notation will be displayed and the operators of the expression will be displayed according to precedence. functions push() , pop() , pop1() and pop2() are related with this staructure type stack */
struct link *dd1=NULL,*dd2;
/*these two external pointers will be used to store the postfix version of the expression in a stack.*/
struct list
{
int num;
char ch;
struct list *next;
};
/*This structure will be used to store the operands of the converted postfix notation*/
struct list *last=NULL;
struct link * pop2(struct link *rec)
{
char ch='a';
struct link *temp;
char x;
while((ch!='(')&&(rec!=NULL))
{
x=rec->ch;
if(x!='(')
{
dd2=(struct link *)malloc(sizeof(struct link));
dd2->ch=x;
dd2->next=dd1;
dd1=dd2;
/*operator stored in the stack for postfix evaluation*/
printf("%c",x);
/* operator is displayed for the postfix version*/
}
temp=rec->next;
free(rec);
/*stack which contains the operators for postfix version shrinks as the operator is displayed.*/
rec=temp;
}
return rec;
}
struct link * pop(struct link *rec)
{
if(rec != NULL)
{
struct link *temp;
char x;
x=rec->ch;
if(x!='(')
{
dd2=(struct link *)malloc(sizeof(struct link));
dd2->ch=x;
dd2->next=dd1;
dd1=dd2;
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=='%')))
{
/*if the current operator has more precedence over the top item of the stack then no action should be taken , they should be kept in the stack as it is.Otherwise the last inserted item ( here operator) should be displayed ( from the else part).*/
}
else
{
if(x!='(')
{
dd2=(struct link *)malloc(sizeof(struct link));
dd2->ch=x;
dd2->next=dd1;
dd1=dd2;
/*the operator is stored in the stack no 2 (for postfix evaluation)*/
printf("%c",x);
}
temp=rec->next;
free(rec);
rec=temp;
/* if the top item of the stack is displayed , the stack should shrink.*/
}
return rec;
}
struct link *push(char c,struct link *rec)
{
if(c==')')
{
//if clossing bracket is found , there must be a openning bracket with operator
rec=pop2(rec);
}
if((rec!=NULL)&&(c!='('))
{
/*if the stack contains an operator and another operator is encountered, the operator which is of more precedence should be displayed.*/
rec=pop1(c,rec);
}
if(c!=')')
{
// from this block the current encountered operator is stored in the stack
struct link *new1;
new1 = (struct link *)malloc(sizeof(struct link));
new1->ch=c;
new1->next = rec;
rec = new1;
}
return rec;
}
struct list *push1(int i,struct list *node)
{
struct list *new1;
new1=(struct list *)malloc(sizeof(struct list));
new1->num=i;
new1->next=node;
node=new1;
return node;
}
struct list *pop3(struct list *node)
{
struct list *p;
p=node->next;
free(node);
node=p;
return node;
}
void dis(struct link *node)
{
int x,y,result;
struct list *ds,*sta=NULL;
while(node)
{
ds=(struct list *)malloc(sizeof(struct list));
ds->ch=node->ch;
node=node->next;
ds->next=last;
last=ds;
}
/* elements of the second stack are stored in another stack in reversed order whose top element is pointed by external pointer last.Now each element of the stack will be checked , if operand is found then it will be pushed in another stack , in case of operator the top two operands will be poped from the stack and operation will be performed according to the operator and the result will be pushed back again in the stack.*/
while(last)
{
char c=last->ch;
if(isdigit(c)!=0)
sta=push1(c-48,sta);
else
{
y=sta->num;
sta=pop3(sta);
x=sta->num;
sta=pop3(sta);
switch(c)
{
/*from here the result is calculated as per the operator and the result is pushed back into the stack*/
case '+':
{
result=(x+y);
sta=push1(result,sta);
break;
}
case '-':
{
result=(x-y);
sta=push1(result,sta);
break;
}
case '*':
{
result=(x*y);
sta=push1(result,sta);
break;
}
case '/':
{
result=(x/y);
sta=push1(result,sta);
break;
}
}
}
last=last->next;
/* pointer last which is traversing the stack containg the postfix version in reversed order moves to the next node.*/
}
/* when all the operations are performed , the final stack contains only one item , the result.*/
printf("\n*****\nResult of the expression is::%d",sta->num);
}
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==')'))
{
/* when operators are encountered ,push method is called with the character and structure pointer as argument. current stack will be returned. */
start=push(ch,start);
i++;
}
else
{
/* this block will be executed is the character read from the input is not an operator*/
if(ch!='\n')
{
printf("%c",ch);
/*operand in postfix version is displayed.*/
dd2=(struct link *)malloc(sizeof(struct link));
dd2->ch=ch;
dd2->next=dd1;
dd1=dd2;
/* the operands are stored in stack no.2 (for postfix evaluation)*/
}
}
}
while(i>0)
{
/* i counts the number of operators in the infix expression, although at present all the operators may not be present in the stack but we should call the pop method to display the remaining operators in the stack( which are not displayed through pop1() or pop2() */
start=pop(start);
/* every call to this function will display the top element of the stack and then the stack will be shrinked and returned so , before i becomes 0 start may point to NULL*/
i--;
}
dis(dd1);
/*dis () function of the second structure is called to reverse the elements of the second stack where all the operators and operands are stored in postfix notation */
getch();
}