The C Programming Language, 2nd Edition, by Kernighan and Ritchie
Exercise 4.03 on page 79
Given the basic framework, it's straightforward to extend the calculator. Add the modulus ( %
) operator and provisions for negative numbers.
Solution by Bob Wightman
In Bob's words:
"Here's my attempt
Adding the modulus is easily done by another case in main and using the fmod function. The standard library has been mentioned at this point so it should be valid to use this for type 0 compliance.
math.h should be added to the list of #includes for fmod."
#include <stdio.h> #include <stdlib.h> int main(void) { int type; double op2; char s[MAXOP]; int flag = TRUE; while((type = Getop(s)) != EOF) { switch(type) { /* other cases snipped for brevity */ case '%': op2 = pop(); if(op2) push(fmod(pop(), op2)); else printf("\nError: Division by zero!"); break; } } return EXIT_SUCCESS; }
Bob goes on to say: "Deal with unary minus when retrieving tokens. This is based on the fact that a unary minus will have no intervening space between it and its operand."
/* Getop: get next operator or numeric operand. */ int Getop(char s[]) { #define PERIOD '.' int i = 0; int c; int next; /* Skip whitespace */ while((s[0] = c = getch()) == ' ' || c == '\t') ; s[1] = '\0'; /* Not a number but may contain a unary minus. */ if(!isdigit(c) && c != PERIOD && c != '-') return c; if(c == '-') { next = getch(); if(!isdigit(next) && next != PERIOD) { return c; } c = next; } else { c = getch(); } while(isdigit(s[++i] = c)) c = getch(); if(c == PERIOD) /* Collect fraction part. */ while(isdigit(s[++i] = c = getch())) ; s[i] = '\0'; if(c != EOF) unGetch(c); return NUMBER; }
Solution by Xggggg
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 '/': if ((op2 = pop()) != 0.0) push(pop() / op2); else printf("error: zero divisor\n"); break; case '%': if ((op2 = pop()) != 0.0) push(fmod(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; } int getop(char s[]) { int i = 0, c, k; while ((s[0] = c = getch()) == ' ' || c == '\t'); s[1] = '\0'; if (isdigit(c) || c == '.' || ((c == '-' || c == '+') && (isdigit(k = getchar()) || k == '.'))) { if (c == '-' || c == '+') s[++i] = c = k; 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); c = NUMBER; } if (c == '-' || c == '+') ungetch(k); return c; }
Solution by menonsahab
//I've added a viewstack() function that let's you see the values in the stack after every iteration. #include <stdio.h> #include <stdlib.h> #include <ctype.h> #include <math.h> #define MAXOP 100 #define NUMBER 0 #define MAXVAL 100 #define BUFSIZE 100 int getop(char *); void push(double); double pop(void); int getch(void); void ungetch(int); void viewstack(void); int bufp = 0; char buf[BUFSIZE]; int sp = 0; double val[MAXVAL]; void push(double f) { if(sp < MAXVAL) val[sp++] = f; else printf("error: stack full, can't push %g\n", f); } double pop(void) { if(sp > 0) return val[--sp]; else { printf("error: stack empty\n"); exit(1); //return 0.0; } } 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; } int getop(char *s) { int i, c, d; while((s[0] = c = getch()) == ' ' || c == '\t'); s[1] = '\0'; if(!isdigit(c) && c != '.' && c != '-') return c; if(c == '-') { d = getch(); if(d == ' ') return c; else ungetch(d); } i = 0; if(isdigit(c) || 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; } void viewstack(void) { int i; printf("\nstack:\n"); for(i = sp - 1; i >= 0; i--) printf("%lf\n", val[i]); } int main() { int type; double op2; char s[MAXOP]; while((type = getop(s)) != EOF) { //viewstack(); Use this function if you wish to see the stack after every iteration 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("error: division by zero\n"); break; case '\n': printf("\t%.8g\n", pop()); break; default: printf("error: unknown command %s\n", s); break; } } return 0; }
Solution by Luke Panayi
My take on minus compatibility. I'm uncertain if it's as clean as the alternatives or not, but it is an alternative.
#include <stdio.h> #include <stdlib.h> #include <ctype.h> #include <math.h> #define MAXOP 100 #define NUMBER '0' #define MAXVAL 100 #define BUFSIZE 100 int getop(char []); void push(double); double pop(void); int getch(void); void ungetch(int); int sp = 0; double val[MAXVAL]; void push(double f) { if (sp < MAXVAL) val[sp++] = f; else printf("error: stack full, can't push %g\n", f); } double pop(void) { if (sp > 0) return val[--sp]; else { printf("error: stack empty\n"); return 0.0; } } int getop(char s[]) { int i, c; while ((s[0] = c = getch()) == ' ' || c == '\t'); s[1] = '\0'; if (!isdigit(c) && c != '.' && c != '-') return c; i = 0; if (c == '-') { s[i] = c; if (!isdigit(c = getch())) { return '-'; } else s[++i] = c; } if (isdigit(c)) while (isdigit(s[++i] = c = getch())); if (c == '.') while (isdigit(s[++i] = c = getch())); s[i] = '\0'; printf("%s\n", s); if (c != EOF) ungetch(c); return NUMBER; } char buf[BUFSIZE]; int bufp = 0; 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; } int 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 '/': if (op2 != 0.0) { op2 = pop(); push(pop() / op2); } else printf("error: zero divisor\n"); break; case '%': op2 = pop(); if (op2 != 0.0) { push(fmod(pop(), op2)); } else printf("error: zero divisor\n"); break; case '\n': printf("\t%.8g\n", pop()); break; } } return 0; }
Solution by anonymous
Like most, I utilized fmod to get the modulus since the data type for both numbers are doubles and the modulo operator only supports ints. I choose to modify getop to store a '-' if first char found and, if any digits are found after it, to store them as well. I had to check to see if only '-' was added to s at the end of the function, but it's simple and required little modification from the original program.
I also added many comments explaining what the code from the book since it took me a while to understand it all. Furthermore, since my '%' case code is essentially the same as everyone else's, I will just highlight the getop differences.
// original: return c if it is not a digit or period if (!isdigit(c) && c != '.') return c; // mine: this prevents an immediate return if a - is found. Returns if not a digit, period, or minus symbol if (!isdigit(c) && c != '.' && c != '-') return c; // original: only continue if c is a digit (c at this point is the first digit or period found) if (isdigit(c)) while (isdigit(s[++i] = c = getch())) ; // mine: only continue if c is a digit or a minus symbol (c at this point is the first digit, period, or minus symbol found) if (c == '-' || isdigit(c)) while (isdigit(s[++i] = c = getch())) ; // original: return number signal after storing the last non-EOF char read in the getch buffer if (c != EOF) ungetch(c); return NUMBER; // mine: after the getch buffer is updated, check to see if the only char read was a - since i[0] == '-' and i == 1 which means i[1] == '\0' since it never reached any s[++i] = c parts of the code if (c != EOF) ungetch(c); if (i == 1 && s[0] == '-') return '-'; return NUMBER;
Here is the entire program
#include <stdio.h> #include <stdlib.h> // for atof() #include <ctype.h> #include <math.h> /* Exercise 4-3. Given the basic framework, it's straightforward to extend the calculator. Add the modulus (%) operator and provisions for negative numbers. */ #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 #define BUFSIZE 100 int sp = 0; // next free stack position double val[MAXVAL]; // value stack char buf[BUFSIZE]; // buffer for ungetch int bufp = 0; // next free position in buf int getop(char s[]); void push(double f); double pop(void); int getch(void); void ungetch(int c); // reverse Polish calculator // note: convert ((((-1 - 2) * (4 + -5)) / -3) % 5) * (-1 - -10) to -1 2 - 4 -5 + * -3 / 5 % -1 -10 - * for reverse Polish notation. -1 2 - 4 -5 + * -3 / 5 % -1 -10 - * == -9 int main() { int type; double op2; char s[MAXOP]; while ((type = getop(s)) != EOF) { switch (type) { case NUMBER: push(atof(s)); // convert the string to type double and push it on the stack break; case '+': push(pop() + pop()); // pop last two digits to sum them and push the result on the stack break; case '*': push(pop() * pop()); // pop last two digits to multiply them and push the result on the stack break; case '-': /* Because + and * are commutative operators, the order in which the popped operands are combined is irrelevant, but for - and / the left and right operands must be distinguished. In push(pop() - pop());, the order in which the two calls of pop are evaluated is not defined. To guarantee the right order, it is necessary to pop the first value into a temporary variable. Hence op2 = pop() in - and / but not in + and * */ op2 = pop(); push(pop() - op2); // pop last two digits to subtract them in the correct order and push the result on the stack break; case '/': op2 = pop(); if (op2 != 0.0) push(pop() / op2); // pop last two digits to divide them in the correct order and push the result on the stack else printf("error: zero divisor\n"); break; case '%': op2 = pop(); if (op2 != 0.0) push(fmod(pop(), op2)); // pop last two digits in the correct order to find the modulus and push the result on the stack else printf("error: zero divisor\n"); break; case '\n': printf("\t%.8g\n", pop()); // get the final result break; default: printf("error: unknown command %s\n", s); break; } } return 0; } // push: push f onto value stack void push(double f) { if (sp < MAXVAL) // if value stack still has space, add f 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) // if the next free stack position is greater than zero, return the highest level item from stack return val[--sp]; else { printf("error: stack empty\n"); return 0.0; } } // getop: get next operator or numeric operand int getop(char s[]) { int i, c; while ((s[0] = c = getch()) == ' ' || c == '\t') // skip white space ; s[1] = '\0'; // terminate string in case input is not a number (s is expected to be a string throughout program) if (!isdigit(c) && c != '.' && c != '-') return c; // not a number. Probably an operator, so return it. Minus operator is a special case and is handled right before return NUMBER; i = 0; if (c == '-' || isdigit(c)) // collect integer(s), if any, after first digit found or after minus symbol found while (isdigit(s[++i] = c = getch())) ; if (c == '.') // collect fraction part if period is found while (isdigit(s[++i] = c = getch())) ; s[i] = '\0'; // terminate string after digits were captured if (c != EOF) ungetch(c); // since we read to far, push the last read char back on the getch buffer. This buffer is read first before getting the next char from input if (i == 1 && s[0] == '-') // if s[0] == '-' && s[1] == '\0', return minus operator return '-'; return NUMBER; } // get a (possibly pushed back) character // checks to see if there are any chars in buffer. If there are, get those and return it. If not, call getchar() from stdio.h to get next char from input int getch(void) { return (bufp > 0) ? buf[--bufp] : getchar(); } // push character back on input // if bufp is less than BUFSIZE, there is room to store more chars to be read by getch next and it stores c and updates the index for it void ungetch(int c) { if (bufp >= BUFSIZE) printf("ungetch: too many characters\n"); else buf[bufp++] = c; }