4 ms·
Author here. That solution has been discussed elsewhere in my blog. If you think of the family of problems involving nested things, or tree-like things, or rec
by braythwayt 8y ago
Author here.
That solution has been discussed elsewhere in my blog. If you think of the family of problems involving nested things, or tree-like things, or recognizing, or parsing, the case where we only have one kind of parentheses and nothing else is what we might call the "degenerate case."
And like many degenerate cases, there is an optimization: Instead of pushing the exact same parenthesis onto the stack over and over again, we count them.
Alas, this does not grow. If we want to modify our code to handle multiple types of parentheses, or parse expressions that include parentheses into trees, and so forth, we must return to the stack.
So... My general thinking is that it is useful to know that for the degenerate case, we can replace a stack with a counter, but should I ever find myself writing a parser or what-not, if I used an optimization like this, I'd probably document that it's an optimization the degenerate case where we only ever put one thing on the stack.
One wild way to do that is to leave the code as-is, but hack the stack itself. So you still call .push() and .pop() and so forth, but behind the scenes, the "stack" object just counts pushes and pops.
- skybrian 8y agoYes, agreed. But it does show another pitfall when it comes to using a degenerate case as an interview question: someone who doesn't know anything about parsing or stacks might solve it easily if they have a different mindset. On the other hand, half-remembering something from school could really mess you up.
- braythwayt 8y agoA typical interview along these lines will get the candidate to the "single balanced parentheses" solution, then throw in multiple types of parentheses. The whole script goes sideways if the candidates whips Perl or Ruby or whatever out, and provides a recursive regex.
- a1369209993 8y ago> the candidates whips Perl or Ruby or whatever out My first thought for is_balanced_parens was something like: while _!="" (s'()''g or reject) #* multiple types of parentheses *# while _!="" (s'()''g or s'{}''g or reject)
- spc476 8y agoAre you talking about the interview script, or the programming script? And what if the interviewee brings out Lua and LPEG [1]: local lpeg = require "lpeg" local balance = lpeg.Cmt( lpeg.P { ( (lpeg.P(1) - lpeg.S"()[]{}<>") + lpeg.P"(" * lpeg.V(1) * lpeg.P")" + lpeg.P"{" * lpeg.V(1) * lpeg.P"}" + lpeg.P"[" * lpeg.V(1) * lpeg.P"]" + lpeg.P"<" * lpeg.V(1) * lpeg.P">" )^0 }, function(subject,position,capture) return position,position > #subject end ) print(balance:match "") -- true print(balance:match "()") -- true print(balance:match "((()))") -- true print(balance:match "()()()") -- true print(balance:match "()(())") -- true print(balance:match "(") -- false print(balance:match "(()") -- false print(balance:match "({)}") -- false print(balance:match "({})") -- true print(balance:match "()))((") -- false [1] http://www.inf.puc-rio.br/~roberto/lpeg/lpeg.html http://www.inf.puc-rio.br/~roberto/lpeg/lpeg.html