You are provided with a sample C programs: calc.c, which implements a reverse polish notation
calculator. Study it carefully. This program uses a stack (of course!) but the stack implementation
is missing and you have to add it. You are to use the linked list structure defined within the
program, to implement a stack. In short, you need to implement the functions pop() and push()
using a linked list.
You are provided with calc-array.c which is a full implementation of the calculator, and uses an
array to implement the stack. Compile and run this program and test it (for instance enter 4 5 3 +
* <ENTER> as standard input and see that you get 32 as the answer). You should use the output
of this program to check that your own implementation is doing the right thing.
#include <stdio.h>
#include <stdlib.h> /* for atof() */
#define MAXOP 100 /* max size of operand or operator */
#define NUMBER '0' /* signal that a number was found */
/* useful prototypes. */
int getop(char []);
void push(double);
double pop(void);
/* reverse Polish calculator */
int main(void)
{
int type;
double op2;
char s[MAXOP];
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 '\n':
printf("\t%.8g\n", pop());
break;
default:
printf("error: unknown command %s\n", s);
break;
}
}
return 0;
}
#include <ctype.h>
int getch(void);
void ungetch(int);
/* getop: get next operator or numeric operand */
int getop(char s[])
{
int i, c;
while((s[0] = c = getch()) == ' ' || c == '\t')
;
s[1] = '\0';
if(!isdigit(c) && c != '.')
return c; /* not a number */
i = 0;
if(isdigit(c)) /* collect integer part */
while(isdigit(s[++i] = c = getch()))
;
if(c == '.')
while(isdigit(s[++i] = c = getch()))
;
s[i] = '\0';
if(c != EOF)
ungetch(c);
return NUMBER;
}
#define BUFSIZE 100
char buf[BUFSIZE]; /* buffer for ungetch */
int bufp = 0; /* next free position in buf */
int getch(void) /* get a (possibly pushed back) character */
{
return (bufp > 0) ? buf[--bufp] : getchar();
}
void ungetch(int c) /* push character back on input */
{
if(bufp >= BUFSIZE)
printf("ungetch: too many characters\n");
else
buf[bufp++] = c;
}
typedef struct list_t {
double item;
struct list_t *next;
} list_t;
list_t *st = NULL; /* To be used as our stack. Starts out as empty (NULL). */
/* push: push f onto value stack */
void push(double f)
{
/* Your code goes here. */
}
/* pop: pop and return top value from stack */
double pop(void)
{
/* Your code goes here. */
}