I came across a task which makes you check if a String passed as an argument to your method/function is a correct statement in the Reverse Polish Notation sense. It can contain lowercase alphabet letters, operation signs and integers. Is there any faster way to check it than to read every character separately and actually try to evaluate the whole expression?
You don't have to evaluate the whole expression but you do need to split it into tokens, and you have to know the valence of every operator (that is, how many operands it takes). For simplicity, let the valence of an operand be 0; then do the following:
Set stack_size to 0; For Each token In expression: Set stack_size to stack_size + 1 - valence(token) If stack_size <= 0: Report failure If stack_size == 1: Report success Else : Report failure
_ for unary minus.
expression: 3 4 + 1 * _ stack_size: 0 1 2 1 2 1 1 -> success expression: 2 3 4 + 1 * _ stack_size: 0 1 2 3 2 3 2 2 -> failure (not 1 at the end) expression: 2 3 + + 1 * _ stack_size: 0 1 2 1 0 -> failure (stack_size <= 0)
You can use a parse table to recognize reverse polish notation. It requires looking at each character, but it's fast.
Wikipedia has a good algorithm to parse the expression. Unless the expression is invalid (in which case you may terminate early), there's no way you can do better than O(n). That is, you have to evaluate all tokens in the string to ensure it's valid.