2 ms·
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
by 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 agoIt 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