Valid Parentheses | Balanced Parentheses (with Python Code)

A parentheses is said to be balanced if each left parenthesis has its respective right parenthesis to match its pair in a well-nested format.

In computer science, valid parentheses(balanced parentheses) are a notation used to simplify expressions written in an operator-precedence parser by allowing the programmer to explicitly mark the operator precedence and associativity of a given expression. 

Balanced Parentheses play a crucial role while dealing with any programming language and hence, most of the technical interview jumps to check the understanding of the candidate for the same. Checking the valid parentheses in an expression is one of the commonly asked interview questions during technical interviews. To help you get the job in your dream company, let us discuss solutions to this problem with different approaches and examples. But before that, let us understand the valid parentheses problem below. 

What is the Valid Parentheses Problem?

Given a string s containing just the characters '(', ')', '{', '}', '[', and ']', determine if the input string is valid or not.

Note that an input string is valid if:

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

Now that you understand the problem statement correctly let us jump to understanding the solution of the problem in detail below. 

How to Check Valid Parentheses in Expression?

Below are two methods by which you can check valid parentheses in expression:

1) Checking valid parentheses using brute force approach

The first thing that comes to your mind while solving the valid parentheses problem is by using the brute force approach. In this approach, you can make use of recursion, i.e., conditional statements and loop to match the parentheses, and if it returns true, the parentheses are valid; otherwise, not.

Here we make use of the while loop to check the sequence of parentheses and return the output whether the parentheses are valid or not.

Check out the below python code for checking valid parentheses using the brute force approach. 

Python code for brute force approach

class Solution:
   def isValid( self, sequence ):
       '''
       Function to check if sequence contains valid parenthesis
       :param sequence: Sequence of brackets
       :return: True is sequence is valid else False
       '''
       # Replace the proper pairs until sequence becomes empty or no pairs are present
       while True:
           if '()' in sequence :
               sequence = sequence.replace ( '()' , '' )
           elif '{}' in sequence :
               sequence = sequence.replace ( '{}' , '' )
           elif '[]' in sequence :
               sequence = sequence.replace ( '[]' , '' )
           else :
               return not sequence

if __name__ == '__main__':
   sequence = '{[()]}'
   print(f'Is {sequence} valid ? : {Solution().isValid(sequence)}')
   sequence1 = '{[()]}{]{}}'
   print(f'Is {sequence1} valid ? : {Solution().isValid (sequence1)}')

Output

Is {[()]} valid ? : True
Is {[()]}{]{}} valid ? : False

2) Checking valid parentheses using stack

To solve a valid parentheses problem optimally, you can make use of Stack data structure. Here you traverse through the expression and push the characters one by one inside the stack. Later, if the character encountered is the closing bracket, pop it from the stack and match it with the starting bracket. This way, you can check if the parentheses find their respective pair at the end of the traversal and if not, the parentheses are not valid.

Algorithm for optimal approach

1. Declare stack S.
2. Now traverse the string expression using a pointer. 
    if the current pointer is at opening bracket ('(' or '{' or '[') then push it to stack S.
    else the current pointer is at closing bracket (')' or '}' or ']') then pop from the stack 
        if the popped bracket is the matching opening bracket then brackets are valid 
        else brackets are not valid.

After complete traversal, if there is some starting bracket left in the stack then "not valid"

Python code for optimal approach

class Solution:
   def isValid (self, sequence: str):
       '''
       Function to pair if sequence contains valid parenthesis
       :param sequence: Sequence of brackets
       :return: True is sequence is valid else False
       '''
       stack = []
       opening = set('([{')
       closing = set(')]}')
       pair = {')' : '(' , ']' : '[' , '}' : '{'}
       for i in sequence :
           if i in opening :
               stack.append(i)
           if i in closing :
               if not stack :
                   return False
               elif stack.pop() != pair[i] :
                   return False
               else :
                   continue
       if not stack :
           return True
       else :
           return False

if __name__ == '__main__':
   sequence = '{[()]}'
   print(f'Is {sequence} valid ? : {Solution().isValid(sequence)}')
   sequence1 = '{[()]}{]{}}'
   print(f'Is {sequence1} valid ? : {Solution().isValid (sequence1)}')

Output

Is {[()]} valid ? : True
Is {[()]}{]{}} valid ? : False

Time complexity

The time complexity to check the valid parentheses using the optimal solution is O(n), where 'n' is the total number of characters in the expression. It is because we traverse through the sequence only once, and hence, the time complexity is linear in nature.

Similarly, the space complexity for this solution is O(n) as we require the stack of size 'n' to fit the characters of the expression.

Example

Let us consider the below expression for understanding the solution of the valid parentheses problem using stack.

Initially, we will start traversing through the expression and push the open brackets inside the stack data structure, as shown in the below image.

Keep repeating the same process until all the opening brackets are pushed inside the stack, and the pointer reaches forward.

As soon as the pointer reaches the closing brackets, check the top of the stack if the respective opening bracket is the same kind or not. Pop the opening bracket from the stack for matching the pair of parenthesis as shown in the below image.

Keep repeating the same process until all the closing brackets are visited by the pointer as shown in the below image.

At last, if there is any bracket left inside the stack, it means that there is one matching pair of parenthesis left and the expression does not contain the valid parentheses. If all the brackets are popped out of the stack, it means the expression contains the valid parentheses, as shown in the below image.

Conclusion

Brackets play a primary role while programming in any language, especially in array indexing. They are also used in general denotation for tuples, set, and many other data structures. As the brackets are widely used in the field of computer science, interviewers always test the knowledge of the job candidate as its competitive problem involving recursion and stack concepts.

In this article, we studied two different approaches to check whether the expression is the valid parentheses or not along with the python code and example It is highly recommended to understand this problem if you are aiming to crack your dream jobs in any product-based company like Microsoft or Amazon.