Given a string of parentheses, checking if the parentheses combination is valid is a popular coding interview question. And over the next few minutes, you’ll learn the technique to solve this question and also code up a Python function to validate a given string.
What is the Valid Parentheses Problem?
Let’s start our discussion by answering the question, what is the valid parentheses problem? A valid parentheses string satisfies the following two conditions: Here are a few examples of valid and invalid parentheses strings. In our problem-solving approach, the stack is the data structure that’ll play a pivotal role. Let’s review the basics of a stack in the next section.
The Stack Data Structure Revisited
The stack is a last in first out (LIFO) data structure, where you can add elements to the top of the stack and also remove them from the top of the stack. We’ll use the following two rules to come up with a set of operations that we can perform on the parentheses string.
Push all opening brackets onto the stack. If you come across a closing bracket, pop off the stack top.
Let’s proceed to solve the valid parentheses checking problem.
How to Check for Valid Parentheses
Putting together all the observations from the above examples, we have the following.
Check the length of the parentheses string: If odd, the string is Invalid
As every opening bracket must have a closing bracket, a valid string should contain an even number of characters. If the length of the string is odd, you can conclude right away it has an invalid combination of parentheses. Next, let’s see how we can tackle when the number of characters in the string is even
The length of the parentheses string is even: what next?
Step 1: Traverse the string from left to right. Let’s call the string test_str, and the individual characters in the string char. Step 2: If the first character char is an opening 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 character ( is an opening bracket; push it to the stack. The second character ) is a closing bracket; pop off the stack top, which happens to be ) – an opening bracket of the same type. Proceed to the next character. The third character ] is a closing square bracket, and you should pop off the stack top again. However, as you can see, the stack is empty—which means there is no 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 ‘}’, ‘]’, ‘)’ as the values. You can use the .keys() method to access individual keys in the dictionary. Let’s use all that we’ve learned to write the definition of the is_valid() function.
Understanding the Function Definition
Read through the following code cell containing the function definition. You can see that we’ve used the steps in the flowchart in tandem with the above explanation. In addition, we’ve also added a docstring including:
a short description of the function the arguments in the function call the return values from the function
▶ You may use help(is_valid) or is_valid.doc to retrieve the docstring. The Python function is_valid checks if the parentheses string is valid, and it works as follows.
The function is_valid takes in one parameter, test_str which is the parentheses string to be validated. It returns True or False depending on whether or not the string test_str is valid. Here, stack is the Python list that emulates the stack. And par_dict is the Python dictionary, with opening brackets as the keys and closing brackets as the corresponding values. While traversing the string, if we run into any condition that makes the parentheses string invalid, the function returns False and exits. After traversing all the characters in the string, stack == [] checks if stack is empty. If yes, test_str is valid, and the function returns True. Else, function returns False.
Now, let’s go ahead and make a few function calls to verify that our function works correctly. From the code snippet above, we can conclude that the function works as expected!
Conclusion
Here’s a quick summary of what you’ve learned.
Firstly, you were introduced to the problem of valid parentheses checking. Next, you learned an approach to solving the problem using the stack as the data structure of choice. You then learned how to validate a parentheses combination using a Python dictionary: with opening brackets, the keys, and the corresponding closing brackets as the values. Finally, you defined the Python function to check if a given parentheses string is valid.
As a next step, try to code the problem on Geekflare’s online Python editor. Feel free to revisit this guide if you need help! Check out more Python tutorials. Happy coding!
