K&R Exercise 5-10. reverse Polish calculator

Question

I have been learning C with K&R Book 2nd Ed. And well, so far I've gotten to chapter five, and I've been dealing with pointers/command line arguments.

I came up with the following solution for the exercise (Chapter 5, Ex-5.10):

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).

I would like to know how to improve it.:

/*-
 *  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).
 *
 *  By jr.chavez
 *
 *  NOTE:
 *      To receive the expected output with the following example:
 *          2 3 4 + *
 *      '\' must be used (e.g., 2 3 4 + \* instead of *)
 */
#include <stdio.h>
#include <stdlib.h> /* for atof() */
#include <string.h> /* for strlen() */
#include <ctype.h>  /* for isdigit() */

#define NUMBER  '0'     /* signal that a number was found */
#define MAXVAL  100     /* next free stack position */

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

void push(double);
double pop(void);

/* reverse Polish calculator */
int
main(int argc, char *argv[])
{
    int type, c;
    double op2;
    
    while (--argc > 0) {
        {
            char *p = *++argv;
            type = (!isdigit(c = *p) && strlen(p) == 1) ? c : 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
                fprintf(stderr, "error: zero divisor\n");
            break;
        default:
            fprintf(stderr, "error: unkown command %s\n", *argv);
            argc = 1;
            break;
        }
    }
    printf("\t%.8g\n", pop()); 
    return 0;
}


/* push: push f onto value stack */
void
push(double f)
{
    if (sp < MAXVAL)
        val[sp++] = f;
    else
        fprintf(stderr, "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 {
        fprintf(stderr, "error: empty stack\n");
        return 0.0;
    }
}

input:

./bin/main 2 3 4 + \*

output:

14

Note: I decided not to add options like sin, cos, exp, and pow.

Answer 1

General Observations

Nice comment block at the top. The comments on the include files are unnecessary.

What happens with 2 digit numbers? Example 15 10 *?

Avoid Global Variables

It is very difficult to read, write, debug and maintain programs that use global variables. Global variables can be modified by any function within the program and therefore require each function to be examined before making changes in the code. In C and C++ global variables impact the namespace and they can cause linking errors if they are defined in multiple files. The answers in this stackoverflow question provide a fuller explanation.

Code Organization

Function prototypes are very useful in large programs that contain multiple source files, and that in case they will be in header files. In a single file program like this it is better to put the main() function at the bottom of the file and all the functions that get used in the proper order above main(). Keep in mind that every line of code written is another line of code where a bug can crawl into the code.

Answer 2

Contrary to popular belief, dividing by zero is not an error in IEEE 754 floating-point arithmetic. By forbidding that special case, you've put extra effort into making the program less useful.

Answer 3

Comment the prototypes, not the functions

I like the overall code organization with main at the top, but I think it's nicer to have brief comments next to the function prototypes rather than near the functions themselves. This lets the prototype section double as a glossary of all the functions. Also, if the function accesses (or modifies!) a global variable, that's important enough to go in the comment.

#define MAXVAL  100     /* next free stack position */

It's not a "next free stack position", but a MAX, but not a "max" because it's one past the maximum array index of 99. Also, it's not the max (or limit) of "val" but of sp. I would change the name to something like STACKSIZE and then maybe calculate a const int max_index = STACKSIZE - 1. Then, with a name like max_index or max_stack_index it almost doesn't need a comment anymore.

Shorter functions

Your functions aren't super long, but I'd recommend factoring them even further. This makes for more functions, but it makes more opportunity for abstracting behavior. It can also avoid the need for adding paragraphs of code within functions and having to comment each paragraph. Instead each paragraph gets factored out to its own function with the function's descriptive name serving the purpose that the comment used to do.

You don't have any commented paragraphs, but the rewrite below ought to show what I'm talking about. It can help subordinate unnecessary detail when reading a function in isolation.

Too tricksy/not tricksy enough?

Regarding this block of code:

    {
        char *p = *++argv;
        type = (!isdigit(c = *p) && strlen(p) == 1) ? c : NUMBER;
    }

If you're already ok with side effects buried in the middle of expressions, then you can make this more concise by moving the assignment to p:

    {
        char *p;
        type = (!isdigit(c = *(p = *++argv)) && strlen(p) == 1) ? c : NUMBER;
    }

Then you can move the declaration char *p to the top level scope and eliminate the type variable altogether, putting the whole expression into the switch condition:

    char *p;
    ...
    switch( (!isdigit(c = *(p = *++argv)) && strlen(p) == 1) ? c : NUMBER ){
    ...

Opinions will differ widely about writing code like this. Some people very much dislike burying side effects in the middle of expressions. I merely dislike doing it halfway where you don't get any savings in lines of code.

Proposed refactoring

I've moved all the code from main to a new function, using the comment to provide the name. Thus, it's trivial to look at main and see "what it does" (or at least, "what it says it does"); and it does this without needing a comment per se.

I've also moved the guts of the while loop to its own function eval and most of the cases have their bodies removed to their own named functions. I think this brings out the simple top level idea of the state machine that counts down until argc is 0.

Grouping all the prototypes together and in order provides a sort of index to the file, showing the order to expect the functions. Although this might become tedious to maintain in a larger program, I think it's a nice thing to do with a small program.

/*-
 *  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).
 *
 *  By jr.chavez
 *
 *  NOTE:
 *      To receive the expected output with the following example:
 *          2 3 4 + *
 *      '\' must be used (e.g., 2 3 4 + \* instead of *)
 */
#include <stdio.h>
#include <stdlib.h> /* for atof() */
#include <string.h> /* for strlen() */
#include <ctype.h>  /* for isdigit() */

#define NUMBER  '0'     /* signal that a number was found */
#define STACKSIZE  100     /* size of the val array */

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

int    reverse_polish_calculator( int argc, char *argv[] );
int    eval( int type, int argc, char *argv[] );
void   eval_number( char *arg );
void   eval_plus( void );
void   eval_times( void );
void   eval_minus( void );
void   eval_divide( void );
void   push(double); /* push f onto value stack (uses val, sp)*/
double pop(void);    /* pop and return top value from stack (uses val, sp)*/

int
main(int argc, char *argv[])
{
    return reverse_polish_calculator( argc, argv );
}

int
reverse_polish_calculator( int argc, char *argv[] )
{
    char *p;
    int c;
    
    while (--argc > 0) {
        argc = eval( (!isdigit(c = *(p = *++argv)) && strlen(p) == 1) ? c : NUMBER,
                 argc, argv);
    }
    printf("\t%.8g\n", pop()); 
    return 0;
}

int
eval( int type, int argc, char *argv[] )
{
    switch (type) {
    case NUMBER: eval_number( *argv ); break;
    case '+':    eval_plus();          break;
    case '*':    eval_times();         break;
    case '-':    eval_minus();         break;
    case '/':    eval_divide();        break;
    default:
        fprintf(stderr, "error: unkown command %s\n", *argv);
        argc = 1;
        break;
    }
    return argc;
}

void
eval_number( char *arg )
{
    push(atof(arg));
}

void
eval_plus( void )
{
    push(pop() + pop());
}

void
eval_times( void )
{
    push(pop() * pop());
}

void
eval_minus( void )
{
    double op2;
    op2 = pop();
    push(pop() - op2);
}

void
eval_divide( void )
{
    double op2;
    op2 = pop();
    if (op2 != 0.0)
        push(pop() /  op2);
    else
        fprintf(stderr, "error: zero divisor\n");
}


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


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

Answer 4

Be careful with <ctype.h> functions

Look at this code; do you see the bug?

    int c;

        char *p = *++argv;
        type = !isdigit(c = *p)

On systems where plain char is a signed type, this can pass a negative value to isdigit(). But the only allowable negative value allowed is EOF. We should be using unsigned char *p here.