News for hackers. Stuff that matters.
Re:A Brutal Look at Balanced Parentheses, Computing Machines... by skybrian on Friday February 22, 2019 @01:28PM (#19227740)
I skimmed, but feel like he should have talked about how in an interview question, you could solve this by counting parens with a 64-bit counter. There are limits on practical input size and on stack size, so arguments about infinite languages don't directly apply.

A deeper question to consider: why do we study infinite languages and then apply the results to finite problems? What do we learn this way?

Re:A Brutal Look at Balanced Parentheses, Computing Machines... by braythwayt on Friday February 22, 2019 @02:24PM (#19228274)
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.

Re:A Brutal Look at Balanced Parentheses, Computing Machines... by skybrian on Friday February 22, 2019 @03:05PM (#19228648)
Yes, 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.
Re:A Brutal Look at Balanced Parentheses, Computing Machines... by braythwayt on Friday February 22, 2019 @03:08PM (#19228671)
A 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.

Re:A Brutal Look at Balanced Parentheses, Computing Machines... by spc476 on Saturday February 23, 2019 @01:52AM (#19232101)
Are 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
Re:A Brutal Look at Balanced Parentheses, Computing Machines... by a1369209993 on Friday February 22, 2019 @08:28PM (#19230956)
> 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)
Re:A Brutal Look at Balanced Parentheses, Computing Machines... by mehrdadn on Friday February 22, 2019 @02:28PM (#19228318)
What do you do when you have multiple types of grouping? E.g. Parentheses and braces and brackets in a programming language?
Re:A Brutal Look at Balanced Parentheses, Computing Machines... by mjevans on Friday February 22, 2019 @03:50PM (#19228979)
I think that depends on the goals of the design. The very simple single-grouping type case can be used to prove that something isn't obviously false in isolation.

Once grouping starts to be an issue I think that different spans need to be broken out from the main section and each treated as isolated fragments to validate.

Re:A Brutal Look at Balanced Parentheses, Computing Machines... by Epholys on Friday February 22, 2019 @02:09PM (#19228139)
Yeah, that's the first solution that popped in my mind too. I think it needs just a special case at the beginning to check if the first paren is not a closing one.

EDIT: yep, after reading the comments below I see that I really should have put just a little more thought before dismissing this as too trivial to think about.

Re:A Brutal Look at Balanced Parentheses, Computing Machines... by braythwayt on Friday February 22, 2019 @02:25PM (#19228284)
The stack solution checks that the stack is non-empty before popping.

The counter solution simply needs to check that the counter is non-zero before decrementing.

All cases then work perfectly.

Re:A Brutal Look at Balanced Parentheses, Computing Machines... by FreeFull on Friday February 22, 2019 @02:25PM (#19228280)
What you actually need is to check if the count ever goes negative.
Re:A Brutal Look at Balanced Parentheses, Computing Machines... by skybrian on Friday February 22, 2019 @02:18PM (#19228207)
A test case: ())(