2 ms·

Do you have a language that allows you to easily create a stack? Push open brackets onto the stack, when you get a closing bracket, pop the stack and make sure

Do you have a language that allows you to easily create a stack? Push open brackets onto the stack, when you get a closing bracket, pop the stack and make sure it's the "right" one. When the input is exhausted, if the stack is empty, the input was balanced.

tzs 4y ago
Since the only thing you are pushing onto the stack are open brackets you don't actually need the stack. Just keep a count of how many brackets would have been on the stack. Increment the count when you see an open bracket. Decrement the count when you see a close bracket. If the count every goes negative there was a mismatch. If the count does not end up at 0 when you've processed all the brackets there was a mismatch. It can also be treated as a text transformation problem. Every non-empty string of matched brackets must contain at least one '()', and deleting a '()' from a string does not change whether or not the string is balanced. That gives an approach of repeatedly finding and deleting '()' from the string until there are no more '()'s to delete. If that gives you an empty string the original string was all matched. If the final string is not empty then the original string had a mismatch. Here's that as a shell script. #!/bin/sh S=`echo $1 | tr -c -d '()'` P=x while [ "$S" ]; do if [ "$S" = "$P" ]; then echo "Mismatch" exit 1 fi P=$S S=`echo $S | sed -e 's/()//g'` done echo "All match" exit 0
- sokoloff 4y ago
  It depends on the problem definition (specifically on the definition of the word "brackets"). If you want to ensure the proper balancing of all of {}, [], and () [while excluding improper nesting], you need a stack [or equivalent]. If you only want to ensure () balancing, you can just do a count. IMO: ({[]}) // has balanced brackets ({[}]) // has imbalanced brackets

tzs 4y ago

Since the only thing you are pushing onto the stack are open brackets you don't actually need the stack. Just keep a count of how many brackets would have been on the stack. Increment the count when you see an open bracket. Decrement the count when you see a close bracket. If the count every goes negative there was a mismatch. If the count does not end up at 0 when you've processed all the brackets there was a mismatch. It can also be treated as a text transformation problem. Every non-empty string of matched brackets must contain at least one '()', and deleting a '()' from a string does not change whether or not the string is balanced. That gives an approach of repeatedly finding and deleting '()' from the string until there are no more '()'s to delete. If that gives you an empty string the original string was all matched. If the final string is not empty then the original string had a mismatch. Here's that as a shell script. #!/bin/sh S=`echo $1 | tr -c -d '()'` P=x while [ "$S" ]; do if [ "$S" = "$P" ]; then echo "Mismatch" exit 1 fi P=$S S=`echo $S | sed -e 's/()//g'` done echo "All match" exit 0

sokoloff 4y ago
It depends on the problem definition (specifically on the definition of the word "brackets"). If you want to ensure the proper balancing of all of {}, [], and () [while excluding improper nesting], you need a stack [or equivalent]. If you only want to ensure () balancing, you can just do a count. IMO: ({[]}) // has balanced brackets ({[}]) // has imbalanced brackets