Hacker News new | ask | show | jobs
by praptak 209 days ago
"But on a day-to-day basis, if asked to recognize balanced parentheses?"

On day-to-day basis you will never encounter this problem in pure form. As the consequence the solutions are not good for the day-to-day stuff.

Even if you only are only writting a verifier (which is already a bit unrealistic), you'll need to say something more than "not balanced". Probably rather something along the lines of "closing brace without a matching opening at [position]" or "[n] unclosed parentheses at <end of stream>" which rules out the simple recursive regex approach (counter still works).
1 comments
jibal 209 days ago
To report the location of an unclosed opener you need a stack.
link
vidarh 209 days ago
Depends. You want a stack, as it's certainly more efficient, but if you can rewind the position pointer you don't need one (you can count backwards).

EDIT: It gets complicated if you need to count multiple different types of openers. In that case I think you need the stack, at least unless there are constraints on which openers can occur within others - you at the very least need to know which closer you're looking for right now, but if you can't deduce what is outside, you obviously then need to keep track of it.

In practice, of course, we'll generally use a stack because it's just pointless to make life harder by not using one for this.

link
jibal 209 days ago
If you've encountered 1 million unclosed parentheses, any or all of them could be unbalanced, so to report which ones are, you need 1 million pieces of information. The obvious way to organize them is as stack. Of course there are worse ways to do it. Rewinding the position pointer means that you've kept the entire input as a stack of characters, and now you have to keep track of all the closers on a stack in order to balance them with their openers.

You NEED a stack.

(And no, I didn't presume anything ... I addressed rewinding above.)

link
vidarh 209 days ago
You're presuming you have only a non-rewindable stream as opposed to a file interface, which is why I was explicit about the requirement to be able to rewind the position to avoid a stack. If you only have a non-rewindable stream, then, yes, you need a strack. If you have a file handle, you do not.

(and yes, you did presume something; if you have rewindable file handle, you do not need to keep the characters; you can instead-re-read them)

link