Given an input like this: 3+4+
Algorithm turns it in to 3 4 + +
I can find the error when it's time to execute the postfix expression. But, is it possible to spot this during the conversion?
(Wikipedia article and internet articles I've read do not handle this case)
Thank you
Valid expressions can be validated with a regular expression, aside from parenthesis mismatching. (Mismatched parentheses will be caught by the shunting-yard algorithm as indicated in the wikipedia page, so I'm ignoring those.)
The regular expression is as follows:
where:
The Wikipedia page you linked includes function calls but not array subscripting; if you want to handle these cases, then:
One thing to note in the above is that
PRE
andINF
are in disjoint contexts; that is, ifPRE
is valid, thenINF
is not, and vice versa. This implies that using the same symbol for both a prefix operator and an infix operator is unambiguous. Also,PRE
andPOST
are in disjoint contexts, so you can use the same symbol for prefix and postfix operators. However, you cannot use the same symbol for postfix and infix operators. As examples, consider the C/C++ operators:I implicitly used this feature above to allow
(
to be used either as an expression grouper (effectively prefix) and as a function call (infix, because it comes between the function name and the argument list; the operator is "call".)It's most common to implement that regular expression as a state machine, because there are only two states:
We could call State 1 "want operand" and State 2 "have operand". A simple implementation would just split the shunting yard algorithm as presented in wikipedia into two loops, something like this (if you don't like
goto
, it can be eliminated, but it really is the clearest way to present a state machine).