A Brutal Look at Balanced Parentheses, Computing Machines, and Pushdown Automata
Key topics
The article explores the concept of balanced parentheses and its relation to computing machines and pushdown automata, sparking a discussion on the practical applications and theoretical foundations of computer science concepts.
Snapshot generated from the HN discussion
Discussion Activity
Very active discussionFirst comment
8d
Peak period
30
Days 9-10
Avg / period
15.5
Based on 31 loaded comments
Key moments
- 01Story posted
Nov 5, 2025 at 12:49 PM EST
about 2 months ago
Step 01 - 02First comment
Nov 13, 2025 at 10:35 PM EST
8d after posting
Step 02 - 03Peak activity
30 comments in Days 9-10
Hottest window of the conversation
Step 03 - 04Latest activity
Nov 26, 2025 at 12:46 PM EST
about 1 month ago
Step 04
Generating AI Summary...
Analyzing up to 500 comments to identify key contributors and discussion patterns
Want the full context?
Jump to the original sources
Read the primary article or dive into the live Hacker News thread when you're ready.
A counter. That's the difference between theory and practice. Because in practice, everything is finite.
(([[()])) -> ok ((([](])) -> not ok
Hope OP gets this message.
https://en.wikipedia.org/wiki/Dyck_language
EDIT: The wikipedia article that is.
If you have multiple kinds of brackets then you need the same number of counters. Each counter corresponds to the number of openers of that type currently on the stack. EDIT: this is wrong. Counters can't distinguish between [() and ([)
If you're writing a parser and you want to report the location of an unclosed opening bracket then you need the actual stack.
So to generalise your point you need a counter for each transition to a different type of opener.
So (([])) needs only 2 counters, not 3.
You could constrain it further if certain types of openers are only valid in certain cases so you could exclude certain types of transitions.
EDIT:
([)] could indeed be handled by just additionally tracking the current open type. (([]]) is a better example, as it shows that to handle deeper nesting you need additional pieces of data that will grow at some rate (at most by the number of opens, possibly lower depending on which types can validly appear within which types)
Indeed! https://neilmadden.blog/2019/02/24/why-you-really-can-parse-...
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).
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.
You NEED a stack.
(And no, I didn't presume anything ... I addressed rewinding above.)
(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)
I still enjoy writing code like the code in TFA, but these days people seem a lot less interested in code than organizing their agentic LLMs, so I don't have the same incentive to share whatI find interesting. And it would be terrible marketing, like showing up to audition for a job driving F1... In a Jaguar E-Type.
Elegant and beautiful, but that isn't the game any more.
20 years later I got to apply some of the same ideas to a language processing application, and it was such a pleasure to actually use something conceptual like that. Made me briefly regret landing in more hybrid infrastructure/automation roles instead of pure software development.
Somewhere I may still have my copy of Preperata and Yeh that my professor recommended at the time for further reading. Like most of my books, it was never actually read, just sat around for years.