# K&R Exercise 5-10. reverse Polish calculator

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);
}

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.

• Why magic number 8 in printf("\t%.8g\n", pop());? Why do you think that is a good choice? Commented Sep 20, 2022 at 5:08

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

• The result with two 2-digit numbers - 15 10 *, would equal 150. Commented Sep 18, 2022 at 10:56
• Those "global" variables won't impact linking since they're marked static, surely? However, push and pop may. Commented Sep 18, 2022 at 11:12
• I will try to minimize the use of global variables. Although I imagine that in some cases it is possible that they can be used, right? Commented Sep 21, 2022 at 21:57
• Yes they can be used, but there are ways to minimize it. The comment about static variables is a good one since static variables are only global to the file they are in. If you had a stack.h and a stack.c and the stack was a static variable in stack.c that would be a good implementation that I would not have commented on. All you really need are the push and pop functions declared in stack.h. Commented Sep 22, 2022 at 2:33
• Disagree with "The comments on the include files are unnecessary." as the include file can often be the only source code the user has access. That is where info meant for the public is best seen. Consider a user may only have access to a .h file and a pre-compiled .lib. Commented Sep 23, 2022 at 16:49

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.

• Speaking of which, comparison with floating point zero is better done differently. The generic form of foo == bar is rather abs(foo-bar) < eps for a sufficiently small eps, something along 1e-6 or 1e-16. Commented Sep 17, 2022 at 23:55
• @OlegLobachev no that is not the generic form. That is a bad form that will surely fail for small numbers. Commented Sep 18, 2022 at 12:15
• Okay, then floating-point-gui.de/errors/comparison Commented Sep 18, 2022 at 12:53
• "dividing by zero is not an error in IEEE 754 floating-point arithmetic" is true yet C does not require IEEE 754 floating-point arithmetic compliance. Highly portable would not not rely on IEEE 754 floating-point arithmetic spec's. OP's approach is reasonable. "forbidding that special case, you've put extra effort into making the program less useful." is an overstatement. It depends on OP's portability goals. Commented Sep 20, 2022 at 5:04

## 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;
}
}

• could it be a good idea to have a header file for prototypes with comments, explaining what that particular project would do? which could be extracted from the header file; for example when using Doxygen to document the code. Since there could be a lot of content in the *.c file Commented Sep 25, 2022 at 0:37
• It's definitely useful when you have multiple .c files to have a header file for exports. And there it makes a lot of sense to comment the "interface". I think there's less of a reason to do it with a single .c file. ... One situation that might call for that is if you have a lot of functions that could be reused elsewhere. Then you could make a header for it to add separate documentation for the functions. But there, you'd probably want to break out main() into its own .c file so other programs could reuse the functions by linking to the .o file. Commented Sep 25, 2022 at 12:34

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

• Now that you mention it, it's true, I'll be more careful. & consider it from now on. Yesterday I noticed it. Thank you. Commented Sep 21, 2022 at 21:53
• This is a notorious trap in the C Standard Library. Pretty much everyone has fallen into it at one time or another, so don't feel bad about being tripped up here! Commented Sep 22, 2022 at 5:58