Postfix notation validation?

Question

What would be a good way to evaluate a string(array, something) that contains a postfix expression(ex: 3 5 +) to check for validity?

Answer 1

I'm assuming here that what you mean by valid is that executing the code will never underflow the stack and will leave a single value on the stack. If you have a more stringent notion of validity, you'll need a more sophisticated checker.

If you want to check for this kind of validity, it is not necessary to evaluate the string, and you can use a counter, not a stack. The counter tracks the number of values that would be on the stack if you evaluated. To simplify, let's suppose you have only literals, binary operators, and unary operators. This algorithm uses a special decrement operation: if when you decrement, the counter goes below zero, the string is invalid:

1. Initialize the counter to 0.
2. When you see a literal, increment the counter.
3. When you see a binary operator, decrement the counter twice, then increment it.
4. When you see a unary operator, decrement the counter, then increment it.
5. At the end of the string, if the counter is 1, and if it never went below 0, the string is valid.