I chanced to read an article this morning on Ben Aston's blog, which dealt with balancing braces. You should go read it now, since it's good and since I'm about to critique the heck out of his approach.
The task Ben sets himself is simple: write a Javascript function, isBalanced, that returns true if a set of braces is balanced. Running his solution through jshint, we find it has 13 statements with a cyclomatic complexity score of 6. I think it is an inelegant solution for an elegant problem, as my solution came in at 4 statements with a complexity score of 2. (And mine doesn't repeat the characters to be matched either. )
This can be looked at not as a parsing problem, but as a pattern-matching problem instead. You have to think about it recursively.
The key insight we will use is that this problem is as easy as repeatedly removing pairs of braces, such as ()
or []
. There is no case where the braces could be balanced without a pair of braces occurring in the string. By repeatedly removing all the paired braces, we will end up with either an empty string or the non-matching braces.
Let's work this through. '[{}]'
has one pair of braces we can spot - {}
. Remove it and we are left with '[]'
and another pair, []
, which we can also remove. Are there any characters left? No? Then the input was balanced. However, '[{]}'
has no pairs of braces, and does have characters left, so it's unbalanced. '()['
reduces to '['
, which is likewise unbalanced.
function isBalanced(braces) {
do {
var matches = braces.split(/\(\)|{}|\[]/);
braces = matches.join('');
} while (matches.length > 1);
return !braces;
}
Given this solution, Ben's statement that "to solve this problem we need to have a function that will return the opener corresponding to a closer" is proven false. We have no such function, and we have solved the problem.
In our code, there's a lot of things we don't have to worry about. We don't have to worry about inverting characters. We don't have to worry about queues. We don't have to worry about what the schema is, or even what a schema is. We just remove characters from a string.
This post is a lot shorter than Ben's, because my solution is a lot simpler. Often you do not have to think of the right data structure, but instead spend some time thinking of the right algorithm. My solution is simpler, but perhaps Ben's is constrained by an outside influence, not stated in the problem - say, the user of the function will want an error message pointing to the mismatched brace. While we should always strive for the clearest code, it's worth remembering that sometimes it was done that way for a reason.