A most important, but also most elusive, aspect of any tool is its influence on the habits of those who train themselves in its use. If the tool is a programming language this influence is, whether we like it or not, an influence on our thinking habits.

dude, you don't need a recursive descent parser to solve paren problem. All you need is two counters - one for open parens, and one for closed. Let's call those A and B. A correct paren expression starts with an open paren, so A gets set to 1 at the start. A correct paren expression also has one closing paren at the end, therefore B should equal A at the end. Now what happens in between? In between we can only have valid paren expression again, therefore at the end we should always check if A-B==0. Also if at any moment B>A, there was an unexpected closed paren and the expression is invalid.

Therefore bigO for paren problem with this algorithm is O(n).

The bigO for the yo-dawg regex is at least O(n^2) from the T(n) = T(n-2) + O(n) recursion recurrence (at each recursion we eliminate two parenthesis). "at least" because it also depends on the regex engine.

dude, you don't need a recursive descent parser to solve paren problem. All you need is two counters - one for open parens, and one for closed. Let's call those A and B. A correct paren expression starts with an open paren, so A gets set to 1 at the start. A correct paren expression also has one closing paren at the end, therefore B should equal A at the end. Now what happens in between? In between we can only have valid paren expression again, therefore at the end we should always check if A-B==0. Also if at any moment B>A, there was an unexpected closed paren and the expression is invalid.

Therefore bigO for paren problem with this algorithm is O(n).

The bigO for the yo-dawg regex is at least O(n^2) from the T(n) = T(n-2) + O(n) recursion recurrence (at each recursion we eliminate two parenthesis). "at least" because it also depends on the regex engine.

## Reply To This Comment