Basic Reverse Polish CL Parser

Question

K and R 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 * (3+4)

#include <stdio.h>
#include "expression_parser.h"

int parse_polish(int size, char *expression[])
{
    char *entry;
    int temp1, temp2;

    if (expression[1] && ((isdigit(*expression[1]) &&
        isdigit(*expression[2])))) {
        stack_init(&size, expression);
        expression++;
        for ( ; *expression; expression++) {
            if (isdigit(*(entry = *expression)))
                push(atoi(entry));
            else {
                switch (*entry) {
                    case '+':
                        push(pop() + pop());
                        break;
                    case '-':
                        temp1 = pop();
                        temp2 = pop();
                        push(temp1 - temp2);
                        break;
                    case '*':
                        push(pop() * pop());
                        break;
                    case '/':
                        temp1 = pop();
                        temp2 = pop();
                        if (!(temp2))
                            return -1;
                        else 
                            push(temp1 / temp2);
                        break;
                    default:
                        return -1;
                }
            }
        }
        return pop();
    } else 
          return -1;
}

Repository

Answer 1

• Your function is called parse_polish(), but it actually does much more: it evaluates the expression too!
• pop() takes no arguments, and push() takes just one argument, so I deduce that they must be operating on a global variable, which is bad practice.

• Your function returns -1 on error, but that could very well also be the result of a legitimate calculation. I recommend one of the following strategies:

  • Passing the calculation result as an out-parameter.
  • Requiring the caller to initialize the stack and pass it to your evaluator. The caller can then pop the result off the stack (which could be empty in case of an error).
  • Using floating-point calculations. Not only do you get floating-point division, but you also have the possibility of returning positive infinity, negative infinity, or NaN.
• Why do you test that *expression[1] and *expression[2] are digits? What if the expression consists of a single token { "5" } — shouldn't the result be 5?
• Perhaps you want to allow negative integers as inputs too?