3
\$\begingroup\$

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<Character> 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();
    }
\$\endgroup\$
2

1 Answer 1

4
\$\begingroup\$

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<Character, Character> 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.

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.