Bracket Pair Validation

Validate that the following bracket pairs [], {}, () open and close successfully in a candidate String.

Valid String Example: "[{()}]" should be evaluated as true because no "outer" open bracket is closed before an "inner" open bracket.

Invalid String Example: "[f{o]o}"

I would appreciate feedback on my implementation:

• Is there a case I'm missing?

• Is there a cleaner way to validate bracket pairs?

• Are there any particular performance concerns I'm ignoring?

• I have hard-coded my bracket values. What if I want to add, say, ten more bracket values...is there a cleaner way to implement the open/close relationship? Use a Map, perhaps?

public boolean validateBracketPairs(final String string) {
final Stack bracketStack = new Stack<>();
for (final char character : string.toCharArray()) {
if ('{' == character || '[' == character || '(' == character) {
bracketStack.push(character);
}

else if (!bracketStack.empty() &&
(('{' == bracketStack.peek() && '}' == character)
|| ('[' == bracketStack.peek() && ']' == character)
|| ('(' == bracketStack.peek() && ')' == character))) {
bracketStack.pop();
}

else if ('}' == character || ']' == character || ')' == character) {
return false;
}
}

return bracketStack.empty();
}


Right, so I've got a few suggestions.

First, instead of making ourselves worry about non-bracket characters, let's trim them out:

string = string.replaceAll("[^\\[\\]\\{\\}\\(\\)]", "");

You'll have to remove the final modifier, which I can't see a reason for anyway. Also, you never actually caused an error if character wasn't a bracket, so the code still ends up working the same. It's just less to worry about.

Note: Technically, since this code ignores all non-bracket characters, this statement isn't necessary. If you comment it out, the rest of the code should still work fine. Still, I like explicitly saying, in code, that my thing ignores your petty brackets and mustaches.

Second, let's define a private static final Map MATCHING_CHARS1 to store the pairs, instead of hardcoding them. That way, instead of checking if something matches one of three hard-coded brackets, we can do this:

if (MATCHING_CHARS.containsKey(character)) {

And instead of peek()ing once per bracket, we do it a flat rate of once:

else if (!bracketStack.empty() &&
    MATCHING_CHARS.get(bracketStack.peek()) == character) {

Note that since get returns null when the key isn't there, it automagically doesn't give a crap if the character isn't in MATCHING_CHARS! (and also doesn't match)

And finally, we replace your last if with:

else if (MATCHING_CHARS.containsValue(character)) {

Whew! Much simpler. Now, unless you plan to synchronize that regex we used at the beginning and the map for any brackets you add in the future, I suggest we do this:

private static final String REMOVE_REGEX = "[^\\" + String.join("\\", 
    MATCHING_CHARS.values().appendAll(MATCHING_CHARS.keys()) // every bracket
) + "]"; //for brackets 'a', 'b', 'c' should be "[^\\a\\b\\c]"

Then we use that in the place of the regex from before.

Actually, I don't suggest we do that awful mess of a line, I suggest we use a language where it's easier to get the behavior I'm looking for and doesn't require ugly hacks, but whatever. Ya make do with what you've got.

Now, one last tip: Don't name things string. Name it checking or toCheck or something that describes its purpose. Java's a statically-typed language; we can tell that it's a String without you naming it that.

StackExchange Code Review Q#113228, answer score: 4