How to Check for Valid Parentheses in Python

In this educational, you’ll be told to test for legitimate parentheses in Python. 

Given a string of parentheses, checking if the parentheses mixture is legitimate is a well-liked coding interview query. And over the following couple of mins, you’ll be told the method to remedy this query and likewise code up a Python serve as to validate a given string.

What is the Valid Parentheses Problem?

 Let’s get started our dialogue by way of answering the query, what’s the legitimate parentheses subject?

Given a string containing the characters easy parentheses, curly and sq. braces: () [] , you may have to test whether or not or no longer the given parentheses mixture is legitimate.

A legitimate parentheses string satisfies the next two stipulations:

1. Every opening bracket will have to have a matching final bracket of the similar kind.
2. The brackets will have to be closed in the proper order.

Here are a couple of examples of legitimate and invalid parentheses strings.

test_str = "]" --> INVALID, ] used to be by no means opened
test_str = "[]" --> VALID
test_str = "[]" --> VALID
test_str = "[]" --> VALID
test_str = "[]" --> INVALID, brackets closed incorrectly!

In our problem-solving method, the stack is the knowledge construction that’ll play a pivotal function. Let’s assessment the fundamentals of a stack in the following segment.

The Stack Data Structure Revisited

The stack is a remaining in first out (LIFO) information construction, the place you’ll be able to upload components to the highest of the stack and likewise take away them from the highest of the stack.

When you upload a component to the stack best, you carry out a push operation, whilst you remove a component from the stack best, you carry out a pop operation.

We’ll use the next two regulations to get a hold of a suite of operations that we will carry out at the parentheses string.

• Push all opening brackets onto the stack.
• If you return throughout a final bracket, pop off the stack best.

Let’s continue to remedy the legitimate parentheses checking subject.

How to Check for Valid Parentheses

Putting in combination all of the observations from the above examples, we now have the next.

Check the duration of the parentheses string: If extraordinary, the string is Invalid

As each opening bracket will have to have a final bracket, a sound string will have to comprise an even selection of characters. If the duration of the string is extraordinary, you’ll be able to conclude immediately it has an invalid mixture of parentheses.

# len(test_str) = 3 (extraordinary); ] does no longer have a gap [
test_str = "]"

# len(test_str) = 3 (extraordinary); ( does no longer have a final )
test_str = "[(]"

# len(test_str) = 5 (extraordinary); there is a spurious )
test_str = "())"

Next, let’s see how we will take on when the selection of characters in the string is even

The duration of the parentheses string is even: what subsequent?

Step 1: Traverse the string from left to proper. Let’s name the string test_str, and the person characters in the string char.

Step 2: If the primary persona char is a gap bracket (, {, or [, push it to the top of the stack and proceed to the next character in the string.

Step 3: Now, check if the next character (char) is an opening or a closing bracket.

Step 3.1: If it’s an opening bracket, push it again onto the stack.

Step 3.2: If you encounter a closing bracket instead, pop off the stack top, and proceed to step 4.

Step 4: Here again, there are 3 possibilities based on the value popped off the stack:

Step 4.1: If is an opening bracket of the same type, loop back to step 3.

Step 4.2: If it is an opening bracket of a different type, you can again conclude that it is not a valid parentheses string.

Step 4.3: The final possibility is that the stack is empty. Again, this is the case of an invalid string, as you’ve run into a closing bracket that doesn’t have a matching opening bracket.

Valid Parentheses String Examples Walkthrough

Now let’s take three examples and walk through the above steps.

📑 If you’ve already gotten the hang of how this works, feel free to skip to the next section.

#1. As a first example, let test_str = "{()".

• { is the first character, and it’s an opening bracket, so you push it to the stack.
• The next character ( is also an opening bracket, so go ahead and push it onto the stack as well.
• The third character in the string ) is a closing bracket, so you have to pop off the stack top, which returns (.
• At this point, you’ve reached the end of the string. But the stack still contains the opening { , which was never closed. So the given parentheses string test_str is invalid.

#2. In this second example, let test_str = "()]"

• The first persona ( is a gap bracket; push it to the stack.
• The 2nd persona ) is a final bracket; pop off the stack best, which occurs to be ) – a gap bracket of the similar kind. Proceed to the following persona.
• The 3rd persona ] is a final sq. bracket, and also you will have to pop off the stack best once more. However, as you’ll be able to see, the stack is empty—this means that there is not any matching opening bracket [. Hence, this string is invalid.

#3. In this final example, test_str = "()".

• The first two characters ( are opening brackets, so push them onto the stack.
• The third character is a closing ), so pop off the stack top – (.
• The next character is a closing curly brace, and when you pop the stack top, you get – an opening curly brace.
• After you have traversed the entire string, the stack is empty and test_str is valid! ✅

📌 I’ve put together the following flowchart outlining the steps in the valid parentheses checking problem. You may save it for quick reference!

In the next section, let’s see how to translate our concept to Python code.

Python Program to Check for Valid Parentheses

In Python, you can use the list to emulate a stack.

You can use the .append() method to add elements to the end of the list. This is similar to pushing to the top of the stack.

The .pop() method returns the last element from the list, and this is similar to the popping off the top of the stack – to remove the last-added element.

So you now know how to implement the push and pop operations on a Python list, emulating the stack.

As a next step, let’s answer the question: how to differentiate between opening and closing brackets?

Well, you can use a Python dictionary – with the opening brackets '', '[', '(' as the keys of the dictionary and the corresponding closing brackets '', ']', ')' because the values. You can use the .keys() means to get admission to person keys in the dictionary.

Let’s use all that we’ve realized to write the definition of the is_valid() serve as.

Understanding the Function Definition

Read thru the next code mobile containing the serve as definition. You can see that we’ve used the stairs in the flowchart in tandem with the above clarification.

In addition, we’ve additionally added a docstring together with:

• a brief description of the serve as
• the arguments in the serve as name
• the go back values from the serve as

▶ You might use assist(is_valid) or is_valid.__doc__ to retrieve the docstring.

def isValid(test_str):
  '''Check if a given parentheses string is legitimate.

  Args:
    test_str (str): The parentheses string to be validated
  
  Returns:
    True if test_str is legitimate; else False 
  '''
  # len(test_str) is extraordinary -> invalid!
  if len(test_str)%2 != 0:
    go back False
  # initialize parentheses dict
  par_dict = '(':')','':'','[':']'
  stack = []
  for char in test_str:
    # push opening bracket to stack
    if char in par_dict.keys():
      stack.append(char)
    else:
      # final bracket with out matching opening bracket
      if stack == []:
          go back False
      # if final bracket -> pop stack best
      open_brac = stack.pop()
      # no longer matching bracket -> invalid!
      if char != par_dict[open_brac]:
        go back False
  go back stack == []

The Python serve as is_valid tests if the parentheses string is legitimate, and it really works as follows.

• The serve as is_valid takes in one parameter, test_str which is the parentheses string to be validated. It returns True or False relying on whether or not or no longer the string test_str is legitimate.
• Here, stack is the Python listing that emulates the stack.
• And par_dict is the Python dictionary, with opening brackets because the keys and shutting brackets because the corresponding values.
• While traversing the string, if we run into any situation that makes the parentheses string invalid, the serve as returns False and exits.
• After traversing all of the characters in the string, stack == [] tests if stack is empty. If sure, test_str is legitimate, and the serve as returns True. Else, serve as returns False.

Now, let’s move forward and make a couple of serve as calls to test that our serve as works appropriately.

str1 = '[]'
isValid(str1)
# Output: True

str2 = '(('
isValid(str2)
# Output: False

str3 = '[()]'
isValid(str3)
# Output: True

str4 = '[)]'
isValid(str4)
# Output: False

str5 = '[[]'
isValid(str5)
# Output: False

From the code snippet above, we will conclude that the serve as works as anticipated!

Conclusion 🧑‍💻

Here’s a handy guide a rough abstract of what you’ve realized.

• Firstly, you had been presented to the issue of legitimate parentheses checking.
• Next, you realized an method to remedy the issue the use of the stack as the knowledge construction of selection.
• You then realized how to validate a parentheses mixture the use of a Python dictionary: with opening brackets, the keys, and the corresponding final brackets because the values.
• Finally, you outlined the Python serve as to test if a given parentheses string is legitimate.

As a subsequent step, check out to code the issue on Geekflare’s on-line Python editor. Feel unfastened to revisit this information if you wish to have assist!

Check out extra Python tutorials. Happy coding!🎉