Conversion from Prefix to Infix
Application of Stacks
Conversion from Prefix to Infix
The algorithm for converting a Prefix expression to an Infix notation is as follows:
- Accept a prefix string from the user.
- Start scanning the string from right one character at a time.
- If it is an operand, push it in stack.
- If it is an operator, pop opnd1, opnd2 and concatenate them in the order (opnd1, optr, opnd2) as follows:
strcpy(arr,opnd1);
strcat(arr,optr);
stracat(arr,opnd2);
Push the result in the stack.
- Repeat these steps until arr of input prefix string ends.
- Pop the remaining element of the stack, which is the required Infix notation equivalent to a given Prefix notation.
Program to convert Prefix expression to Infix:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define MAX 20
struct stack
{
int top;
char arr[MAX];
};
void push(struct stack *,char);
char pop(struct stack *);
int isdigit(char);
void prefix_to_infix(char instr[],char outstr[]);
void main()
{
clrscr();
char str[MAX],resstr[MAX];
printf(“nEnter a prefix string?”);
gets(str);
printf(“nPrefix string: %s”,str);
prefix_to_infix(str,resstr);
printf(“nInfix string: %s”,resstr);
getch();
}
void push(struct stack *s,char ch)
{
if(s->top==MAX-1)
{printf(“Stack Overflow!”);
exit(1);
}
s->arr[++(s->top)]=ch;
}
char pop(struct stack *s)
{
if(s->top==-1)
{printf(“Stack Underflow!”);
exit(1);
}
return(s->arr[(s->top)–]);
}
int isdigit(char ch)
{return(ch>=’0′ && ch<=’9′); }
void prefix_to_infix(char instr[],char outstr[])
{
int i,j,ct=1,z=0;
char ch,opnd1,opnd2;
struct stack stk;
stk.top=-1;
for(i=0;instr[i]!=’�’;i++);
for(j=i-1;j>=0;j–)
{
ch=instr[j];
if(isdigit(ch))
{push(&stk,ch);
}
else {
if(ct==1)
{opnd1=pop(&stk);
opnd2=pop(&stk);
outstr[z++]=opnd1;
outstr[z++]=ch;
outstr[z++]=opnd2;
ct++;
}
else {
opnd2=pop(&stk);
outstr[z++]=ch;
outstr[z++]=opnd2;
}
}
}
outstr[z]=’�’;
}
Conversion from Prefix to Postfix
Application of Stacks
Conversion from Prefix to Postfix
The algorithm for converting a Prefix expression to a Postfix notation is as follows:
- Accept a prefix string from the user.
- Start scanning the string from right one character at a time.
- If it is an operand, push it in stack.
- If it is an operator, pop opnd1, opnd2 and concatenate them in the order (opnd1, opnd2, optr) as follows:
strcpy(arr,opnd1);
strcat(arr,opnd2);
stracat(arr,optr);
Push the result in the stack.
- Repeat these steps until arr of input prefix string ends.
- Pop the remaining element of the stack, which is the required Postfix notation equivalent to a given Prefix notation.
Program to convert Prefix expression to Postfix:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define MAX 20
struct stack
{
int top;
char arr[MAX];
};
void push(struct stack *,char);
char pop(struct stack *);
int isdigit(char);
void prefix_to_postfix(char instr[],char outstr[]);
void main()
{
char str[MAX],resstr[MAX],temp[MAX];
int i,z;
clrscr();
printf(“nEnter a prefix string?”);
gets(str);
for(i=0;str[i]!=’�’;i++);
for(i=i-1,z=0;i>=0;z++,i–)
temp[z]=str[i];
temp[z]=’�’;
printf(“nPrefix string: %s”,str);
prefix_to_postfix(temp,resstr);
printf(“nPostfix string: %s”,resstr);
getch();
}
void push(struct stack *s,char ch)
{
if(s->top==MAX-1)
{printf(“Stack Overflow!”);
exit(1);
}
s->arr[++(s->top)]=ch;
}
char pop(struct stack *s)
{
if(s->top==-1)
{printf(“Stack Underflow!”);
exit(1);
}
return(s->arr[(s->top)–]);
}
int isdigit(char ch)
{return(ch>=’0′ && ch<=’9′);
}
void prefix_to_postfix(char instr[],char outstr[])
{
int i,j,ct=1,z=0;
char ch,opnd1,opnd2;
struct stack stk;
stk.top=-1;
for(i=0;instr[i]!=’�’;i++)
{
ch=instr[i];
if(isdigit(ch))
{push(&stk,ch);
}
else
{
if(ct==1)
{opnd1=pop(&stk);
opnd2=pop(&stk);
outstr[z++]=opnd1;
outstr[z++]=opnd2;
outstr[z++]=ch;
ct++;
}
else
{
opnd2=pop(&stk);
outstr[z++]=opnd2;
outstr[z++]=ch;
}
}
}
outstr[z]=’�’;
}
Conversion from Postfix to Infix
Application of Stacks
Conversion from Postfix to Infix
The algorithm for converting a Postfix expression to Infix notation is as follows:
- Accept a postfix string from the user.
- Start scanning the string from left to right one character at a time.
- If it is an operand, push it in stack.
- If it is an operator, pop opnd2, opnd1 and concatenate them in the order (opnd1, optr, opnd2) as follows:
strcpy(arr,opnd1);
strcat(arr,optr);
stract(arr,opnd2);
Push the result in the stack.
- Repeat these steps until arr of input postfix string ends.
- Pop the remaining element of the stack, which is the required Infix notation equivalent to a given Postfix notation.
Program to convert a Postfix expression to Infix:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define MAX 20
struct stack
{
int top;
char arr[MAX];
};
void push(struct stack *,char);
char pop(struct stack *);
int isdigit(char);
void postfix_to_infix(char instr[],char outstr[]);
void main()
{
char postfix[MAX],infix[MAX];
clrscr();
printf(“nEnter a postfix string?”);
gets(postfix);
printf(“nPostfix string is: %s”,postfix);
postfix_to_infix(postfix,infix);
printf(“nInfix string is: %s”,infix);
getch();
}
void push(struct stack *s,char ch)
{
if(s->top==MAX-1)
{printf(“Stack Overflow!”);
exit(1);
}
s->arr[++(s->top)]=ch;
}
char pop(struct stack *s)
{
if(s->top==-1)
{
printf(“Stack Underflow!”);
exit(1);
}
return(s->arr[(s->top)–]);
}
int isdigit(char ch)
{return(ch>=’0′ && ch<=’9′); }
void postfix_to_infix(char instr[],char outstr[])
{
int i,z=0,ct=1;
char ch,opnd1,opnd2;
struct stack stk;
stk.top=-1;
for(i=0;(ch=instr[i])!=’�’;i++)
{
if(isdigit(ch))
{push(&stk,ch); }
else {
if(ct==1)
{opnd2=pop(&stk);
opnd1=pop(&stk);
outstr[z++]=opnd1;
outstr[z++]=ch;
outstr[z++]=opnd2;
ct++;
}
else {opnd2=pop(&stk);
outstr[z++]=ch;
outstr[z++]=opnd2;
}
}
}
outstr[z]=’�’;
}
Conversion from Postfix to Prefix
Application of Stacks
Conversion from Postfix to Prefix
The algorithm for converting a Postfix expression to Prefix notation is as follows:
- Accept a postfix string from the user.
- Start scanning the string from left to right one character at a time.
- If it is an operand, push it in stack.
- If it is an operator, pop opnd2, opnd1 and concatenate them in the order (optr, opnd1, opnd2) as follows:
strcpy(arr,optr);
strcat(arr,opnd1);
stract(arr,opnd2);
Push the result in the stack.
- Repeat these steps until arr of input postfix string ends.
- Pop the remaining element of the stack, which is the required Prefix notation equivalent to a given Postfix notation.
Program to convert Postfix expression to Prefix:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define MAX 20
struct stack
{
int top;
char arr[MAX];
};
void push(struct stack *,char);
char pop(struct stack *);
int isdigit(char);
void postfix_to_prefix(char instr[],char outstr[]);
void main()
{
char str[MAX],resstr[MAX];
clrscr();
printf(“nEnter a postfix string?”);
gets(str);
printf(“nPostfix string: %s”,str);
postfix_to_prefix(str,resstr);
printf(“nPrefix string: %s”,resstr);
getch();
}
void push(struct stack *s,char ch)
{
if(s->top==MAX-1)
{printf(“Stack Overflow!”);
exit(1);
}
s->arr[++(s->top)]=ch;
}
char pop(struct stack *s)
{
if(s->top==-1)
{printf(“Stack Underflow!”);
exit(1);
}
return(s->arr[(s->top)–]);
}
int isdigit(char ch)
{return(ch>=’0′ && ch<=’9′);
}
void postfix_to_prefix(char instr[],char outstr[])
{
int i,j,ct=1,z=MAX-1;
char ch,opnd1,opnd2;
struct stack stk;
stk.top=-1;
for(i=0;instr[i]!=’�’;i++)
{
ch=instr[i];
if(isdigit(ch))
{push(&stk,ch);
}
else
{
if(ct==1)
{opnd2=pop(&stk);
opnd1=pop(&stk);
outstr[z–]=’�’;
outstr[z–]=opnd2;
outstr[z–]=opnd1;
outstr[z–]=ch;
ct++;
}
else
{
opnd2=pop(&stk);
outstr[z–]=opnd2;
outstr[z–]=ch;
}
}
}
for(i=0,z=z+1;outstr[z]!=’�’;i++,z++)
{
outstr[i]=outstr[z];
outstr[z]=’ ‘;
}
outstr[i]=’�’;
}
Conversion from Infix to Prefix
Application of Stacks
Conversion from Infix to Prefix
The algorithm for converting an Infix expression to Prefix is as follows:
An Infix expression is converted into Prefix using two stacks, one for operator and another for operands. The infix sting is read in an array, from which symbols/characters are fetched one by one and the following checks are performed:
- If symbol is an operand, push it in operand’s stack.
- Initialize operator stack with a dummy operator with the least precedence (say #).
- If the symbol is an operator, then do the following:
- Pop an operator from the operator stack.
- Check its precedence with the symbol.
- If the precedence of the symbol is higher, then simply push the popped operator and then the symbol.
- Else if the precedence of symbol is lower (or equal to) than the popped operator, pop two operands, (opnd2 and opnd1) and perform concatenation operation (optr, opnd1, opnd2).
- Push the result in operand’s stack.
- Repeat the above steps until the symbol becomes less than the popped operator.
- After the string ends, start popping an operator from the operator stack and two operands from operand stack.
- Repeat step (d) until dummy operator (#) is found.
- Pop the expression from the operand stack and return it, which is the desired Prefix equivalent of given Infix string.
Program to convert an Infix expression to Prefix:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 15
struct opndstack
{
int top;
char items[MAX][MAX];
};
struct optrstack
{
int top;
char items[MAX];
};
void init_opndstack(struct opndstack *);
void pushopnd(struct opndstack *,char[]);
void popopnd(struct opndstack *,char arr[]);
int isoperand(char);
void pushoptr(struct optrstack *,char);
char pop(struct optrstack *);
int isoperator(char);
void init_opndstack(struct opndstack * s)
{int i;
for(i=0;i<MAX;i++)
strcpy(s->items[i],””);
s->top=-1;
}
void pushopnd(struct opndstack *s,char ch[])
{
if(s->top==MAX-1)
{printf(“nStack full! Overflow.”);
exit(1);
}
else
{strcat(s->items[++(s->top)],ch);
}
}
void popopnd(struct opndstack *s,char str[])
{
if(s->top==-1)
{printf(“nStack empty! Underflow.”);
exit(1);
}
else
{strcpy(str,s->items[s->top]);
strcpy(s->items[s->top–],””);
}
}
int isoperand(char ch)
{return(ch>=’0′ && ch<=’9′);
}
void pushoptr(struct optrstack *s,char ch)
{
if(s->top==MAX-1)
{
printf(“nStack full! Overflow.”);
exit(1);
}
else
{
s->items[++(s->top)]=ch;
}
}
char popoptr(struct optrstack *s)
{
if(s->top==-1)
{printf(“nStack empty! Underflow.”);
exit(1);
}
else
{
return(s->items[(s->top)–]);
}
}
int isoperator(char ch)
{
switch(ch)
{
case ‘+’:
case ‘-‘:
case ‘*’:
case ‘/’:
case ‘^’:
return 1;
default :
return 0;
}
}
int precedence(char ch)
{
switch(ch)
{
case ‘#’:return 0;
case ‘+’:
case ‘-‘:return 1;
case ‘*’:
case ‘/’:return 2;
case ‘^’:return 3;
default :printf(“nInvalid operator!”);
exit(1);
}
}
void main()
{struct opndstack opndstk;
struct optrstack optrstk;
optrstk.top=-1;
pushoptr(&optrstk,’#’);
char str[MAX],outstr[MAX],instr[MAX];
char ch,soptr,soptrarr[MAX];
char opnd1[MAX],opnd2[MAX],res[MAX];
strcpy(res,””);
int i;
clrscr();
printf(“nEnter a string in infix form?”);
gets(str);
for(i=0;(instr[0]=str[i])!=’�’;i++)
{instr[1]=’�’;
ch=instr[0];
if(isoperand(ch))
pushopnd(&opndstk,instr);
if(isoperator(ch))
{soptr=popoptr(&optrstk);
if(precedence(ch)>precedence(soptr))
pushoptr(&optrstk,soptr);
else
{while(precedence(ch)<=precedence(soptr) && (soptr!=’#’))
{
popopnd(&opndstk,opnd2);
popopnd(&opndstk,opnd1);
soptrarr[0]=soptr;
soptrarr[1]=’�’;
strcat(res,soptrarr);
strcat(res,opnd1);
strcat(res,opnd2);
pushopnd(&opndstk,res);
strcpy(res,””);
soptr=popoptr(&optrstk);
}
if(soptr==’#’)
pushoptr(&optrstk,’#’);
}
pushoptr(&optrstk,ch);
}
}
soptr=popoptr(&optrstk);
while(soptr!=’#’)
{
strcpy(res,””);
popopnd(&opndstk,opnd2);
popopnd(&opndstk,opnd1);
soptrarr[0]=soptr;
soptrarr[1]=’�’;
strcat(res,soptrarr);
strcat(res,opnd1);
strcat(res,opnd2);
pushopnd(&opndstk,res);
soptr=popoptr(&optrstk);
}
strcpy(outstr,””);
strcpy(outstr,res);
printf(“nInfix expression is: %s”,str);
printf(“nEquivalent Prefix expression is: %s”,outstr);
getch();
}
Conversion from Infix to Postfix
Application of Stacks
Conversion from Infix to Postfix
The algorithm for converting an Infix expression to Postfix is as follows:
An Infix expression is converted into Postfix using two stacks, one for operator and another for operands. The infix sting is read in an array, from which symbols/characters are fetched one by one and the following checks are performed:
- If symbol is an operand, push it in operand’s stack.
- Initialize operator stack with a dummy operator with the least precedence (say #).
- If the symbol is an operator, then do the following:
- Pop an operator from the operator stack.
- Check its precedence with the symbol.
- If the precedence of the symbol is higher, then simply push the popped operator and then the symbol.
- Else if the precedence of symbol is lower (or equal to) than the popped operator, pop two operands, (opnd2 and opnd1) and perform concatenation operation (opnd1, opnd2, optr).
- Push the result in operand’s stack.
- Repeat the above steps until the symbol becomes less than the popped operator.
- After the string ends, start popping an operator from the operator stack and two operands from operand stack.
- Repeat step (d) until dummy operator (#) is found.
- Pop the expression from the operand stack and return it, which is the desired Postfix equivalent of given Infix string.
Equivalent Postfix expression
Program to convert and Infix expression to Postfix
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 15
struct opndstack
{
int top;
char items[MAX][MAX];
};
struct optrstack
{
int top;
char items[MAX];
};
void init_opndstack(struct opndstack *);
void pushopnd(struct opndstack *,char[]);
void popopnd(struct opndstack *,char arr[]);
int isoperand(char);
void pushoptr(struct optrstack *,char);
char pop(struct optrstack *);
int isoperator(char);
void init_opndstack(struct opndstack * s)
{int i;
for(i=0;i<MAX;i++)
strcpy(s->items[i],””);
s->top=-1;
}
void pushopnd(struct opndstack *s,char ch[])
{
if(s->top==MAX-1)
{printf(“nStack full! Overflow.”);
exit(1);
}
else
{strcat(s->items[++(s->top)],ch);
}
}
void popopnd(struct opndstack *s,char str[])
{
if(s->top==-1)
{printf(“nStack empty! Underflow.”);
exit(1);
}
else
{strcpy(str,s->items[s->top]);
strcpy(s->items[s->top–],””);
}
}
int isoperand(char ch)
{return(ch>=’0′ && ch<=’9′);
}
void pushoptr(struct optrstack *s,char ch)
{
if(s->top==MAX-1)
{
printf(“nStack full! Overflow.”);
exit(1);
}
else
{
s->items[++(s->top)]=ch;
}
}
char popoptr(struct optrstack *s)
{
if(s->top==-1)
{printf(“nStack empty! Underflow.”);
exit(1);
}
else
{
return(s->items[(s->top)–]);
}
}
int isoperator(char ch)
{
switch(ch)
{
case ‘+’:
case ‘-‘:
case ‘*’:
case ‘/’:
case ‘^’:
return 1;
default :
return 0;
}
}
int precedence(char ch)
{
switch(ch)
{
case ‘#’:return 0;
case ‘+’:
case ‘-‘:return 1;
case ‘*’:
case ‘/’:return 2;
case ‘^’:return 3;
default :printf(“nInvalid operator!”);
exit(1);
}
}
void main()
{struct opndstack opndstk;
struct optrstack optrstk;
optrstk.top=-1;
pushoptr(&optrstk,’#’);
char str[MAX],outstr[MAX],instr[MAX];
char ch,soptr,soptrarr[MAX];
char opnd1[MAX],opnd2[MAX],res[MAX];
strcpy(res,””);
int i;
clrscr();
printf(“nEnter a string in infix form?”);
gets(str);
for(i=0;(instr[0]=str[i])!=’�’;i++)
{instr[1]=’�’;
ch=instr[0];
if(isoperand(ch))
pushopnd(&opndstk,instr);
if(isoperator(ch))
{soptr=popoptr(&optrstk);
if(precedence(ch)>precedence(soptr))
pushoptr(&optrstk,soptr);
else
{while(precedence(ch)<=precedence(soptr) && (soptr!=’#’))
{
popopnd(&opndstk,opnd2);
popopnd(&opndstk,opnd1);
strcat(res,opnd1);
strcat(res,opnd2);
soptrarr[0]=soptr;
soptrarr[1]=’�’;
strcat(res,soptrarr);
pushopnd(&opndstk,res);
strcpy(res,””);
soptr=popoptr(&optrstk);
}
if(soptr==’#’)
pushoptr(&optrstk,’#’);
}
pushoptr(&optrstk,ch);
}
}
soptr=popoptr(&optrstk);
while(soptr!=’#’)
{
strcpy(res,””);
popopnd(&opndstk,opnd2);
popopnd(&opndstk,opnd1);
soptrarr[0]=soptr;
soptrarr[1]=’�’;
strcat(res,opnd1);
strcat(res,opnd2);
strcat(res,soptrarr);
pushopnd(&opndstk,res);
soptr=popoptr(&optrstk);
}
strcpy(outstr,””);
strcpy(outstr,res);
printf(“nInfix expression is: %s”,str);
printf(“nEquivalent Postfix expression is: %s”,outstr);
getch();
}
Evaluation of Infix expression
Application of Stacks
Evaluation of Infix expression
An infix expression is evaluated using two stacks, one for operator and another for operands. The infix sting is read in an array, from which symbols/characters are fetched one by one and the following checks are performed:
- If symbol is an operand, push it in operand’s stack.
- Initialize operator stack with a dummy operator with the least precedence (say #).
- If the symbol is an operator, then do the following:
- Pop an operator from the operator stack.
- Check its precedence with the symbol.
- If the precedence of the symbol is higher, then simply push the popped operator and then the symbol.
- Else if the precedence of symbol is lower (or equal to) than the popped operator, pop two operands, (opnd2 and opnd1) and perform operation specified by popped operator.
- Push the result in operand’s stack.
- Repeat above steps until the symbol becomes less than the popped operator.
- After the string ends, start popping an operator from the operator stack and two operands from operand stack.
- Repeat step (d) until dummy operator (#) is found.
- Pop the value from the operand stack and return it.
Program to evaluate an Infix expression:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <math.h>
#define MAX 10
struct opndstack
{
int top;
double items[MAX];
};
struct optrstack
{
int top;
char items[MAX];
};
void pushopnd(struct opndstack *s,double val)
{
if(s->top==MAX-1)
{
printf(“nStack Overflow.”);
exit(1);
}
else
{s->items[++(s->top)]=val;
}
}
double popopnd(struct opndstack *s)
{
if(s->top==-1)
{
printf(“nStack Underflow.”);
exit(1);
}
else
{
return(s->items[(s->top)–]);
}
}
void pushoptr(struct optrstack *s,char ch)
{
if(s->top==MAX-1)
{
printf(“nStack Overflow.”);
exit(1);
}
else
{s->items[++(s->top)]=ch;
}
}
char popoptr(struct optrstack *s)
{
if(s->top==-1)
{
printf(“nStack Underflow.”);
exit(1);
}
else
{
return(s->items[(s->top)–]);
}
}
int isdigit(char ch)
{return(ch>=’0′ && ch<=’9′);
}
int isoperator(char ch)
{
switch(ch)
{
case ‘+’:
case ‘-‘:
case ‘*’:
case ‘/’:
case ‘^’:
return 1;
default:
return 0;
}
}
double eval(char ch,double opnd1,double opnd2)
{
switch(ch)
{
case ‘+’:return(opnd1+opnd2);
case ‘-‘:return(opnd1-opnd2);
case ‘*’:return(opnd1*opnd2);
case ‘/’:return(opnd1/opnd2);
case ‘^’:return(pow(opnd1,opnd2));
default:printf(“nInvalid operator.”);
exit(1);
}
}
int precedence(char ch)
{
switch(ch)
{
case ‘#’: return 0;
case ‘+’:
case ‘-‘: return 1;
case ‘*’:
case ‘/’:return 2;
case ‘^’:return 3;
case ‘(‘:return 4;
default :printf(“nInvalid operator.”);
exit(1);
}
}
double infix(char str[])
{
double opnd1,opnd2,value;
char ch;
opndstack opndstk;
optrstack optrstk;
opndstk.top=-1;
optrstk.top=-1;
pushoptr(&optrstk,’#’);
int i=0;
char optr2;
for(i=0;str[i]!=’�’;i++)
{
if(isdigit(str[i]))
pushopnd(&opndstk,(double)(str[i]-‘0′));
else if(isoperator(str[i]))
{optr2=popoptr(&optrstk);
if(precedence(str[i])>precedence(optr2))
{pushoptr(&optrstk,optr2);
pushoptr(&optrstk,str[i]);
}
else
{
while(precedence(str[i])<=precedence(optr2))
{ opnd2=popopnd(&opndstk);
opnd1=popopnd(&opndstk);
value = eval(optr2,opnd1,opnd2);
pushopnd(&opndstk,value);
optr2=popoptr(&optrstk);
}
pushoptr(&optrstk,optr2);
pushoptr(&optrstk,str[i]);
}
}
}
while((ch=popoptr(&optrstk))!=’#’)
{
opnd2=popopnd(&opndstk);
opnd1=popopnd(&opndstk);
value=eval(ch,opnd1,opnd2);
pushopnd(&opndstk,value);
}
return(popopnd(&opndstk));
}
void main()
{
char str[80];
int i;
clrscr();
printf(“nEnter an infix string?”);
for(i=0;(str[i]=getchar())!=’n’;i++);
str[i]=’�’;
printf(“nInfix String = %s”,str);
printf(“nEvaluation of infix = %f”,infix(str));
getch();
}
Evaluation of Prefix expression
Application of Stacks
Advertisement
Evaluation of Prefix expression
The algorithm for evaluating a prefix expression is as follows:
- Accept a prefix string from the user.
say (-*+ABCD), let A=4, B=3, C=2, D=5
i.e. (-*+4325) is the input prefix string.
- Start scanning the string from the right one character at a time.
- If it is an operand, push it in stack.
- If it is an operator, pop opnd1, opnd2 and perform the operation, specified by the operator. Push the result in the stack.
- Repeat these steps until arr of input prefix strings ends.
This algorithm works fine, if given prefix expressions are evaluated from left to right without considering precedence of operators, which will not give correct result in all the cases, where precedence rules of operators must be followed to get correct result.
For example: Consider the following two prefix notations:
(a) +*435 and (b) *+435
Infix equivalent of a is 4*3+5 and that of b is 4+3*5. Result of a is 12+5=17 and that of b is 7*5=35, which is not the desired result since the precedence of * operator is higher as compared to +. Result should be 4+3*5=4+15 = 19 or if the expression is (4+3)*5, then (7)*5=7*5=35.
Thus precedence of operators and availability of brackets must be kept in mind for evaluating a given prefix string to result in a correct output.
Therefore, correct result may only be achieved from a prefix string, if while converting from infix to prefix, due consideration is kept in mind for precedence of operators and that of brackets.
Program to evaluate Prefix expression:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <math.h>
#define MAX 80
struct stack
{int top;
double items[MAX];
};
void push(struct stack *,int);
int pop(struct stack *);
void display(struct stack *);
int isdigit(char);
double eval(char []);
double oper(char,double,double);
void push(struct stack *s,int x)
{
if(s->top==MAX-1)
{printf(“nStack Overflow…!”);
return;
}
else
{s->items[++s->top]=x;
}
}
int pop(struct stack *s)
{
if(s->top==-1)
{printf(“nStack Underflow…!”);
return 0;
}
else
{return(s->items[s->top–]);
}
}
void display(struct stack *s)
{
int ctr;
if(s->top==-1)
{printf(“nStack is empty…!”);
return;
}
else
{
ctr=s->top;
while(ctr!=-1)
printf(“%dt”,s->items[ctr–]);
}
}
int isdigit(char ch)
{
return(ch>=’0′ && ch<=’9′);
}
double oper(char c,double opnd1,double opnd2)
{
switch(c)
{
case ‘+’: return(opnd1+opnd2);
case ‘-‘: return(opnd1-opnd2);
case ‘*’: return(opnd1*opnd2);
case ‘/’: return(opnd1/opnd2);
case ‘^’: return(pow(opnd1,opnd2));
default: printf(“nInvalid operator…!”);return 0;
}
}
double eval(char str[])
{
char c;
double opnd1,opnd2,val;
struct stack stk;
stk.top=-1;
int i;
for(i=0;(c=str[i])!=’�’;i++)
{
if(isdigit(c))
push(&stk,(double)(c-‘0′));
else
{
opnd2=pop(&stk);
opnd1=pop(&stk);
val=oper(c,opnd1,opnd2);
push(&stk,val);
}
}
return(pop(&stk));
}
void main()
{
char str[MAX];
int i,j,k;
char temp;
clrscr();
printf(“ntEnter prefix string:”);
for(i=0;(str[i]=getchar())!=’n’;i++);
str[i]=’�’;
k=i;
printf(“nThe prefix expression is: %s”,str);
for(i=0,j=k-1;i<=j;i++,j–)
{
temp=str[i];
str[i]=str[j];
str[j]=temp;
}
printf(“nPrefix expression after reversing is %s”,str);
printf(“nResult after evaluation is: %f”,eval(str));
getch();
}
Evaluation of Postfix expression
Application of Stacks
Evaluation of Postfix expression
The algorithm for evaluating a postfix expression is as follows:
- Accept a postfix string from the user.
say (ABCD*+-), let A=4, B=3, C=2, D=5
i.e. (4325*+-) is the input postfix string.
- Start scanning the string from left to right one character at a time.
- If it is an operand, push it in stack.
- If it is an operator, pop opnd2, opnd1 and perform the operation, specified by the operator. Push the result in the stack.
- Repeat these steps until arr of input postfix string ends.
The postfix string, entered, as an input must be converted from infix string considering precedence rules of operators and brackets for getting correct result. The program to evaluate a given postfix expression is as follows:
Program to evaluate a Postfix expression:
/*Evaluation of post-fix expression using stack.*/
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <math.h>
#define MAX 80
struct stack
{int top;
double items[MAX];
};
void push(struct stack *,int);
int pop(struct stack *);
void display(struct stack *);
int isdigit(char);
double eval(char []);
double oper(char,double,double);
void push(struct stack *s,int x)
{
if(s->top==MAX-1)
{printf(“nStack Overflow…!”);
return;
}
else
{s->items[++s->top]=x;
}
}
int pop(struct stack *s)
{
if(s->top==-1)
{printf(“nStack Underflow…!”);
return 0;
}
else
{return(s->items[s->top–]);
}
}
void display(struct stack *s)
{
int ctr;
if(s->top==-1)
{printf(“nStack is empty…!”);
return;
}
else
{
ctr=s->top;
while(ctr!=-1)
printf(“%dt”,s->items[ctr–]);
}
}
int isdigit(char ch)
{
return(ch>=’0′ && ch<=’9′);
}
double oper(char c,double opnd1,double opnd2)
{
switch(c)
{
case ‘+’: return(opnd1+opnd2);
case ‘-‘: return(opnd1-opnd2);
case ‘*’: return(opnd1*opnd2);
case ‘/’: return(opnd1/opnd2);
case ‘^’: return(pow(opnd1,opnd2));
default: printf(“nInvalid operator…!”);return 0;
}
}
double eval(char str[])
{
char c;
double opnd1,opnd2,val;
struct stack stk;
stk.top=-1;
int i;
for(i=0;(c=str[i])!=’�’;i++)
{
if(isdigit(c))
push(&stk,(double)(c-‘0’));
else
{
opnd2=pop(&stk);
opnd1=pop(&stk);
val=oper(c,opnd1,opnd2);
push(&stk,val);
}
}
return(pop(&stk));
}
void main()
{
char str[MAX];
int i;
clrscr();
for(i=0;(str[i]=getchar())!=’n’;i++);
str[i]=’�’;
printf(“nThe postfix expression is: %s”,str);
printf(“nResult after evaluation is: %f”,eval(str));
getch();
}
Parenthesis checker
Application of Stacks
Parenthesis checker
It is an algorithm that confirms that the number of closing parenthesis equals opening parenthesis by using stack. If number of closing parenthesis is not equal to the number of opening parenthesis, then it results in an error. Input a string from the user. The user must enter a set of opening and closing parenthesis as follows:
(()(()))
Scan the above input string from first character until NULL is found. If it is an opening parenthesis, then push it in the stack, otherwise, if a closing parenthesis is found, pop the topmost element of the stack. If the string ends and the stack becomes empty, then there is a perfect match, otherwise, you may report error by returning appropriate value to the invoking function.
Program for Parenthesis checker is as follows:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define MAX 20
struct stack
{
int top;
char arr[MAX];
};
void push(struct stack *s,char ch)
{
if(s->top==MAX-1)
{printf(“Stack Overflow.”);
exit(1);
}
s->arr[++(s->top)]=ch;
}
char pop(struct stack *s)
{
if(s->top==-1)
{printf(“Stack Underflow.”);
exit(1);
}
return(s->arr[s->top–]);
}
int parenthesischecker(char str[])
{
struct stack s;
char ch;
int i,flag=0;/*0 for no error, 1 for error*/
s.top=-1;
for(i=0;((str[i]!=”) && (flag==0));i++)
{if(str[i]=='(‘)
push(&s,str[i]);
else
{ch=pop(&s);
if(ch!='(‘)
flag=1;
}
}
if(s.top!=-1)
flag=1;
return flag;
}
void main()
{
char str[MAX],flag;
clrscr();
printf(“nEnter a string of parenthesis?”);
gets(str);
flag=parenthesischecker(str);
if(flag==0)
{printf(“nParenthesis Match O.K.”);
}
else
{printf(“nOpening/Closing Parenthesis do not match.”);
}
getch();
}
