Valid Parentheses Coding Problem (Java)

The valid parentheses problem is pretty common and demonstrates the user’s ability to use a rarer data structure: the stack.

Given a string filled with parentheses – (, [, {, ), ], } – you must determine if the string is valid. A valid string is one that has the same number of opening parentheses as closing ones, and those groups must match in order. One being out of place immediately invalidates the string.

Example: “{[[]]}” This would be a valid string, but “(([]()” would not.

The first thing to determine is how to attack the problem. Our best bet is using a Stack, which is a data structure that holds data in a first in, last out style. It acts like a stack of books; you add to the top, and to dismantle it you would take from the top. This is perfect for this situation.

To begin, we need to set up a loop that will go through the given string. Because we need to know what each specific character is, it is best to turn the string into a character array and loop through that.

public boolean isValid(String s){
    Stack<Character> stack = new Stack<>();
    for (char c : s.toCharArray()){
        //logic
    }
}

So we create the stack and tell the computer that it will be filled with the data type ‘Character.’ Then we create a for each loop stating that for each character ‘c’ in the newly made character array, we will be running that logic.

Now to add the logic. We know that for every open bracket, there must be a corresponding closed bracket of the same type. We also know that they must be ordered correctly. To do this, look at the following code.

public boolean isValid(String s){
    Stack<Character> stack = new Stack<>();
    for (char c : s.toCharArray()){
        if (c == '(')
            stack.push(')');
        else if (c == '{')
            stack.push('}');
        else if (c == '[')
            stack.push(']');
        else if (stack.isEmpty() || stack.pop() != c)
            return false;
    }
    return stack.isEmpty();
}

That was quite a bit of code, so let’s take a closer look at it. For each character in the array, we check to see which kind of bracket it is. If it is any of the opening ones, we add the corresponding closing one to the stack. (stack.push() adds the data to the stack). If the current character is a closing bracket, that final if statement is the only one that matters. The two lines ‘||’ signify ‘or.’ If the stack is empty or the data at the top of the stack – which is obtained via the pop method – does not equal the current character, we run the ‘return false;’ line. We know that if the stack is empty but there is still a closing bracket to loop for, it means that there is no corresponding opening bracket and the string becomes invalid. If the popped data does not equal the current closing bracket, it means that there is a mismatch between brackets, and that also invalidates the string.

If the loop completes without returning a false value, the only thing left to check for is if the stack is empty. If it is, the string is valid and the return should be true. If not, return false. That completes the problem!