Valid Parentheses

The input string is considered as a balanced expression if 

  1. Open brackets must be closed by the same type of brackets. 
  2. Open brackets must be closed in the correct order.

Note that an empty String is also considered valid.

Example 1:
Input: "{()}" → Output: true

Example 2:
Input: "()[]{}" → Output: true

Example 3:
Input: "({]" → Output: false

Example 4:
Input: "([)]" → Output: false

Example 5:
Input: "{[]}" → Output: true

This solution is very useful for compilers to check if the parentheses are balanced or not. The expressions that we will deal with in this problem can consist of three different types of parenthesis:

  • (),
  • {} and
  • []

A Stack can be used to check whether the given expression has balanced parenthesis. The program will read one character at a time. If the character is an opening delimiter such as (, {, [ – then it is pushed into the Stack. When a closing delimiter is encountered like ), } or ] – then the stack is popped and compared against the opening delimiter. If they match then the parsing of the String continues. If they do not match, the program indicates that there is a mismatch of the delimiter. A linear-time algorithm based on the stack can be given as follows.

Algorithm:

  • Create a Stack.
  • Convert the input String into a Character array.
  • While the end of the String is not reached, read one character at a time.
    • If the character is an opening symbol (, {, [  then push it into the Stack.
    • If the character is a closing symbol ), }, ]  then if the stack is empty then return false. Otherwise, pop the Stack.
    • If the popped delimiter does not match with the corresponding character from the String then return false. If the current character in the loop is '(' then the popped element must be ')'.
  • At the end of the loop if the Stack is still not empty then return false, which means there are unbalanced parentheses present in the String.

An interesting property about a valid parenthesis expression is that a sub-expression of a valid expression should also be a valid expression. 

Following is the Java implementation of the algorithm:

class Solution {
    public boolean isValid(String s) {
        
        if( s == null || s.isEmpty()){
            return true;
        }
        Stack<Character> stack = new Stack<>();
        int n = s.length();
        int i = 0;
        while( i < n){
            char cur = s.charAt(i++);
            if(cur == '(' || cur == '{' || cur == '['){
                stack.push(cur);
            }else{
                // Closing parentheses found without
                // a matching openning parentheses
                //'')'' or ''}'' or '']'' found before a openning
                if(stack.isEmpty()){
                    return false;
                }
                
                // Closing parentheses should also 
                // have a matching opening parentheses
                if(cur == ')' && stack.peek() != '('){
                    return false;
                }else if(cur == '}' && stack.peek() != '{'){
                    return false;
                }else if(cur == ']' && stack.peek() != '['){
                    return false;
                }
                
                // openning and closing parentheses has matched
                stack.pop();
            }
        }
        
        // If there are unbalanced parentheses present in the String
        if(!stack.isEmpty()){
            return false;
        }
        return true;
    }
}

Complexity analysis

  • Time Complexity: O(n) because we simply traverse the given string one character at a time and push and pop operations on a stack take O(1) time.
  • Space Complexity: O(n) as we push all opening brackets onto the stack and in the worst case, we will end up pushing all the brackets onto the stack. e.g. {[{[(({{.

Categories: Stack

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s