You cannot copy content of this page.
The algorithm for converting a Prefix expression to an Infix notation is as follows:
strcpy(arr,opnd1);
strcat(arr,optr);
stracat(arr,opnd2);
Push the result in the stack.
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]=’�’;
}
The algorithm for converting a Prefix expression to a Postfix notation is as follows:
strcpy(arr,opnd1);
strcat(arr,opnd2);
stracat(arr,optr);
Push the result in the stack.
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]=’�’;
}
The algorithm for converting a Postfix expression to Infix notation is as follows:
strcpy(arr,opnd1);
strcat(arr,optr);
stract(arr,opnd2);
Push the result in the stack.
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]=’�’;
}
The algorithm for converting a Postfix expression to Prefix notation is as follows:
strcpy(arr,optr);
strcat(arr,opnd1);
stract(arr,opnd2);
Push the result in the stack.
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]=’�’;
}
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:
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();
}
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:
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();
}
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:
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();
}
Advertisement
The algorithm for evaluating a prefix expression is as follows:
say (-*+ABCD), let A=4, B=3, C=2, D=5
i.e. (-*+4325) is the input prefix string.
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();
}
The algorithm for evaluating a postfix expression is as follows:
say (ABCD*+-), let A=4, B=3, C=2, D=5
i.e. (4325*+-) is the input postfix string.
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();
}
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();
}