In this assignment, you will be using the STL stack to implement a calculator th
ID: 3559971 • Letter: I
Question
In this assignment, you will be using the STL stack to implement a calculator that calculates
arithmetic expressions. The trick is, that this calculator will be using prefix notation, otherwise
known as polish notation, for the expressions.
Definition:
In contrast to normal arithmetic notation, in prefix notation, operators are placed to the LEFT of
their operands, not inbetween them. One of the advantages of this notation is that it removes the
need for parentheses.
For example, the notation
(5 - 4) * 3
in polish notation is
*-543
To evaluate, you can simply go through the string from right to left (reverse from reading
direction) until you find an operator, then replace the operator and the two values to the right of
the operator with the result. Continue doing this until you get the final result.
The expression
3 - (4 * 2)
in polish notation is
-5*42
So what is our algorithm to implement this with a computer? Simply use a stack! This is again an
example of how a stack can make some tasks much easier to deal with. Go from right to left,
pushing the input string operand by operand onto the stack, until you encounter an operator in
the input string. Note that a space is used to separate operators and operands from each other.
When you encounter an operator, pop the top two elements of the stack, do the operation, and
push the result onto the stack. Then continue on reading in the string.
Task:
Write a program that takes a string from the user. This string should be a prefix expression, with
the allowable operators +, -, * and /. The allowable operands are any number from 1-1000. Skip
any blank space in the input string (dont push it on the stack or do anything with spaces). Spaces
are the only delimiters necessary.
The program should then calculate the value of that prefix expression and output the result.Details:
When going through your stack and evaluating any operands, I want you to display to the screen
the results of subexpressions before you push them onto the stack. This is for my own grading
purposes (and should help you with debugging!).
Another larger example:
? * / 15 ? 7 + 1 1 3 + 2 + 1 1
is equivalent to
((15 / (7 ? (1 + 1))) * 3) * (2 + (1 + 1)) = 5
Since the user is entering a string and you will be pushing various substrings onto the stack, you
will need to do conversions from strings to integer values and back again in order to push back
on the stack. I suggest using the following syntax to do so:
atoi(str.c_str() )
You can truncate the result of any divisions.
Explanation / 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;
}
}