4 ms·

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

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.

testaccount28 1y ago
you don't need a full counter. increment, decrement, and check_if_zero are enough. no need for get_value.
- stellalo 1y ago
  you also need check_if_negative to detect close-before-open
  - jibal 1y ago
    The counter is at 0, which indicates an error ... that plus the counter being non-zero when reaching the end of input is the entire point.
nmadden 1y ago
> Because in practice, everything is finite. Indeed! https://neilmadden.blog/2019/02/24/why-you-really-can-parse-html-and-anything-else-with-regular-expressions/ https://neilmadden.blog/2019/02/24/why-you-really-can-parse-...
pfortuny 1y ago
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.
- jibal 1y ago
  .
  - immibis 1y ago
    Your solution incorrectly fails ({}). You need the stack.
    - jibal 1y ago
      You're right ... no counter can tell the difference between ({ and {(. Oops.
- _0ffh 1y ago
  In case anybody is interested, when we generalize the concept we're talking about Dyck languages. https://en.wikipedia.org/wiki/Dyck_language https://en.wikipedia.org/wiki/Dyck_language
  - reuben364 1y ago
    I was surprised to not see a connection made to free groups in the article. EDIT: The wikipedia article that is.
jibal 1y ago
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 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.
- gpderetta 1y ago
  Wouldn't two counters report "([)]" as being properly balanced?
  - deleted 1y ago
    [deleted]
  - jibal 1y ago
    No, there's an open [ when the ) is encountered. The problem is the other way around -- my algorithm would report [() as an error. Oops, back to the drawing board. Clearly no counting can tell the difference between [() and ([).
- vidarh 1y ago
  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)

testaccount28 1y ago

you don't need a full counter. increment, decrement, and check_if_zero are enough. no need for get_value.

stellalo 1y ago
you also need check_if_negative to detect close-before-open
- jibal 1y ago
  The counter is at 0, which indicates an error ... that plus the counter being non-zero when reaching the end of input is the entire point.

nmadden 1y ago

> Because in practice, everything is finite. Indeed! https://neilmadden.blog/2019/02/24/why-you-really-can-parse-html-and-anything-else-with-regular-expressions/ https://neilmadden.blog/2019/02/24/why-you-really-can-parse-...

pfortuny 1y ago

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.

jibal 1y ago
.
- immibis 1y ago
  Your solution incorrectly fails ({}). You need the stack.
  - jibal 1y ago
    You're right ... no counter can tell the difference between ({ and {(. Oops.
_0ffh 1y ago
In case anybody is interested, when we generalize the concept we're talking about Dyck languages. https://en.wikipedia.org/wiki/Dyck_language https://en.wikipedia.org/wiki/Dyck_language
- reuben364 1y ago
  I was surprised to not see a connection made to free groups in the article. EDIT: The wikipedia article that is.

jibal 1y ago

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

gpderetta 1y ago
Wouldn't two counters report "([)]" as being properly balanced?
- deleted 1y ago
  [deleted]
- jibal 1y ago
  No, there's an open [ when the ) is encountered. The problem is the other way around -- my algorithm would report [() as an error. Oops, back to the drawing board. Clearly no counting can tell the difference between [() and ([).
vidarh 1y ago
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)