RPN calculator in C

Question

I had to write a RPN calculator in C as one of my homework problems, but if someone could critique my code and suggest any improvements, that would be fantastic! I haven't added any overflow errors or input errors, but I will add that eventually.

My code takes operands and operators from the command line (e.g., 3 4 - would return -1), and sends it to the decode function which uses the pop and push functions.

#include <stdio.h>
#include <stdlib.h>

void push(float stack[], float value, int *currStack)
{
    int i = *currStack;

    while (i != 0)
    {
        stack[i] = stack[i-1];
        i--;
    }

    stack[0] = value;
    *currStack += 1;
}

void pop(float stack[], char operation, int *currStack)
{
    int i;

    switch (operation)
    {
        case '+':
            stack[0] = stack[1] + stack[0];
            break;
        case '-':
            stack[0] = stack[1] - stack[0];
            break;
        case '*':
            stack[0] = stack[1] * stack[0];
            break;
        case '/':
            stack[0] = stack[1] / stack[0];
            break;
        default:
            printf("Invalid character.");
            break;
    }

    for (i=1;i<*currStack;i++)
    {
        float temp = stack[i];
        stack[i] = stack[i+1];
        stack[i+1] = temp;
    }

    *currStack -= 1;
}

int decode(char **instring, float *outval, int size)
{
    int i=0, currStack=0;
    float stack[size/2];

    for (i=1;i<size;i++)
    {           
        if (atof(instring[i]))
            push(stack, atof(instring[i]), &currStack);
        else
            pop(stack, *instring[i], &currStack);

        *outval = stack[0];
    }
}

int main(int argc, char *argv[])
{
    float result;
    decode(argv, &result, argc);

    printf("The answer is: %.3f\n", result);

    return 0;
}

Answer 1

for (i=1;i<*currStack;i++)
{
    float temp = stack[i];
    stack[i] = stack[i+1];
    stack[i+1] = temp;
}

This is more complicated than it needs to be.

float temp = stack[1];
for ( i = 1; i < *currStack; i++ )
{
    stack[i] = stack[i+1];
}
stack[*currStack] = temp;

This version has the exact same effect but does *currStack + 1 assignments where your original does *currStack * 3 - 3 assignments (although that may drop to *currStack * 2 - 2 assignments with good register management by the compiler).

We can do even better since we don't care about the value that is at stack[1] before we start.

for ( i = 1; i < *currStack; i++ )
{
    stack[i] = stack[i+1];
}

The for loop is sufficient. We don't need to muck around with temp at all. It's just junk data at this point.

Note: I'm not disputing vnp's point that the copy is unnecessary. I'm just saying that if you do do the copy, you don't actually have to copy the stack[1] value. And you certainly don't have to copy stack[1] once per element in the stack.

    default:
        printf("Invalid character.");
        break;
}

You don't actually need the break; there. It's all right to let it fall out of the default case on its own. It won't hurt anything, but I think it's more readable to set off default slightly by having it not break.

int decode(char **instring, float *outval, int size)

You say that decode is supposed to return an int but you never return anything. You could declare this of type void.

void decode(char **instring, float *outval, int size)

Then no one would expect it to return anything.

float stack[size/2];

for (i=1;i<size;i++)

You should probably comment why this works. Note that it's only because argc is one greater than the number of arguments that it does. This shows up implicitly in the way that you start with i=1 but could be clearer. As a general rule, any time you do something clever, you should comment to explain it. Otherwise, you have to be clever again to read the code.

for (i=1;i<size;i++)
{           
    if (atof(instring[i]))
        push(stack, atof(instring[i]), &currStack);
    else
        pop(stack, *instring[i], &currStack);

    *outval = stack[0];
}

You assign a value to *outval on every iteration of the loop but only use it once. You could do this outside the loop with the same ultimate effect.

for ( i = 1; i < size; ++i ) {
    double temp;
    if ( temp = atof(instring[i]) ) {
        push(stack, temp, &currStack);
    } else {
        pop(stack, *instring[i], &currStack);
    }
}

*outval = stack[0];

You also don't need to calculate atof(instring[i]) twice. Save it the first time.

I added curly braces around the statements in the if/else. The single statement version is susceptible to a class of typo bugs that is rather hard to diagnose.

There is an argument that ++i is faster than i++. It's not a big difference and a good compiler should be able to optimize this out, but it doesn't hurt anything to use the prefix notation.

Your code doesn't allow for values of 0.0 and will display "Invalid character" in that case. Yet that's a valid value. Another possibility would be

    if ( temp = atof(instring[i]) || ! strcmp(instring[i], "0.0") ) {

which would allow for 0.0, although it only supports one format. An alternative would be an is_zero function which could do a more exhaustive check.

The string manipulation to check for a number is more expensive (in terms of time) than checking for an operator. Checking for an operator only requires checking two characters to establish that it is an operator.

if ( ! instring[i][1] && is_operator(in_string[i][0] ) {
    pop(stack, *instring[i], &currStack);
} else if ( temp = atof(instring[i]) || ! strcmp(instring[i], "0.0") ) {
    push(stack, temp, &currStack);
} else {
    printf("Invalid argument:  [%s].", in_string[i]);
}

Then you just need an is_operator function:

int is_operator(char c) {
    switch (c) {
        case '+':
        case '-':
        case '*':
        case '/':
            return 1;
        default:
            return 0;
    }
}

The atof statement returns a double, but you are only using float variables. It would be better to make stack, outval, etc. hold double values rather than just float values. That would save the implicit conversions as well. Note that %lf in printf expects a double as well.

Answer 2

First, you have a top of stack at 0. This is very unconventional, and results in a lot of unnecessary data moves. Having a top of stack at currStack would make code much simpler. For example, push becomes just

*currStack++ = value;

and pop

case '+':
    currStack[-2] += currStack[-1];
    --currStack;
    break;

etc.

Second, pop means just that, pop a value from the stack. Your function performs an arithmetic operation and should be renamed accordingly, apply_operation perhaps.

Finally, I recommend to change a decode signature to float decode(char **, int). Returning results via size effect makes the code harder to reason about, and there must be a serious reason for such decision. As much as possible try to utilize return values.

Answer 3

Use of float

You should nearly almost use double instead of float. That advice applies here too. For example, the C library math functions all work with doubles; that includes atof(), which returns a double that you degraded into a float.

Compiler warning

These kinds of warnings almost always indicate a logic bug. Indeed, decode() never returns anything, even though it was supposed to return an int.

$ clang -Wall -o rpn rpn.c
rpn.c:65:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
1 warning generated.

Bug

You fail to handle 0 operands:

$ ./rpn 1 3 0 '*' +
Invalid character.The answer is: 0.000

The expected answer is 1.000. I got it to print 0.000, but the output is actually arbitrary, since this triggers a stack underflow.

Implementation

Your function signatures are weird. For example, in

void push(float stack[], float value, int *currStack)

… I would have expected stack and currStack to be placed together, since the two parameters together conceptually constitute a stack. Better yet, you should just structure them together to form a simple data structure:

typedef struct {
    double *data;
    size_t size;
} stack;

void push(stack *s, double datum);

As has been mentioned, your stack is laid out backwards in memory, and you are manipulating the wrong end of the array.

pop(), as you have written it, isn't the stack operation it should be. Rather, it performs an arithmetic operation (pop → pop → push), making it misnamed, and leaving you without a proper stack-popping function.

decode() would be better named rpn_calc(). Again, instring and size should be adjacent to each other. (In fact, this is a pretty strong convention in C: pass a pointer, followed by its associated array size).

The core of the calculator should look more like this:

void rpn_calc(stack *s, char *tokens[], size_t n_tokens) {
    for (int i = 0; i < n_tokens; i++) {
        const char *token = tokens[i];
        if (0 == strcmp(token, "+")) {
            push(s, pop(s) + pop(s));
        } else if (0 == strcmp(token, "-")) {
            double x = pop(s);
            push(s, pop(s) - x);
        } else if (0 == strcmp(token, "*")) {
            push(s, pop(s) * pop(s));
        } else if (0 == strcmp(token, "/")) {
            double x = pop(s);
            push(s, pop(s) / x);
        } else {
            push(s, atof(token));
        }
    }
}

To get the result, main() just needs to peek at the top of the stack afterwards.

Answer 4

What happens if I run your program like this?

rpn 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

I guess it crashes, or it might do anything else, since it invokes undefined behavior.

This is why you should not use tricks like the size/2 array size and check each array access whether the index is valid, i.e. 0 <= index <= arraylength. Since a C program cannot ask for the length of an arbitrary array, you have to pass the array as a tuple (start, size) or something equivalent.