Postfix Expressions

Puzzle: recursive postfix evaluation.

On Saturday the Computer Science&Informatics School of the University College Dublin has a local programming competition. That, and a problem from Mihai, reminded me that I didn't post puzzles here in a long time. This one is an implementation puzzle.

A typical way to evaluate a postfix expression is to use a stack.

#include <stdio.h>

int stack[1<<20]; /* operand stack */
int sz; /* stack[0..sz) is used */

int main() {
  int c; /* last read character */
  while ((c = getchar()) != '|') {
    switch (c) {
    case '+': --sz; stack[sz-1] += stack[sz]; break;
    case '-': --sz; stack[sz-1] -= stack[sz]; break;
    case '*': --sz; stack[sz-1] *= stack[sz]; break;
    default:
      if ('0' <= c && c <= '9') stack[sz++] = c - '0';
    }
  }
  printf("%d\n", *stack);
}

The code above assumes that operands are digits, that the only allowed operators are +-*, that the input is terminated by |, and that there are no other characters.

The problem is: Can you implement this without:

• an explicit stack
• loops

Both should be replaced by recursion. As usual, you can email me solutions to radugrigore at gmail.com and I'll post the best solution plus a list of those who solved the puzzle.