The C Programming Language, 2nd Edition, by Kernighan and Ritchie
Exercise 5.10 on page 118
Write the program expr , which evaluates a reverse Polish expression from the command line, where each operator or operand is a separate argument. For example,
expr 2 3 4 + *
evaluates 2 X (3 + 4).
Solution by Lars Wirzenius
Note: Lars uses EXIT_FAILURE on error. As far as I can tell, this is the only
thing which makes this a Category 1, rather than Category 0, solution.
/* * Solution to exercise 5-10 in K&R2: * * Write the program expr, which evaluates a reverse Polish expression * from the command line, where each operator or operand is a separate * argument. For example, * * expr 2 3 4 + * * * evaluates 2*(3+4). * * This is very similar to the program in 4.3 (and should ideally have been * a modification of that). * * Feel free to modify and copy freely. * * Lars Wirzenius <liw@iki.fi> */ #include <ctype.h> #include <stdio.h> #include <stdlib.h> #define STACK_SIZE 1024 double stack[STACK_SIZE]; int stack_height = 0; void panic(const char *msg) { fprintf(stderr, "%s\n", msg); exit(EXIT_FAILURE); } void push(double value) { if (stack_height == STACK_SIZE) panic("stack is too high!"); stack[stack_height] = value; ++stack_height; } double pop(void) { if (stack_height == 0) panic("stack is empty!"); return stack[--stack_height]; } int main(int argc, char **argv) { int i; double value; for (i = 1; i < argc; ++i) { switch (argv[i][0]) { case '\0': panic("empty command line argument"); break; case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9': push(atof(argv[i])); break; case '+': push(pop() + pop()); break; case '-': value = pop(); push(pop() - value); break; case '*': push(pop() * pop()); break; case '/': value = pop(); push(pop() / value); break; default: panic("unknown operator"); break; } } printf("%g\n", pop()); return 0; }
Solution by Alex Hoang (Category 0)
/* Allows for leading plus/minus as well as decimal numbers */ #include <stdio.h> #include <stdlib.h> #include <math.h> #include <string.h> #define NUMBER 0 void push(double f); double pop(void); main(int argc, char *argv[]) { int type; int c; double op1, op2, latest; while (--argc > 0) { *++argv; if (!isdigit(c = **argv) && strlen(*argv) == 1) type = c; else type = NUMBER; switch (type) { case NUMBER: push(atof(*argv)); 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: zero divisor\n"); break; case '^': op2 = pop(); op1 = pop(); if (op1 == 0.0 && op2 <= 0) printf("if x = 0.0, y must be greater than 0\n"); else push(pow(op1, op2)); break; case 'e': push(exp(pop())); break; case '~': push(sin(pop())); break; default: printf("error: unknown command: %c\n", type); break; } } latest = pop(); printf("\t%.8g\n", latest); return 0; } #define MAXVAL 100 int sp = 0; double val[MAXVAL]; /* maximum depth of val stack */ /* next free stack position */ /* 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; } }
Solution by menonsahab
(Note for Menonsahab and readers: The reason that * is causing issues is that it is a shell wildcard. You are calling the program from your shell and the argument is passing to the shell first, which expands it into a list of all files in the current folder. If you use the escape sequence \* instead of * as an argument while calling your c program, you should get the expected result.). However, if you escape the asterisk and you are still having problems, it could be that you are using MinGW's version of gcc. See anonymous' solution to that problem.
#include <stdio.h> #include <stdlib.h> #include <ctype.h> #define MAXVAL 100 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 main(int argc, char *argv[]) { int i, c, op2; char *p; for(i = 1; i < argc; i++) { p = argv[i]; printf("argv[%d] = %s\n", i, argv[i]); while(*p && isdigit(*p)) p++; printf("*p = %d, %c\n", *p, *p); switch(*p) { case '\0': push(atoi(argv[i])); break; case '+': push(pop() + pop()); break; case '-': op2 = pop(); push(pop() - op2); break; case 'x': push(pop() * pop()); break; case '/': op2 = pop(); if(op2 != 0.0) push(pop() / op2); else printf("error: zero divisor\n"); break; } } printf("Final result = %lf\n", pop()); return 0; } /* I noticed that the program was giving weird results when I was using the multiplication symbol '*' as a command line input. I couldn't figure out why that was happening so now I'm just using the 'x' symbol to denote multiplication. I even ran the other two solutions on this page but to no avail. */ /* On running: expr 2 3 4 + x the output is: Final result = 14.000000 */
Solution by i9383
#include <stdio.h> #include <ctype.h> #include <stdlib.h> #define MAXVAL 100 main(int argc, char *argv[]) { double d[MAXVAL]; double *pd = d; while (--argc) { if (isdigit(**++argv)) *pd++ = atof(*argv); else if (*argv[0] == '-') { pd -= 2; *pd = *pd - *(pd+1); ++pd; } else if (*argv[0] == '/') { pd -= 2; *pd = *pd / *(pd+1); ++pd; } else if (*argv[0] == '*') { pd -= 2; *pd = *pd * *(pd+1); ++pd; } else if (*argv[0] == '+') { pd -= 2; *pd = *pd + *(pd+1); ++pd; } else argc = 1; } printf("%f\n", *--pd); return 0; }
Solution by anonymous
I took the reverse Polish calculator program from pages 76-79 and adapted it to use command line arguments instead of relying on getch() and ungetch(). I originally had the program from exercise 4.10 working, but I figured someone could add that functionality back since I kept this solution similar to the book's version of the calculator. Plus, it is 150 lines shorter.
During the conversion I ran into an annoying issue when an asterisk (*) was given as a command line argument in Windows. It turns out that the MinGW version of gcc adds in globbing for command line arguments by default and it cannot be escaped. This is because a program compiled by it will take an asterisk and expand it inside of the program. Fortunately, this annoying documentation-lacking feature is easily disabled by setting _CRT_glob to 0. Afterwards, everything worked as expected.
#include <stdio.h> #include <stdlib.h> // for atof() #include <ctype.h> // for isdigit() /* Exercise 5-10. Write the program expr, which evaluates a reverse Polish expression from the command line, where each operator or operand is a separate argument. For example, expr 2 3 4 + * evaluates 2 x (3 + 4). */ extern int _CRT_glob = 0; // disables MinGW globbing that is added to this program. Source: https://willus.org/mingw/_globbing.shtml #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 MAXLINE 1000 // buffer size for line 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 int getop(char s[]); void push(double f); double pop(void); // reverse Polish calculator int main(int argc, char *argv[]) { int type, c, i = 0; double op2; char s[MAXOP]; if (argc < 2) // if no arguments were given, print usage and exit { printf("Usage: expr <reverse Polish expression>\n"); return -1; } while (--argc > 0) // while there are arguments left, add them to the line char array { argv++; // This prevents the first argument from being processed and moves to next argument on each iteration while ((c = *(*argv)++)) // gets each character in the argument until it reaches '\0' line[i++] = c; line[i++] = ' '; // space delimit the arguments for the getop function } line[i++] = '\n'; // since the switch below expects a newline character to print the data, add it at the end line[i] = '\0'; // then terminate the string 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 '-': 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 '\n': printf("%.8g\n", pop()); // print the final result break; default: printf("error: unknown command %s\n", s); break; } } return 0; } // 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 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. Update the pointer to point to the item below it 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 = 0, c; if (line[linep] == '\0') // if at end of line return EOF to terminate the loop in main return EOF; 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 (!isdigit(c) && c != '.') return c; // not a number. Probably an operator, so return it. if (isdigit(c)) // collect integer(s), if any, after first digit 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 one return NUMBER; }
