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

If you're only interested in checking the validity and not actually evaluating the expression, all you need is a counter. Parse the string into tokens (a token is either a number or an operator), initialise a counter to 0, then proceeding left to right:

• add 1 for each number
• subtract 1 for each binary operator (+, *, etc)
• check that the counter is greater than zero for each unary operator (sqrt, sin, etc)

If the counter ever goes below zero, then you have too many operators and the expression is not valid. If the counter ends up greater than zero, then you have too many input numbers. If the counter is zero at the end, then the expression is complete and valid.

Answer 2

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 zero.
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 binary operator, decrement the counter, then increment it.
5. At the end of the string, if the counter is one, and if it never went below zero, the string is valid.