Shunting-yard: missing argument to operator

Question

I'm implementing the shunting-yard algorithm. I'm having trouble detecting when there are missing arguments to operators. The wikipedia entry is very bad on this topic, and their code also crashes for the example below.

For instance 3 - (5 + ) is incorrect because the + is missing an argument.

Just before the algorithm reaches the ), the operator stack contains - ( + and the operand stack contains 3 5. Then it goes like this:

• it pops + from the operator stack
• discovers that + is a binary operator
• pops two operands, apply operator and push result (8) to operand stack
• then it pops the matching ( from the stack, and continues

So how can I detect that the + is missing an argument? extra kudos if you also update wikipedia :-)

Answer 1

For binary operator only expressions, the postfix expression has the invariant that in any prefix of the expression, numbers of operands > numbers of operators and in the end, that difference is exactly one.

So you can verify the RPN expression for validity at each stage of the shunting yard by maintaining a running count of number of operands - number of operators. If that drops below one, or becomes more than one at the end, you have an error.

It does not pinpoint the error, but at least lets you know there is one.

(Note: I haven't tried proving the above fact, but seems like it will work)