Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A Brutal Look at Balanced Parentheses, Computing Machines, and Pushdown Automata

raganwald.com

Post reply on HN
Print view View original

21–30 of 38 posts

Re: A Brutal Look at Balanced Parentheses, Computing Machines, and Pushdown Automata

#21

Post by vidarh »

jibal wrote: post #17
userbinator wrote: post #5

we’ll ask, “What’s the simplest possible computing machine that can recognize balanced parentheses?” A counter. That's the difference between theory and practice. Because in practice, everything is finite.

The counter is simply the stack depth without bothering with the actual stack. If the stack is empty when you encounter a closer then it's unbalanced. If the stack isn't empty when you reach the end of the input then the items in the stack are unbalanced. 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 st…

You need the actual stack, I think, in the case of multiple types of openers without additional constraints, because if you just have raw counters you'd get tripped up by ([)] or similar.

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)

Re: A Brutal Look at Balanced Parentheses, Computing Machines, and Pushdown Automata

#22

Post by immibis »

jibal wrote: post #16
pfortuny wrote: post #11

Earlier quoted context omitted.

Yes. Actually, a more interesting example which does not complicate the statement (not the problem) too much is to check for nested parenthesis and brackets: (([[()])) -> ok ((([](])) -> not ok Hope OP gets this message.

.

Your solution incorrectly fails ({}). You need the stack.

Re: A Brutal Look at Balanced Parentheses, Computing Machines, and Pushdown Automata

#24

Post by jibal »

vidarh wrote: post #19
jibal wrote: post #18

Earlier quoted context omitted.

To report the location of an unclosed opener you need a stack.

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…

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.)

Re: A Brutal Look at Balanced Parentheses, Computing Machines, and Pushdown Automata

#25

Post by [deleted] »

gpderetta wrote: post #20
jibal wrote: post #17

Earlier quoted context omitted.

The counter is simply the stack depth without bothering with the actual stack. If the stack is empty when you encounter a closer then it's unbalanced. If the stack isn't empty when you reach the end of the input then the items in the stack are unbalanced. 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 st…

Wouldn't two counters report "([)]" as being properly balanced?

[deleted]

Re: A Brutal Look at Balanced Parentheses, Computing Machines, and Pushdown Automata

#26

Post by _0ffh »

pfortuny wrote: post #11
userbinator wrote: post #5

we’ll ask, “What’s the simplest possible computing machine that can recognize balanced parentheses?” A counter. That's the difference between theory and practice. Because in practice, everything is finite.

Yes. Actually, a more interesting example which does not complicate the statement (not the problem) too much is to check for nested parenthesis and brackets: (([[()])) -> ok ((([](])) -> not ok Hope OP gets this message.

In case anybody is interested, when we generalize the concept we're talking about Dyck languages.

https://en.wikipedia.org/wiki/Dyck_language

Re: A Brutal Look at Balanced Parentheses, Computing Machines, and Pushdown Automata

#27

Post by vidarh »

jibal wrote: post #24
vidarh wrote: post #19

Earlier quoted context omitted.

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…

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 t…

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)

Re: A Brutal Look at Balanced Parentheses, Computing Machines, and Pushdown Automata

#28

Post by [deleted] »

vidarh wrote: post #21
jibal wrote: post #17

Earlier quoted context omitted.

The counter is simply the stack depth without bothering with the actual stack. If the stack is empty when you encounter a closer then it's unbalanced. If the stack isn't empty when you reach the end of the input then the items in the stack are unbalanced. 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 st…

You need the actual stack, I think, in the case of multiple types of openers without additional constraints, because if you just have raw counters you'd get tripped up by ([)] or similar. 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…

[deleted]

Re: A Brutal Look at Balanced Parentheses, Computing Machines, and Pushdown Automata

#29

Post by [deleted] »

[deleted] wrote: post #28
vidarh wrote: post #21

Earlier quoted context omitted.

You need the actual stack, I think, in the case of multiple types of openers without additional constraints, because if you just have raw counters you'd get tripped up by ([)] or similar. 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…

[deleted]

[deleted]
Post reply on HN