One way to evaluate a prefix expression is to use a queue. To evaluate the expre
ID: 3547447 • Letter: O
Question
One way to evaluate a prefix expression is to use a queue. To evaluate the expression, scan it repeatedly until the final expression value is known. In each scan, read the tokens and store them in a queue. In each scan, replace an operator followed by two operands by the calculated values. For example, the following expression is a prefix expression, which is evaluated to 159. - + * 9 + 2 8 * + 4 8 6 3 We scan the expression and score it in a queue. During the scan, when an operator is followed by two operands, such as + 2 8, we put the result, 10 in the queue. After the first scan, we have - + * 9 10 * 12 6 3 After the second scan, we have - + 90 72 3 After the third scan, we have - 162 3 After the fourth scan, we have 159Explanation / Answer
#include<stdio.h>
#include<conio.h>
#include<math.h>
#include<string.h>
#define MAX 30
#define OPERAND 10
#define OPERATOR 20
typedef struct prexp
{
int top;
int stack[MAX];
}stck;
void init(stck*);
void push(stck*,int);
int pop(stck*);
void eval(stck*,char,int,int);
int gettype(char);
void main()
{
char pre[MAX];
int num1,num2,item,l,i,pr;
stck stk;
fflush(stdin);
clrscr();
init(&stk);
printf(" ENTER THE PREFIX EXPRESSION ");
gets(pre);
l=strlen(pre);
for(i=l-1;i>=0;i--)
{
if(pre[i]==' ' || pre[i]=='')
continue;
switch(gettype(pre[i]))
{
case OPERAND : item=pre[i]-'0';
push(&stk,item);
break;
case OPERATOR : num1=pop(&stk);
num2=pop(&stk);
eval(&stk,pre[i],num1,num2);
}
}
printf("%d",stk.stack[0]);
getch();
}
void init(stck *st )
{
st->top=-1;
}
void push(stck *st,int num)
{
st->top++;
st->stack[st->top]=num;
}
int pop(stck *st)
{
int num;
num=st->stack[st->top];
st->top--;
return num;
}
void eval(stck *st,char op,int num1,int num2)
{
int res;
switch(op)
{
case '+': res=num1+num2;
break;
case '-': res=num1-num2;
break;
case '*': res=num1*num2;
break;
case '/': res=num1/num2;
break;
case '%': res=num1%num2;
break;
case '$': res=pow(num1,num2);
break;
}
push(st,res);
}
int gettype(char c)
{
switch(c)
{
case '+':
case '-':
case '*':
case '/':
case '$':
case '%': return OPERATOR;
default : return OPERAND;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.