RPN Calculator in C

For a C implementation, we usually have to do a bit more work and at a lower level of detail than in most modern languages. But C is so versatile that it is very easy to realise our RPN calculator in whatever of the possible ways we choose.

Here is an implementation that reads input lines in the main function and calls eval to parse and evaluate each expression. eval is recursive and processes the input string backwards. If a token is found to be a number, eval returns its value. If that token is an operator, eval calls itself to parse more of the string and eventually obtain the values of the two operands, then applies the operator on them and returns the computed value.

In main, the while loop reads a characer at a time and if it is not end of line, stores it and repeats the same again. Upon encountering end of line (the else part) we trim all but one trailing blanks and if the line is not empty, invoke eval. Throughout the program, we use a dynamically allocated (malloc, realloc) string pointed at by pb, in which we keep an input line, and use p as the ‘parser's reading head’ within it.

When main is about to invoke eval, it calls the pseudo-function setjmp. The latter returns immediately with a value of 0, but it also marks where the call was made, in order to make possible the program control to get back to the same point if necessary. In both main and eval a call of longjmp may take place. If that happens, the program behaves (almost) like setjmp has just returned but this time with a value of 1.

The setjmp/longjmp pair is the standard way to implement non-local control mechanisms in C, e.g. exception handling and backtracking. The way setjmp marks where it has been called is by filling-in the structure value (env) passed to it as an argument. A longjmp referring to the same value ensures jumping to the point after setjmp's returning. In this program, we call longjmp to signal a syntax error in the input expression, such as a missing or incorrect token (in eval) or extra non-blank characters (in main). Note that longjmp exits all pending calls to eval at once.

Clearly, it is possible to improve or modify this implementation in various ways. For example, we could have introduced an array of indices to tell us where the tokens start within the string. The array would be getting its values as the contents of a line are being read, and would simplify the parsing afterwards.

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

char *pb, *p;
jmp_buf env;

double eval() {
  double x;  char *q1, *q2;
  if (isspace(*--p)) {
    while (p>pb && isspace(*p)) --p;
    if (p>pb) switch (*p) {
        case '+': return eval()+eval();
        case '*': return eval()*eval();
        case '-': return x=eval(),eval()-x;
        case '/': return x=eval(),eval()/x;
	default:  q1 = p+1;
                  while (!isspace(*--p)) ;
		  if (x=strtod(++p,&q2),q2==q1) return x;
    }
  }
  longjmp(env,0);
}

int main() {
  int sz,c,n;
  double x;
  pb = malloc(sz=4);
  *pb = ' ';
  p = pb+1;
  while ((c=getchar())!=EOF)
    if (c!='\n') {
      n = p-pb;
      if (n+2==sz) pb = realloc(pb,sz*=2);
      p = pb+n;
      *p++ = c;
    } else {
      while (--p>pb && isspace(*p)) ;
      if (p++>pb) {
        *p++ = ' ';
        if (!setjmp(env)) {
          x = eval();
          while (--p>pb && isspace(*p)) ;
          if (p>pb)  longjmp(env,0);
          printf("%f\n",x);
        }
        else  printf("error\n");
        p = pb+1;
      }
    }
}

boykobbatgmaildotcom