Python · Course navigation

Python stacks and balanced parentheses

Use last-in, first-out storage to match nested parentheses.

On this page

Before you start

Lists, loops, and conditions.

Use last-in, first-out storage to match nested parentheses.
Predict the sample output and explain the state changes.
Complete the practice task and check the boundary cases.

The concept

A stack removes the most recently added item first. Opening parentheses are pushed; a closing parenthesis must match an existing opening one.

If a closing parenthesis appears when the stack is empty, fail immediately. After the scan, any remaining openings mean the expression is incomplete. This example ignores non-parenthesis characters.

Code example

Python

def balanced(text):
    stack = []
    for char in text:
        if char == "(":
            stack.append(char)
        elif char == ")":
            if not stack:
                return False
            stack.pop()
    return not stack

print(balanced("(())"))
print(balanced(")("))
assert balanced("")
assert not balanced("(()")

Output

True
False

Example details

Follow the code

Open the walkthrough to inspect the example one step at a time.

Show guided walkthrough

Guided walkthroughReady

1def balanced(text):

2 stack = []

3 for char in text:

4 if char == "(":

5 stack.append(char)

6 elif char == ")":

7 if not stack:

8 return False

9 stack.pop()

10 return not stack

12print(balanced("(())"))

13print(balanced(")("))

14assert balanced("")

15assert not balanced("(()")

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
Start the first call with no unmatched openings.	`stack = []`	—
Push the first opening.	`stack = ['(']`	—
Push the nested opening.	`stack = ['(', '(']`	—
The first closing matches the latest opening.	`stack = ['(']`	—
The second closing matches the remaining opening.	`stack = []`	—
No unmatched openings remain.	`stack = []`	True
The second call starts with a closing parenthesis and an empty stack.	`stack = []`	True
Print the failure.	`stack = []`	True False

Behind the scenes

How Python processes this code

Python runs this source through its interpreter. It creates objects for values and resolves names as each statement runs.

Cost and common mistakes

O(n) time and O(n) worst-case auxiliary space.

Counting opening and closing parentheses alone misses wrong ordering such as )(.
Matching multiple bracket types requires checking the type at the stack top.

Try it yourself

Trace balanced('(()())').

Reveal answer and reasoning

The stack depths are 1, 2, 1, 2, 1, 0, so the result is True.