Puzzle Answer: Postfix Expressions

A solution to a two-month old puzzle.

A while back I posted a puzzle asking for a recursive and stackless postfix expression evaluator. A bit over a week ago I received a solution from Ashutosh Mehra. (Go on, have a look at his blog. It's quite nice.)

At first sight this seems like a lowly coding exercise. And it is, but with a catch: It is designed to illustrate two fundamental ideas that should be part of every programmer's ethos.

1. Recursion is equivalent to loops.
2. Recursion is implemented with stacks.

If one of these two fairly obvious statements is not built into you, then you'll have trouble finding a solution. The first statement implies that any program can be written without using loops. How? First, write all the loops using only while. Second, replace each loop while (C) B; with a call to a new function loop defined as follows:

void loop(ARGS) {
  if (!C) return;
  B; loop();
}

The condition C and the body B will probably refer to some local variables. In order to have them accessible for reading and for writing from loop we send as arguments ARGS pointers to them, and modify C and B accordingly.

Exercise: What to do if B contains break? (Note: The solution to this is supposed to be easy if the previous two paragraphs were understood.)

What about the stack? We also want to get rid of the stack.

The solution is again easy if you remember that local variables (and function arguments) come from a "stack". So the key idea is to use the call stack as the operand stack. This said, enjoy the solution.

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

int add(int x, int y) { return x + y; }
int sub(int x, int y) { return x - y; }
int mul(int x, int y) { return x * y; }
typedef int (*op_t)(int, int);
op_t op[256];

int c; /* last read character */

void read_digits(int* y) {
  if (!isdigit(c = getchar())) return;
  *y = eval(*y, c - '0');
  read_digits(y);
}

int eval(int x, int y) {
  read_digits(&y);
  return op[c](x, y);
}

int main() {
  op['+'] = add, op['-'] = sub, op['*'] = mul, op['|'] = add;
  printf("%d\n", eval(0, getchar() - '0'));
}

When the function eval(x, y) is called, the top value in the operand stack is y and the value just before is x. While the next token is a digit it calls itself recursively eval(y, new_digit). The "while" part is implemented by the recursive function read_digits. When the token that says what operation should be performed between x and y is read, the operation is performed and the result returned.

This variant is somewhat wasteful of memory.