Learn To Solve It
Exercise 4.4 - RPN Calculator - print two top elements of the stack without popping¶
Question¶
Add the commands to print the top elements of the stack without popping, to duplicate it, and to swap the top two elements. Add a command to clear the stack.
#include <ctype.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#define MAXOP 100
#define NUMBER '0'
#define BUFSIZE 100
#define MAXVAL 100
int bufp = 0;
int sp = 0;
double val[MAXVAL];
char buf[BUFSIZE];
int getch(void);
void ungetch(int);
int getop(char[]);
void push(double);
double pop(void);
/* reverse polish calculator */
int main(void) {
int type;
double op2, op1;
char s[MAXOP];
void clearsp(void);
while ((type = getop(s)) != EOF) {
switch (type) {
case NUMBER:
push(atof(s));
break;
case '+':
push(pop() + pop());
break;
case '*':
push(pop() * pop());
break;
case '-':
op2 = pop();
push(pop() - op2);
break;
case '/':
op2 = pop();
if (op2 != 0.0)
push(pop() / op2);
else
printf("error:zero divisor\n");
break;
case '%':
op2 = pop();
if (op2 != 0.0)
push(fmod(pop(), op2));
else
printf("erro:zero divisor\n");
break;
case '?':
op2 = pop();
printf("\t%.8g\n", op2);
push(op2);
break;
case 'c':
clearsp();
break;
case 'd':
op2 = pop();
push(op2);
push(op2);
break;
case 's':
op1 = pop();
op2 = pop();
push(op1);
push(op2);
break;
case '\n':
printf("\t%.8g\n", pop());
break;
default:
printf("error: unknown command %s\n", s);
break;
}
}
return 0;
}
void push(double f) {
if (sp < MAXVAL)
val[sp++] = f;
else
printf("error:stack full, cant push %g\n", f);
}
double pop(void) {
if (sp > 0)
return val[--sp];
else {
printf("error: stack empty\n");
return 0.0;
}
}
void clearsp(void) { sp = 0; }
int getop(char s[]) {
int i, c;
while ((s[0] = c = getch()) == ' ' || c == '\t');
s[1] = '\0';
i = 0;
if (!isdigit(c) && c != '.' && c != '-')
return c;
if (c == '-')
if (isdigit(c = getch()) || c == '.')
s[++i] = c;
else {
if (c != EOF)
ungetch(c);
return '-';
}
if (isdigit(c))
while (isdigit(s[++i] = c = getch()));
if (c == '.')
while (isdigit(s[++i] = c = getch()));
s[i] = '\0';
if (c != EOF)
ungetch(c);
return NUMBER;
}
int getch(void) { return (bufp > 0) ? buf[--bufp] : getchar(); }
void ungetch(int c) {
if (bufp >= BUFSIZE)
printf("ungetch: too many characters\n");
else
buf[bufp++] = c;
}
Explanation¶
This program has number of helper functions like getop, push and pop, which we use to the implement the reverse polish notation calculator. It enhances the RPN calculator with additional features like d to double the entries of the top two elements, s to swap the entries of the top two elements, ? to display the top element and finally c to clear the stack.
The function getop takes a string and determines if it is number. If it is a number, both integer or decimal, it will store that number in the array and return a flag NUMBER which states that number is found. It will push that number to the stack. If it getop returns an operator like +, -, * or /, it will pop two numbers out of the stack and operate on it. When it encounters a /, it ensures that the second operand is not 0 and disallows.
It pushes each number to the stack and when it finds an operand, it will pop out two numbers in the stack and operate on it and push the result back into the stack. When it encounters a n it will pop out the last stored number in the stack and gives the result.
On d, It doubles the characters.
On s, It swaps the characters.
On c, It clears the characters in the stack.
On ?, It goes to the top element of the stack.
So here is how the expression is evaluated.
1 d + 3 s ?
2
2
?
3
3
?
It takes 1 and d doubles it. So our stack will be 1 1. And then when it sees +, it will add the two values and substitute with the result. So our stack will now be 2. We push 3 to the stack and s swaps it. Our stack will be 3 2. So when we input ? and enter. We get the top element 2 out. And then pressing ? again will pop next element 3.