Python stacks and balanced parentheses

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

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

Explanation

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.

Explore the dry run

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

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.

Python stacks and balanced parentheses

Explanation

Follow the example

Cost and common mistakes

Try it yourself

Further reading