You cannot copy content of this page.
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();
}