In this tutorial, you’ll learn to **check for valid parentheses** in Python.

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?*

Given a string containing the characters simple parentheses, curly and square braces:

`() [] {}`

, you have to check whether or not the given parentheses combination is valid.

A valid parentheses string satisfies the following two conditions:

- Every opening bracket must have a
**matching**closing bracket of the same type. - The brackets should be closed in the
**correct**order.

Here are a few examples of valid and invalid parentheses strings.

```
test_str = "{}]" --> INVALID, ] was never opened
test_str = "[{}]" --> VALID
test_str = "[]" --> VALID
test_str = "[]{}" --> VALID
test_str = "[{]}" --> INVALID, brackets closed incorrectly!
```

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.

When you

addan element to the stack top, you perform apushoperation, when youremove an element from the stack top, you perform apopoperation.

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.

```
# len(test_str) = 3 (odd); ] does not have an opening [
test_str = "{}]"
# len(test_str) = 3 (odd); ( does not have a closing )
test_str = "[(]"
# len(test_str) = 5 (odd); there's a spurious )
test_str = "{())}"
```

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.

```
def isValid(test_str):
'''Check if a given parentheses string is valid.
Args:
test_str (str): The parentheses string to be validated
Returns:
True if test_str is valid; else False
'''
# len(test_str) is odd -> invalid!
if len(test_str)%2 != 0:
return 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:
# closing bracket without matching opening bracket
if stack == []:
return False
# if closing bracket -> pop stack top
open_brac = stack.pop()
# not matching bracket -> invalid!
if char != par_dict[open_brac]:
return False
return stack == []
```

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.

```
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 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!