I am now in the midst of making a simple bytecode interpreter that uses RPN for expression notation and really postfix notation for anything, but now I've come to the question which is: can short circuit evaluation actually be used on postfix expressions? For example when evaluating the expression (false && (factorial(7) > factorial(5))) C++ knows the result of the && operator on the two operands evaluates to false before it even gets to the second operand, since (false && anything) is always equal to false. Now when you put this in RPN, you get (false (7 factorial 5 factorial >) &&).
I wanted to build an efficient RPN expression parser, so the problem is this: how do I make an efficient RPN expression parser with short circuit evaluation?
You would evaluate an RPN expression in two phases.
Phase 1: parse the RPN, and construct a tree representation of the RPN. So, in this tree, for example, the && node has two children nodes, for each half of the expression. Constructing this tree is a nearly identical process as evaluating the RPN, except for the evaluating part, which gets replaced by the operation of constructing a new node, and linking its child nodes to their new parent node, then pushing the parent node back on the RPN evaluation stack.
Phase 2: evaluate the constructed tree, using recursive descent. At this point, short-circuit evaluation becomes trivial: evaluate the left-hand child of a &&, then decide whether you actually want to evaluate the right-hand child.
Ditto for the || node, etc...