finding validity of bracket string in java

Question

Here is the thing:

You are given a string whose elements are brackets ( ) [ ] { }.

Rules:

Every opening bracket has a corresponding closing bracket.
2 brackets form a pair if they have no open bracket of any type between them.
The closing bracket of a pair must be of the same as the opening bracket, e.g. () is valid, but [) is not valid.

The task is to determine if a string of bracket is valid or invalid by these criteria.

example valid string: {}[]()

example invalid string: {[}]

This is my solution:

static String braces(String string) {
   Stack<String> stack = new Stack<>();
   for(int i = 0; i <= string.length() - 1; i ++){

       if(string.substring(i, i+1).equals("("))
           stack.push((string.substring(i, i+1)));

       else if(string.substring(i, i+1).equals("["))
           stack.push((string.substring(i, i+1)));

       else if(string.substring(i, i+1).equals("{"))
           stack.push((string.substring(i, i+1)));

       else if(string.substring(i, i+1).equals(")"))
           if(stack.peek().equals("("))
               stack.pop();
           else
               return "NO";

       else if(string.substring(i, i+1).equals("]"))
           if(stack.peek().equals("["))
               stack.pop();
           else
               return "NO";

       else if(string.substring(i, i+1).equals("}"))
           if(stack.peek().equals("{"))
               stack.pop();
           else 
               return "NO";
       }
   return "YES";
   }

It is done according to algorithm from here How to find validity of a string of parentheses, curly brackets and square brackets? which is as follows:

Maintain a stack of characters.
Whenever you find opening braces '(', '{' OR '[' push it on the stack.
Whenever you find closing braces ')', '}' OR ']' , check if top of stack is corresponding opening bracket, if yes, then pop the stack, else break the loop and return false.
Repeat steps 2 - 3 until end of the string.

But I don't like how does it look like. The way of accessing to String elements is kind of clunky and I'm curious if there is another, more clear way to solve the problem, maybe using regular expression?

I'm voting to close this question as off-topic because is it about general code improvement rather than a specific problem. This may be considered as "primarily opinion based" or it may be better on another Stack Exchange site, perhaps code review. — AdrianHHH, Apr 09 '16 at 12:03
The algorithm seems good, the only problem is that it performs 6 tests for each character that is not a bracket. Perhaps can you try to extract all brackets from the string before, or to remove all that is not a bracket. (but not sure that this will speed up the code in all cases). — Casimir et Hippolyte, Apr 09 '16 at 12:04

STaefi · Answer 1 · 2016-04-09T13:05:10.280

It is a very clear algorithm and seems you got it right. So for changing the way of accessing the characters, why didn't you use the String#charAt method?

Also you may want to change the return type of the method from String "YES" or "NO" to true or false of type boolean:

static boolean isValidBracketString(String string) {
    Stack<Character> stack = new Stack<>();
    for(int i=0; i< string.length(); i++){
        if(string.charAt(i) == '{' || string.charAt(i) == '[' || string.charAt(i) == '('){
            stack.push(string.charAt(i));
        } else if(string.charAt(i) == '}' || string.charAt(i) == '}' || string.charAt(i) == ')') {
            if(stack.size() == 0)
                return false;
            switch(stack.pop()){
                case '(':
                    if(string.charAt(i) != ')')
                        return false;
                    break;
                case '[':
                    if(string.charAt(i) != ']')
                        return false;
                    break;
                case '{':
                    if(string.charAt(i) != '}')
                        return false;
                    break;
            }
        }
    }
    return stack.size() == 0;
}

Oh nice, that's what I was looking for! Thanks! – bambaniasz Apr 09 '16 at 12:32 — bambaniasz, Apr 09 '16 at 12:32

score 2 · Accepted Answer · answered Apr 09 '16 at 12:29

You could convert the string to a char[] and iterate over it. Additionally, you could make the code look more elegant by having a Map of closing to opening brackets:

// Initialize some helper structures:
private static Map<Character, Character> CLOSE_TO_OPEN;
private static Set<Character> OPENERS;
static {
    CLOSE_TO_OPEN = new HashMap<>();
    CLOSE_TO_OPEN.put(')', '(');
    CLOSE_TO_OPEN.put(']', '[');
    CLOSE_TO_OPEN.put('}', '{');
    OPENERS = new HashSet<>(closeToOpen.values());
}

public static boolean braces (String str) {
    Stack<Character> stack = new Stack<>();
    for (Character c : str.toCharArray()) {

        // If it's an opening bracket, push it to the stack
        if (OPENERS.contains(c)) {
            stack.push(c);
        } 
        // If it's a closing bracket, check the last opener
        else if (CLOSE_TO_OPEN.containsKey(c)) {
            try {
                Character opener = stack.pop();
                // Handle mismatches brackets
                if (!CLOSE_TO_OPEN.get(c).equals(opener)) {
                    return false;
                }
            } 
            // If the stack is empty, there's a redundant closer
            catch (EmptyStackException ignore) {
                return false;
            }
        }
    }

    // If the stack isn't empty once we're done with the string, 
    // there are redundant openers
    if (!stack.empty) {
        return false
    }
    return true;
}

finding validity of bracket string in java

2 Answers2