cstackcalculatorpolish

K&R possible bug in polish calculator

I'm not sure where to post this but I think I found a pretty major bug in K&R's polish calculator program. Basically, when you perform an operation, two values get popped while only the result gets pushed. The problem is that the result isn't getting pushed to the top of the stack! Here's an illustration:

Polish calculator bug

The full code for the polish calculator provided by the textbook is shown below:

#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 */

int getop(char []);
void push(double);
double pop(void);

/* reverse Polish calculator */
main()
{
    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;
        }
    }
    system("Pause");
    return 0;
}

#define MAXVAL 100 /* maximum depth of val stack */

int sp = 0; /* next free stack position */
double val[MAXVAL]; /* value stack */

/* push: push f onto value stack */
void push(double f)
{
    if ( sp < MAXVAL)
        val[sp++] = f;
    else
        printf("error: stack full. can't push %g\n", f);
}

/* pop: pop and return top value from stack */
double pop(void)
{
    if (sp > 0)
        return val[--sp];
    else {
        printf("error: stack empty\n");
        return 0.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 == '.') /*collect fraction part*/
        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;
}

If you want to check for yourself, all I did was add 

static int pass = 0;
int i, check;
i = check = 0;

inside the while loop in main() and 

if(!check) {
    printf("pass #%d\n",pass++);
    while(val[i] != '\0') {
        printf("val[%d]: %.2f\n",i,val[i]);
        ++i;
    }
}

at the end of the while loop, just after the switch statement. I also put check = 1; in the case for '\n'.

As a possible workaround I re-wrote the pop function such that popped values are removed from the val array as soon as they are accessed. So instead of

double pop(void)
{
    if (sp > 0)
        return val[--sp];
    else {
        printf("error: stack empty\n");
        return 0.0;
    }
}

you'd have something like

double pop(void)
{
    if (sp > 0) {
        double temp = val[--sp];
        val[sp] = '\0';
        return temp;
    }
    else {
        printf("error: stack empty\n");
        return 0.0;
    }
}

I also re-wrote the push function to ensure that values are always pushed to the end of the val array. So instead of

void push(double f)
{
    if ( sp < MAXVAL)
        val[sp++] = f;
    else
        printf("error: stack full. can't push %g\n", f);
}

you'd have

void push(double f)
{
    if ( sp < MAXVAL) {
        while (val[sp] != '\0')
            ++sp;
        val[sp++] = f;
    }
    else
        printf("error: stack full. can't push %g\n", f);
}

Even with these changes, I still had to re-write

case '\n':
        printf("\t%.8g\n", pop());
        break;

to retrieve the value at the top of the stack without popping it, which required replacing the printf statement with a simple function like

void print_top(void)
{
    int i = 0;
    while( val[i] != '\0' )
        ++i;
    --i;
    printf("\t%.8g\n",val[i]);
}

Only then does the polish calculator seem to function as intended, at least in terms of what the stack is doing behind the scenes. You can try it out for yourself with the modified code:

#include <stdio.h>
#include <stdlib.h> /* for atof() */
#include <ctype.h>

#define MAXOP 100 /* max size of operand or operator */
#define NUMBER '0' /* signal that a number was found */
#define MAXVAL 100 /* maximum depth of val stack */

int getop(char []);
void push(double);
double pop(void);
void print_top(void);

int sp = 0; /* next free stack position */
double val[MAXVAL]; /* value stack */

/* reverse Polish calculator */
main()
{
    int type;
    double op2;
    char s[MAXOP];

    while ((type= getop(s)) != EOF) {

        static int pass = 0;
        int i, check;
        i = check = 0;

        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':
            print_top();
            check = 1;
            break;
        default:
            printf("error: unknown command %s\n", s);
            break;
        }
        if(!check) {
            printf("pass #%d\n",pass++);
            while(val[i] != '\0') {
                printf("val[%d]: %.2f\n",i,val[i]);
                ++i;
            }
        }
    }
    system("Pause");
    return 0;
}

/* push: push f onto value stack */
void push(double f)
{
    if ( sp < MAXVAL) {
        while (val[sp] != '\0')
            ++sp;
        val[sp++] = f;
    }
    else
        printf("error: stack full. can't push %g\n", f);
}

/* pop: pop and return top value from stack */
double pop(void)
{
    if (sp > 0) {
        double temp = val[--sp];
        val[sp] = '\0';
        return temp;
    }
    else {
        printf("error: stack empty\n");
        return 0.0;
    }
}

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 == '.') /*collect fraction part*/
        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;
}

void print_top(void)
{
    int i = 0;
    while( val[i] != '\0' )
        ++i;
    --i;
    printf("\t%.8g\n",val[i]);
}

Note that I had to move most of my #define statements and prototype declarations to the beginning in order to accommodate for the debugging printfstatement at the end of main().

*Edited out some of my audacious claims :P

Solution

    1. You're thinking of the stack backwards - the top of the stack is in the highest valid index, not in val[0]. This behaviour is evident when you look at the pushes of the operands. Your output:

      3 4 +
pass #0
val[0]: 3.00
pass #1
val[0]: 3.00
val[1]: 4.00

      First, the 3 is pushed - going onto the top of the (previously empty) stack - it's in slot 0. Next 4 is pushed. As you can see, it goes into val[1], clearly showing that val[0] is not the top of the stack in this case.

    2. You're printing the stack incorrectly, which is confusing you further. Change your print loop to:

      while (i < sp) {
    printf("val[%d]: %.2f\n",i,val[i]);
    ++i;
}

      That is, print only the valid entries in the stack, and you'll see your error.

      Your current comparison is looking for a 0 entry on the stack, which isn't how the program is identifying the free entries. That's what the sp variable is used for. In addition to looking for the wrong thing, it's doing it in a bizarro way - val is a an array of floating-point numbers - why are you comparing to a character literal \0?

      Here's the complete corrected output:

      3 4 +
pass #0
val[0]: 3.00
pass #1
val[0]: 3.00
val[1]: 4.00
pass #2
val[0]: 7.00
    7

      Now, you see the correct output - both the 3.00 and 4.00 are popped, and 7.00 is pushed back onto the stack. It's now the only valid entry.