11–20 of 38 posts
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.
(([[()])) -> ok ((([](])) -> not ok
Hope OP gets this message.
What is some further reading y'all could recommend on formal languages?
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 " which rules out the simple recursive regex approach (counter still works).
Earlier quoted context omitted.
you don't need a full counter. increment, decrement, and check_if_zero are enough. no need for get_value.
you also need check_if_negative to detect close-before-open
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.
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.
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.
"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 with…
"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 with…
To report the location of an unclosed opener you need a stack.
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.
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…