StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POK&R possible bug in polish calculator
text
Body
copied!<p>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:</p> <p><img src="https://i.stack.imgur.com/fp4Ac.png" alt="Polish calculator bug"></p> <p>The full code for the polish calculator provided by the textbook is shown below:</p> <pre><code>#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; } </code></pre> <p>If you want to check for yourself, all I did was add </p> <pre><code>static int pass = 0; int i, check; i = check = 0; </code></pre> <p>inside the while loop in main() and </p> <pre><code>if(!check) { printf("pass #%d\n",pass++); while(val[i] != '\0') { printf("val[%d]: %.2f\n",i,val[i]); ++i; } } </code></pre> <p>at the end of the while loop, just after the switch statement. I also put <code>check = 1;</code> in the case for <code>'\n'</code>.</p> <p>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</p> <pre><code>double pop(void) { if (sp > 0) return val[--sp]; else { printf("error: stack empty\n"); return 0.0; } } </code></pre> <p>you'd have something like</p> <pre><code>double pop(void) { if (sp > 0) { double temp = val[--sp]; val[sp] = '\0'; return temp; } else { printf("error: stack empty\n"); return 0.0; } } </code></pre> <p>I also re-wrote the push function to ensure that values are always pushed to the end of the val array. So instead of</p> <pre><code>void push(double f) { if ( sp < MAXVAL) val[sp++] = f; else printf("error: stack full. can't push %g\n", f); } </code></pre> <p>you'd have</p> <pre><code>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); } </code></pre> <p>Even with these changes, I still had to re-write</p> <pre><code>case '\n': printf("\t%.8g\n", pop()); break; </code></pre> <p>to retrieve the value at the top of the stack without popping it, which required replacing the <code>printf</code> statement with a simple function like</p> <pre><code>void print_top(void) { int i = 0; while( val[i] != '\0' ) ++i; --i; printf("\t%.8g\n",val[i]); } </code></pre> <p>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:</p> <pre><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]); } </code></pre> <p>Note that I had to move most of my <code>#define</code> statements and prototype declarations to the beginning in order to accommodate for the debugging <code>printf</code>statement at the end of <code>main()</code>.</p> <p>*Edited out some of my audacious claims :P</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload