The C Programming Language, 2nd Edition, by Kernighan and Ritchie
Exercise 4.10 on page 79
An alternate organization uses getline to read an entire input line; this makes getch and ungetch unnecessary. Revise the calculator to use this approach.
Solution by Franz Fritsche
/* K&R Exercise 4-10 */ /* Franz Fritsche */ #include <stdio.h> #include <stdlib.h> #define MAXOP 100 /* max size of operand or operator */ #define NUMBER '0' /* signal that a number was found */ #define MAXLINE 1000 int getop(char []); void push(double); double pop(void); int getline(char [], int); char line[MAXLINE]; int line_i; /* reverse Polish calculator */ int main(void) { int type; double op2; char s[MAXOP]; while (getline(line, MAXLINE) != 0) { line_i = 0; while ((type = getop(s)) != '\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': printf("\t%.8g\n", pop()); break; default: printf("error: unknown command \'%s\'\n", s); break; } } } 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; } /* getline: get line into s, return length */ int getline(char s[], int lim) { int c, i; i = 0; while (--lim > 0 && (c = getchar()) != EOF && c != '\n') s[i++] = c; if (c == '\n') s[i++] = c; s[i] = '\0'; return i; } #include <ctype.h> /* getop: get next character or numeric operand */ int getop(char s[]) { int i, c; while ((s[0] = c = line[line_i++]) == ' ' || 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 = line[line_i++])) ; if (c == '.') /* collect fraction part */ while (isdigit(s[++i] = c = line[line_i++])) ; s[i] = '\0'; line_i--; return NUMBER; }
Solution by Jesus Alvarez (Category 0)
#include <stdio.h> #include <stdlib.h> #include <math.h> #include <ctype.h> #define MAXOP 100 /* Max size of operand or operator. */ #define NUMBER '0' /* Signal that a number was found. */ #define VARIABLE '1' #define VARMAX 27 #define BUFSIZE 1000 int is_first_input = 0; /* Prevents the solution from being printed on first input */ double var_array[VARMAX]; /* Contains user defined variables. */ int getop(char []); void push(double); double pop(void); double top(void); int clear(void); int swap(void); int elem(void); int dup(void); void sprnt(void); void result(void); void set_solution(void); void print_help(void); int mygetline(char [], int); int main() { int type; int i, j; int op3; double topd; double op2; char ic[MAXOP]; /* Input Char */ char tmp[MAXOP]; for (i = 0; i < VARMAX; i++) { var_array[i] = 0; } print_help(); while ((type = getop(ic)) != EOF) { op3 = elem(); if (op3 == 0) { /* Only one input completed. */ is_first_input = 1; } else if (op3 > 1) { is_first_input = 0; } i = j = 0; switch (type) { case NUMBER: push(atof(ic)); break; case VARIABLE: for (i = 2; ic[i] != '\0'; i++){ tmp[j++] = ic[i]; tmp[j] = '\0'; } var_array[ic[0] - 'A'] = atof(tmp); 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: Divide by zero.\n"); } break; case '%': op3 = (int) pop(); push((int) pop() % op3); break; case 'c': if (clear()) { printf("Stack Cleared.\n"); } break; case 'p': if ((topd = top()) != 0) { printf("Top stack element: %g", topd); printf(" of %d elements.\n", elem()); } break; case 's': if (swap()) { printf("Swap successful.\n"); } break; case 'd': if (dup()) { printf("Duplication is successful.\n"); } else { printf("Error: Stack empty.\n"); } break; case 'r': sprnt(); break; case 'o': if (elem() < 2) { printf("Error: pow requires at least two "); printf("items on the stack.\n"); break; } op2 = pop(); push(pow(op2, pop())); break; case 'i': set_solution(); push(sin(pop())); result(); break; case 'y': set_solution(); push(cos(pop())); break; case 't': set_solution(); push(tan(pop())); break; case 'x': set_solution(); push(exp(pop())); break; case 'q': set_solution(); push(sqrt(pop())); break; case 'f': set_solution(); push(floor(pop())); break; case 'l': set_solution(); push(ceil(pop())); break; case 'v': for (i = 0; i < VARMAX; i++) { if (i < VARMAX-1) { printf("%c: %10.10G\n", 'A' + i, var_array[i]); } else { printf("%c: %10.10G\n", '=', var_array[VARMAX]); } } break; case 'h': print_help(); break; case '\n': result(); break; default: if ((type >= 'A' && type <= 'Z') || type == '=') { if (type != '=') { push(var_array[type - 'A']); } else { push(var_array[VARMAX]); } } else { printf("Error: Unknown command \'%s\'\n", ic); } break; } } return 0; } #define MAXVAL 100 /* Maximum depth of val stack. */ int sp = 0; /* Next free stack position. */ double val[MAXVAL]; /* Value stack. */ void push(double f) { if (sp < MAXVAL) { val[sp++] = f; } else { printf("Error: Stack full, cannot push %g\n", f); } } double pop(void) { if (sp > 0) { return val[--sp]; } else { printf("Error: Stack empty.\n"); return 0.0; } } double top(void) { if (sp > 0) { return val[sp-1]; } else { printf("Error: Stack empty.\n"); return 0.0; } } int clear(void) { if (sp > 0) { while(val[--sp] != '\0'); sp = 0; return 1; } else { printf("Error: Stack empty.\n"); return 0; } } int swap(void) { double sbuf; if (sp > 0) { sbuf = val[sp-2]; val[sp-2] = val[sp-1]; val[sp-1] = sbuf; return 1; } else { printf("Error: Stack empty.\n"); return 0; } } int elem(void) { return sp; } int dup (void) { if (sp > 0) { sp++; val[sp] = val[sp-1]; return 1; } else { return 0; } } void sprnt(void) { int count = 0; while (count < sp) { printf("%d:%10.12g\n", count+1, val[count]); count++; } } void result(void) { if (sp == 1 && is_first_input != 1) { printf("Solution: %10.20g\n", val[0]); var_array[VARMAX] = val[0]; is_first_input = 0; clear(); } } /* * Opens result() for execution. * Primarily used with the math functions because they can be used with only * one stack item. For ex, if "1 i" is entered as the first input, this * function would allow for a result to be shown and the stack cleared. */ void set_solution(void) { if (elem() >= 1) { is_first_input = 0; } } int mygetline(char s[], int maxline) { int i = 0; char c; while ((c = getchar()) != EOF && c != '\n' && i < maxline) { s[i++] = c; } if (c == '\n') { s[i++] = c; } s[i++] = '\0'; return i; } char getopbuf[BUFSIZE]; /* A string buffer that holds the mygetline. */ int getopbufp = 0; /* Current position is the string buffer. */ int getopbuflen = 0; int getop(char s[]) { int i = 0, c; s[0] = '\0'; if (getopbuflen == 0 || getopbufp == getopbuflen-2) { getopbufp = 0; /* Get a new line of input from the user. */ getopbuflen = mygetline(getopbuf, BUFSIZE); } if (getopbuf[getopbufp] == '\n') { return '\n'; } /* Jump over spaces at the begining of the string. */ while (isspace(c = getopbuf[getopbufp++])); s[i++] = c; if (isalpha(c) && c >= 'A' && c <= 'Z') { /* Collect the variable. */ for (i = 1; getopbuf[getopbufp] != ' ' && getopbuf[getopbufp] != '\n'; s[i++] = getopbuf[getopbufp++]); s[i] = '\0'; if (i > 1) { /* A properly formed variable definition. */ return VARIABLE; } else { return c; } } else if (!isdigit(c) && c != '.' && c != '-') { return c; /* Not a number. */ } if (c == '-') { if ((c = getopbuf[++getopbufp]) == ' ') { /* If the next char is space, then c is a operator. */ return c; } else if (isdigit(c)) { s[++i] = c; } } if (isdigit(c)) { /* Collect integer part. */ for ( ; isdigit(c = getopbuf[getopbufp]); i++, getopbufp++) { s[i] = c; } } if (c == '.') { /* Collect fraction part. */ while (isdigit(s[i++] = c = getopbuf[getopbufp++])); } s[i] = '\0'; return NUMBER; } void print_help(void) { printf("The Polish Calculator\n"); printf("-----------------------------------------------\n"); printf("-> Enter equations in the form: \"1 1 + 2 5 + *\"\n"); printf("-> Use \"A=1 B=2 C=3\" to store variables.\n"); printf("-> Use \"A B C * *\" to use stored variables.\n"); printf("-----------------------------------------------\n"); printf(">>> Command Help:\n"); printf(">>> c: Clear memory.\n"); printf(">>> p: Print last character.\n"); printf(">>> s: Swap last two characters.\n"); printf(">>> d: Duplicate the last input.\n"); printf(">>> r: Print the entire stack.\n"); printf(">>> v: Print variable list.\n"); printf(">>> o: pow(x,y), x^y, x > 0.\n"); printf(">>> i: sin(x), sine of x.\n"); printf(">>> y: cos(x), cosine of x.\n"); printf(">>> t: tan(x), tangent of x.\n"); printf(">>> x: exp(x), e^x, exponential function.\n"); printf(">>> q: sqrt(x), x >= 0, square of x.\n"); printf(">>> f: floor(x), largest integer not greater than x.\n"); printf(">>> l: ceil(x), smallest integer not less than x.\n"); printf(">>> =: Access the last successful solution.\n"); printf(">>> h: Print this help text.\n"); }
Solution by anonymous
I struggled to write this program on my own, so I used code from http://www.learntosolveit.com/cprogramming/Ex_4.10_calculator_getline.html as a guide. I originally attempted a much more complex method of doing this, but I discovered there was a much simpler way of replacing getch/ungetch with getline. Below are the major changes from my exercise 4.6 program and this one:
int getop(char s[]) { … // previous i = 0; while ((s[0] = c = getch()) == ' ' || c == '\t') // skip white space // new i = 0; if (line[linep] == '\0') // if at end of line or is first time reaching this since array is initialized to '\0' { if (getline(line, MAXLINE) == 0) // if == 0, reached EOF. So return it return EOF; else // otherwise, reset line position to zero to process new line linep = 0; } while ((s[0] = c = line[linep++]) == ' ' || c == '\t') // skip white space
For the rest of the getop function, all getch() was replaced with line[linep++] and all ungetch(c) was replaced with linep--. That is basically it. The rest of the minor changes were replacing buf with line, bufp with linep, BUFSIZE with LINESIZE, removing getch, ungetch, and adding getline. Here is the whole program:
#include <stdio.h> #include <stdlib.h> // for atof() #include <ctype.h> #include <math.h> #include <string.h> // for strlen() /* Exercise 4-10. An alternate organization uses getline to read an entire input line; this makes getch and ungetch unnecessary. Revise the calculator to use this approach. */ #define MAXOP 100 // max size of operand or operator #define NUMBER '0' // signal that a number was found #define SETVARIABLE 's' // signal that a variable is being assigned #define GETVARIABLE 'g' // signal that a variable is being retrieved #define ERRORSIGNAL ' ' // signal that an error occurred in getop #define MAXVAL 100 // maximum depth of val stack #define MAXLINE 1000 // buffer size for line #define NUMVARS 27 // number of variables supported (a-z) plus the variable L for last printed enum boolean {FALSE, TRUE}; int sp = 0; // next free stack position double val[MAXVAL]; // value stack char line[MAXLINE] = {'\0'}; // buffer for getline. Set all values to zero from the start for logic below int linep = 0; // current position in line buffer double varVals[NUMVARS] = {0.0}; // array to store the double values for variables. Supports variables a through z (lower case). Initial value is 0 int getop(char s[]); void push(double f); double pop(void); void printTop(void); void duplicateTop(void); void swapTopTwo(void); int getline(char s[], int lim); // 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]; char skipNextNewline = FALSE; 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 SETVARIABLE: if (strlen(s) > 2 && s[1] == '=') { int v = s[0]; // stores variable int i = 1; // start at 1 since while loop needed ++i for a few reasons while (s[++i] != '\0') // this removes the variable name= part of s e.g. if s == "a=123.45" after loop s == "123.45" s[i - 2] = s[i]; // shifts chars two to the left by 2 s[i - 2] = '\0'; // since '\0' isn't copied, terminate string manually varVals[v - 'a'] = atof(s); // convert string to double and store it in array } else printf("error: set variable length too small or incorrectly formatted (%s)\n", s); skipNextNewline = TRUE; break; case GETVARIABLE: push(varVals[s[0] - 'a']); // convert the variable name to stored value 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 '?': printTop(); skipNextNewline = TRUE; break; case '#': duplicateTop(); skipNextNewline = TRUE; break; case '~': swapTopTwo(); skipNextNewline = TRUE; break; case '!': // sets next free stack position to zero (meaning the value stack is empty). // all of the original values are still there, but they will no longer be accessible by the current functions and they will be overwritten when new elements are stored sp = 0; skipNextNewline = TRUE; break; case '$': push(sin(pop())); skipNextNewline = TRUE; break; case '@': push(exp(pop())); skipNextNewline = TRUE; break; case '^': op2 = pop(); push(pow(pop(), op2)); // pop last two digits in the correct order to raise a number to the given power skipNextNewline = TRUE; break; case '&': push(sqrt(pop())); skipNextNewline = TRUE; break; case ',': push(fabs(pop())); skipNextNewline = TRUE; break; case 'L': push(varVals[NUMVARS - 1]); // adds the last printed value to the stop of the stack break; case '\n': if (skipNextNewline) skipNextNewline = FALSE; else { varVals[NUMVARS - 1] = pop(); // updates last printed value printf("\t%.8g\n", varVals[NUMVARS - 1]); // 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; char setVar = FALSE; i = 0; if (line[linep] == '\0') // if at end of line or is first time reaching this since array is initialized to '\0' { if (getline(line, MAXLINE) == 0) // if == 0, reached EOF. So return it return EOF; else // otherwise, reset line position to zero to process new line linep = 0; } while ((s[0] = c = line[linep++]) == ' ' || 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 (c >= 'a' && c <= 'z') { if ((s[++i] = c = line[linep++]) == '=') // get next char and check if it was an equal symbol. Update s in case of error setVar = TRUE; else if (c == ' ' || c == '\t' || c == '\n') { linep--; // this moves the line position back to process the whitespace later return GETVARIABLE; } if (!(setVar && ((s[++i] = c = line[linep++]) == '-' || isdigit(c)))) return ERRORSIGNAL; // triggers an error and will display what is in s } 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; if (c == '-' || isdigit(c)) // collect integer(s), if any, after first digit found or after minus symbol found while (isdigit(s[++i] = c = line[linep++])) ; if (c == '.') // collect fraction part if period is found while (isdigit(s[++i] = c = line[linep++])) ; s[i] = '\0'; // terminate string after digits were captured if (c != EOF) linep--; // since we read too far, move the line position back back one if (i == 1 && s[0] == '-') // if s[0] == '-' && s[1] == '\0', return minus operator return '-'; if (setVar) return SETVARIABLE; else if (c >= 'a' && c <= 'z') return ERRORSIGNAL; // if last char is a variable and setVar wasn't set to TRUE, throw error return NUMBER; } // prints the top element in the value stack void printTop(void) { if (sp > 0) printf("\t%.8g\n", val[sp - 1]); else printf("error: stack empty\n"); } void duplicateTop(void) { if (sp < MAXVAL) // only need to see if there is space for one more push(val[sp - 1]); // duplicates top item else printf("error: stack full, can't duplicate top element\n"); } void swapTopTwo(void) { // if sp == 2, there are at least two elements stored if (sp > 1) { // <third> <second> <first> double first = pop(); // <third> <second> double second = pop(); // <third> push(first); // <third> <first> push(second); // <third> <first> <second> } else printf("error: can't swap top two, not enough elements\n"); } // get line into s, return length int getline(char s[], int lim) { int c, i; i = 0; while (--lim > 0 && (c=getchar()) != EOF && c != '\n') s[i++] = c; if (c == '\n') s[i++] = c; s[i] = '\0'; return i; }
