2
\$\begingroup\$

Purpose

Validate whether the open brackets within a String have matching closed brackets, in the correct order.

The three types of valid brackets are

  • [ and ]
  • { and }
  • ( and )

Examples:

  • A[B]{C}(D) returns true
  • A[B{C}(D) returns false

Feedback

  • Creating a new Map of open brackets to closed brackets seems a bit expensive to do every single time - what's the best way of making a static Map (or some equivalent)?
  • Is the switch statement the best way to go about evaluating the cases? Is it better to use if statements instead?

Implementation

public class BracketPairsValidator {

  public static final char OPEN_SQUARE_BRACKET = '[';
  public static final char CLOSED_SQUARE_BRACKET = ']';

  public static final char OPEN_CURLY_BRACKET = '{';
  public static final char CLOSED_CURLY_BRACKET = '}';

  public static final char OPEN_PARENTHESIS = '(';
  public static final char CLOSED_PARENTHESIS = ')';

  public static boolean validBracketPairs(final String candidate) {
    final char[] chars = candidate.toCharArray();
    final Stack<Character> bracketStack = new Stack<>();
    final Map<Character, Character> bracketMap = new HashMap<>();
    bracketMap.put(OPEN_SQUARE_BRACKET, CLOSED_SQUARE_BRACKET);
    bracketMap.put(OPEN_CURLY_BRACKET, CLOSED_CURLY_BRACKET);
    bracketMap.put(OPEN_PARENTHESIS, CLOSED_PARENTHESIS);
    for (final char ch : chars) {
      switch (ch) {
        case OPEN_SQUARE_BRACKET:case OPEN_CURLY_BRACKET:case OPEN_PARENTHESIS: {
          bracketStack.add(ch);
          break;
        }

        case CLOSED_SQUARE_BRACKET:case CLOSED_CURLY_BRACKET:case CLOSED_PARENTHESIS: {
          if (bracketStack.isEmpty()) {
            return false;
          }

          if (ch != bracketMap.get(bracketStack.pop())) {
            return false;
          }
          break;
        }

        default: {
          break;
        }
      }
    }

    return bracketStack.isEmpty();
    }
}
\$\endgroup\$
  • 2
    \$\begingroup\$ You miss a constructor. It is a place to initialize the map. \$\endgroup\$ – vnp Feb 10 '16 at 1:22
2
\$\begingroup\$

Object scope

You should introduce object scope. Your source code gains flexibility through the possibility to to apply abstraction, polymorphy, inheritance (Open Closed Principle). Your code will be testable much more easy. Furthermore in JAVA 8 you can make use of functional interfaces. That would not be possible in a static context.

Constants

As "bracketMap" is a constant you should declare it "static final". Then you will get rid of instantiating the HashMap every time you call "validateBracketPairs".

break, multiple return (and continue)

Avoid those statements. Using them you hinder yourself to make use of applying refactorings like "extract method".

Within a loop you spread your breaking conditions all over the place. That makes the code less readable an maintainable. All breaking conditions for a loop should be at one place, the loop header/footer.

For methods that have to have a return value try to have only ONE return statement at the end.

for-loop

The for-each-loop is not the appropriate loop for this case. Consider a loop type that allows breaking conditions to have a proper place to put your go-on (breaking) conditions: As long as there are characters to process OR you not found a validation error.

switch-case

The switch case statement can be simplified through the standard if-then-else. Use the keys() and values()-method of the bracketMap to check if they contain a character. Now you are able to extends bracket pairs through putting them into the bracketMap without touching the if statement anymore. (Single Responsibility Principle).

Naming

Because bracketStack only contains open brackets it should be mentioned in the name: openBracketStack.

Code

So I would end up with something like this:

public class BracketPairsValidator implements Function<String, Boolean> {


    public static void main(String[] args) {
        System.out.println(new BracketPairsValidator().apply(""));
    }


    public static final char OPEN_SQUARE_BRACKET = '[';
    public static final char CLOSED_SQUARE_BRACKET = ']';

    public static final char OPEN_CURLY_BRACKET = '{';
    public static final char CLOSED_CURLY_BRACKET = '}';

    public static final char OPEN_PARENTHESIS = '(';
    public static final char CLOSED_PARENTHESIS = ')';

    private final static Map<Character, Character> BRACKET_MAP = createBracketMap();


    private static Map<Character, Character> createBracketMap() {
        HashMap<Character, Character> map = new HashMap<>();
        map.put(OPEN_SQUARE_BRACKET, CLOSED_SQUARE_BRACKET);
        map.put(OPEN_CURLY_BRACKET, CLOSED_CURLY_BRACKET);
        map.put(OPEN_PARENTHESIS, CLOSED_PARENTHESIS);
        return map;
    }


    @Override
    public Boolean apply(final String candidate) {

        StringCharacterIterator iterator = new StringCharacterIterator(candidate);

        final Stack<Character> openBracketStack = new Stack<>();

        boolean hasMatchingBracket = true;

        for (char ch = iterator.current(); ch != StringCharacterIterator.DONE && hasMatchingBracket; ch = iterator.next()) {

            if (isOpenBracket(ch)) {
                openBracketStack.add(ch);
            } else if (isClosedBracket(ch)) {
                hasMatchingBracket = !openBracketStack.isEmpty() && ch == BRACKET_MAP.get(openBracketStack.pop());
            }

        }

        return hasMatchingBracket && openBracketStack.isEmpty();
    }


    private boolean isClosedBracket(final char ch) {
        return BRACKET_MAP.values().contains(ch);
    }


    private boolean isOpenBracket(final char ch) {
        return BRACKET_MAP.keySet().contains(ch);
    }


}
\$\endgroup\$
0
\$\begingroup\$

In addition to oopexpert' s answer, I would also factor our the BracketMap (ideally to an interface as well)

public class DefaultBrackets implements Brackets{

    private static final char OPEN_SQUARE_BRACKET = '[';
    private static final char CLOSED_SQUARE_BRACKET = ']';

    private static final char OPEN_CURLY_BRACKET = '{';
    private static final char CLOSED_CURLY_BRACKET = '}';

    private static final char OPEN_PARENTHESIS = '(';
    private static final char CLOSED_PARENTHESIS = ')';

    private final static Map<Character, Character> BRACKET_MAP = createBracketMap();


    private static Map<Character, Character> createBracketMap() {
        HashMap<Character, Character> map = new HashMap<>();
        map.put(OPEN_SQUARE_BRACKET, CLOSED_SQUARE_BRACKET);
        map.put(OPEN_CURLY_BRACKET, CLOSED_CURLY_BRACKET);
        map.put(OPEN_PARENTHESIS, CLOSED_PARENTHESIS);
        return map;
    }

    @Override
    public boolean isClosedBracket(final char ch) {
        return BRACKET_MAP.values().contains(ch);
    }

    @Override
    public boolean isOpenBracket(final char ch) {
        return BRACKET_MAP.keySet().contains(ch);
    }


    @Override
    public char get(final char ch) {

        return BRACKET_MAP.get(ch);
    }
}

And the Validator becomes:

public class BracketPairsValidator implements Function<String, Boolean> {



    private Brackets brackets;

    public BracketPairsValidator(Brackets brackets) {
        this.brackets = brackets;
    }



    @Override
    public Boolean apply(final String candidate) {

        StringCharacterIterator iterator = new StringCharacterIterator(candidate);

        Brackets bracketMap = new Brackets();

        final Stack<Character> openBracketStack = new Stack<>();

        boolean hasMatchingBracket = true;

        for (char ch = iterator.current(); ch != StringCharacterIterator.DONE && hasMatchingBracket; ch = iterator.next()) {

            if (bracketMap.isOpenBracket(ch)) {
                openBracketStack.add(ch);
            } else if (bracketMap.isClosedBracket(ch)) {
                hasMatchingBracket = !openBracketStack.isEmpty() && ch == bracketMap.get(openBracketStack.pop());
            }

        }

        return hasMatchingBracket && openBracketStack.isEmpty();
    }


    public static void main(String[] args) {
        System.out.println(new BracketPairsValidator(new Brackets()).apply(""));
    }

}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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