Balanced parentheses in Python

Why it matters

Every compiler and code editor checks that brackets close in the right order. Python does too. If you write print("hi" and forget the closing parenthesis, Python stops and names the bracket that was never closed. The error message comes from a stack-based check, the same idea this lesson builds.

Bracket matching is also one of the most common stack questions in interviews, because the solution is short, the idea is precise, and it leads to several harder problems.

This lesson builds the bracket check from first principles. You will see why a simple counter fails, why a stack succeeds, and how the same pattern solves postfix calculation and the longest valid run of brackets.

Words you will need

• Bracket: one of the symbols (, ), [, ], { and }. An opener is an opening bracket. A closer is a closing bracket.
• Pair: an opener and the closer that matches it. ( pairs with ), [ with ], and { with }.
• Balanced: a string is balanced when every opener has a matching closer, and the pairs do not cross each other.
• Nesting: a pair placed inside another pair, such as the [ and ] inside ( ) in ([]).
• Index: the position of a character in a string. The first character is at index 0.
• Dictionary: a table that maps keys to values. You write one with curly braces, as in {")": "("}, and look up a value with square brackets, as in PAIRS[")"].
• enumerate: a built-in function that gives each item together with its index. for i, ch in enumerate(s) visits every character and its position.
• Postfix notation: a way to write arithmetic where each operator comes after its two operands, such as 2 3 + for 2 plus 3.

The first principle: nesting closes in reverse

Think of a set of nested boxes, the kind you can pack one inside another. You can close the outer box only after the inner box is closed. If you have opened a small box inside a big one, the small one must close first. The box you opened most recently is the box you must close first.

That is exactly last in, first out. Each opener is a box you have opened and not yet closed. The stack holds those open boxes, with the most recent one on the right. When a closer arrives, it must close the box on top. If it closes a different kind of box, the nesting is broken. If nothing is open, the closer has nothing to close.

So the rule for a balanced string is this. Read the characters left to right. Each opener goes onto the stack. Each closer must match the item on top of the stack, and that item is removed. At the end, the stack must be empty, which means no opener was left without a closer.

Why a counter is not enough

A beginner's first idea is to count. Add 1 for each opener, subtract 1 for each closer, and check that the count is 0 at the end. This works for one kind of bracket. It fails for two kinds, and it fails in a way that is easy to miss.

Take the string ([)]. It has two openers and two closers, so a count of openers and closers agrees. A counter says the string is balanced. But the pairs cross. The [ opened after (, so it should close before ( does. Here ) arrives while [ is still open. The counter cannot see that, because it knows only how many brackets are open, not which ones.

The stack remembers which bracket is open. When ) arrives, the top of the stack is [, so the check fails. That single difference is why the stack is the right tool.

Here is a quick comparison.

The counter is right in the first, third and fourth rows, and wrong in the second. The stack is right in every row.

The algorithm, step by step

To check any string, follow these steps.

1. Create an empty list to use as a stack.
2. Read the characters from left to right.
3. On an opener, append it to the stack.
4. On a closer, check the stack. If it is empty, the string is not balanced, because nothing is open to close. Otherwise, pop the top and check that it is the matching opener. If it is not, the string is not balanced.
5. When the characters run out, the string is balanced only if the stack is empty.

Step 5 is easy to forget. A string like (( never triggers a mismatch, so only the final check catches it. Without it, (( would be called balanced.

Step 4 has two checks, and both matter. The empty check stops a closer from popping nothing. The match check compares the kinds. For example, (] has an opener and a closer, but they are not a pair.

A longer trace

Try a string with more structure: {[()()]}. The stack goes up and down, but it never has a closer that meets the wrong opener.

The stack reached three items at its highest point, and it was empty at the end. The two pairs () and () sit side by side inside the square brackets. Each one opens and closes before the next one starts, and the stack shows that by going back down to { [ between them.

Worked example 1: trace two strings

Trace {[()]} first. The stack is written from bottom to top.

The stack is empty at the end, so the string is balanced. Each closer met the opener that was waiting for it, in the reverse order of opening.

Now trace ([)].

The check stops at the third character. It never reaches the fourth. A check that stops early is fine, because one mistake is enough to answer no.

The bracket checker in Python

Here is the complete program. The first line of input says how many strings follow. Each string is then checked on its own line of output.

Type this into the Input box:

5
{[()]}
([)]
((
())
]

YES
NO
NO
NO
NO

The dictionary PAIRS maps each closer to the opener it needs. PAIRS[")"] is "(". One lookup replaces a separate test for each pair.

OPENERS is a string of three characters. The test ch in OPENERS is true when ch is one of them. The same test works on any string, so it is a short way to say "is this an opener".

The for loop visits each character. The first if handles openers and pushes them. The elif handles closers. Inside it, the code checks not stack before it pops. Popping an empty list raises an exception, so the check protects the program.

Now the input. int(input()) reads the number 5. Then input() reads one line at a time. strip() removes spaces at both ends of the line. Each bracket string here has no spaces, so the line is the string itself.

The last line, return not stack, is the final check. An empty list counts as false, so not stack is true when nothing is left open.

Check the five answers against the rules. {[()]} is balanced, so YES. ([)] crosses the pairs, so NO. (( never closes, so NO. ()) has a closer with nothing to close at its position, so NO. ] is a closer on an empty stack, so NO.

Step through the animation above with the string ([)]. Watch the stack at the moment ) arrives, and notice that the top is [, not (. That single fact is the whole reason the check fails.

What happens inside

Each character is handled once. For each one, the program either pushes it, pops it, or does nothing. A push or pop takes constant time on average, so the whole check is O(n) for a string of n characters.

The stack holds the openers that are still waiting. Its size is the number of open brackets at the worst moment. For ((((((, the stack grows to six. For ()()(), it never grows above one. So the space used is O(n) in the worst case and much smaller in friendly input.

Python does not need a wrapper type to store characters. Each character in the stack is a string of length 1, and the list holds it directly.

Notice what you do not need. You do not need to scan it twice. One pass with one stack is enough.

Worked example 2: say where the string goes wrong

A yes or no answer is useful, but a real tool, such as a compiler, tells you where the problem is. The next program reports the first problem it finds. This change needs only two small edits to the basic algorithm: store the position of each opener, not the character, and describe the failure when it happens.

Type this into the Input box:

([)]

mismatch at index 2: ) closes [ from index 1

The stack now holds positions, which are whole numbers, instead of characters. To find the character, the code reads it from the string: s[open_at]. This works because the position is a fixed address in the text.

The line if stack: near the end deserves a close look. Why stack[0] and not stack[-1]? The list's right end is the most recent opener, which is the top of the stack. Index 0 is the left end, the oldest opener that is still open. The message names the earliest problem, which is the most useful one for the reader.

Here are the four results from the program, one input each. Each line is the real output.

The mismatch message uses the index of the closer and the index of the opener it failed to match. Those two numbers together tell the reader exactly which pair is at fault. When you build a tool like this, always report both positions.

Worked example 3: the same stack in postfix arithmetic

Stacks also evaluate arithmetic. In normal notation, you write 2 + 3 * 4, and the rules of precedence decide that * happens first. Postfix notation avoids those rules. You write each operator after its two operands: 2 3 4 * + means 2 plus the product of 3 and 4. Computers find postfix easy because a stack does the work.

The rule is simple. Read the tokens from left to right. A number goes onto the stack. An operator pops the two most recent numbers, applies the operator, and pushes the answer. At the end, the stack holds one number, which is the result.

Trace 5 1 2 + 4 * + 3 -. This is the expression 5 + (1 + 2) * 4 - 3, written in postfix. Here is the stack after each token.

The result is 14. The order matters for subtraction and division. The right operand is the one popped first, so b is the top and a is below it. The program writes a - b, which is the left operand minus the right.

Type this into the Input box. The line holds the tokens, separated by spaces.

5 1 2 + 4 * + 3 -

14

The operator module from the standard library holds the arithmetic functions, such as operator.add. The dictionary OPS maps each operator symbol to its function. In Python a function is a value like any other, so you can store it in a dictionary and call it later. OPS[tok](a, b) looks up the function for the token and calls it with the two operands.

The code does not need a long type or a size limit. Python integers have no fixed size. The expression 2 ** 100 prints the exact value 1267650600228229401496703205376, which has 31 digits.

Postfix needs no parentheses and no precedence rules, because the order of the tokens already says which operator applies to which operands. Many calculators work this way. A stack is all the extra machinery it needs.

Notice how the bracket check and the postfix evaluator share one shape. Each one pushes something when it sees one kind of token, and pops when it sees another kind. The stack is the memory of what is still waiting. This pattern shows up over and over.

Worked example 4: how many brackets to add

Suppose a string is not balanced, and you may add brackets to fix it. How many do you need? This question has a neat answer when the string uses only round brackets, and a counter is enough here, because there is only one kind of pair.

Read the string left to right. Keep two numbers. waiting counts ( that are still waiting for a ). add_before counts ) that had no ( to match. A ) with a waiting ( uses it up. A ) with nothing waiting adds one to add_before, because a ( must be added before it. At the end, each ( still waiting needs a ) added after it. The answer is add_before plus waiting.

Type this into the Input box:

))((

4

For ))((, the first two ) have nothing waiting, so add_before becomes 2. The two ( are both still waiting at the end, so waiting is 2. The answer is 4: add two ( at the front and two ) at the end, to get (())(()). The counter does the work of the stack here, because with one kind of bracket, knowing how many are open is enough.

The variable is named waiting and not open. A name such as open would hide Python's built-in open function for the rest of the program. Choosing names that do not match built-in names avoids that surprise.

This program does not work for ([)], which needs a stack. The counter always treats any ( as a match for any ), so it cannot see the mismatch. Use a stack whenever more than one kind of bracket is involved.

Worked example 5: the longest valid run

A harder question asks for the length of the longest part of the string that is balanced. In ()((), the balanced parts are () at the start and () in the middle, so the answer is 2. The stack can track this if it stores positions and uses a base marker.

The trick is to keep, in the stack, the position just before the current run of valid brackets. Start the stack with -1, which stands for the position before the string begins. For each (, push its position. For each ), pop. If the stack is now empty, the ) could not be matched, so it becomes the new base: push its position. Otherwise, the run of valid brackets runs from the position on top of the stack plus one, to the current position, so its length is the current index minus the top.

Type this into the Input box, then run the program.

()(()

2

Trace it with indexes. The list is written from bottom to top. Index 0 is (, so push 0. The stack is [-1, 0]. Index 1 is ), so pop 0. The stack is [-1], not empty, so the length is 1 - (-1) = 2. Index 2 is (, push 2: [-1, 2]. Index 3 is (, push 3: [-1, 2, 3]. Index 4 is ), pop 3: [-1, 2]. The length is 4 - 2 = 2, which is the run () at positions 3 and 4. The best is 2.

Try )()()) as well. The first ) at index 0 pops the base marker, leaves the stack empty, and pushes 0 as the new base. Then the first () gives length 2, and the second () joins it to make a run of length 4. The last ) at index 5 becomes a new base. The best run has length 4, so the program prints 4 for that input.

Common mistakes

These are the mistakes that beginners make most often. For each one, the message you will see and the fix are listed.

Reading the top of an empty list. Suppose you write stack[-1] on an empty list. The list has no position -1, so Python raises an error.

stack = []
print(stack[-1])

Traceback (most recent call last):
  File ".../empty_top.py", line 2, in <module>
    print(stack[-1])
          ~~~~~^^^^
IndexError: list index out of range

The fix is to check if stack: before you read the top.

Calling peek on a list. Python lists have no peek method, so the call raises an AttributeError. The fix is stack[-1], after the check.

stack = ["("]
stack.peek()

Traceback (most recent call last):
  File ".../peek_list.py", line 2, in <module>
    stack.peek()
    ^^^^^^^^^^
AttributeError: 'list' object has no attribute 'peek'

Popping without checking. The loop below pops for each closer without checking the list first. The second ) finds an empty list.

stack = []
for ch in "())":
    if ch == "(":
        stack.append(ch)
    else:
        stack.pop()

Traceback (most recent call last):
  File ".../popping.py", line 6, in <module>
    stack.pop()
    ~~~~~~~~~^^
IndexError: pop from empty list

The check if not stack: return False prevents this. Put it before every pop. The folder in the file path is shown as ..., and it will differ on your machine.

Returning True after the loop. Writing return True instead of return not stack makes (( count as balanced. The openers left on the stack are the proof that something never closed.

Comparing with is. The is operator checks whether two names refer to the same object. It does not check whether the values are equal. Python warns about it when one side is a literal string.

ch = "("
print(ch is "(")
print(ch == "(")

.../is_check.py:2: SyntaxWarning: "is" with 'str' literal. Did you mean "=="?
  print(ch is "(")
True
True

Compare values with ==. The warning is the reason to avoid is here, because the result of is depends on how Python stores the objects.

Comparing the popped opener with the closer. The check if stack.pop() == ch compares an opener with a closer, which are never equal. The check must look up the expected opener first: stack.pop() != PAIRS[ch].

Using a counter with more than one kind. A counter cannot tell ([)] from ([]), as the table near the start of the lesson showed. Use a stack.

Forgetting the base marker. In the longest-run program, if you start with an empty list, a ) at the start makes stack.pop() raise an error, and a run that empties the stack, such as (), is never measured, so the answer is 0 instead of 2. The -1 marker makes the arithmetic work from the start of the string.

Debugging walkthrough

Suppose the bracket checker says (() is balanced. It is not, so something is wrong. Trace it with a print statement inside the loop, or on paper.

Start with an empty list. The first ( is appended, so the stack is (. The second ( is appended, so it is ( (. The ) pops the top, so it is (. The loop ends with one opener still on the stack. The final return not stack gives False, which is correct.

If your version printed balanced instead, check the last line. It is the most common place for this bug. Also check that the loop really pops on each closer. A typical mistake is writing stack[-1] where stack.pop() belongs, which leaves the opener on the stack and gives the wrong result for some strings.

A second kind of bug is a typo in a rule. Suppose the square-bracket entry of PAIRS said "]": "(" by mistake. Then [] fails, because ] no longer matches [, and the program prints NO for a string that should be YES. Testing each pair on its own, with (), [] and {}, finds this in seconds. Test the simple pairs before the long strings.

A second useful check is to print the stack after each character. The next program prints the positions of the open brackets after the first three characters of (([.

[0, 1, 2]

The list prints from the bottom to the top, so the top, position 2, is the last item. The bottom is the first item, position 0, which is the first unclosed opener. Printing the stack shows you the position of each waiting opener, so you can see at once which one a closer should have matched.

Variations and edge cases

Test these edge cases with every bracket checker you write. The table gives the answer the checker in worked example 1 gives for five short inputs.

Each row is one case that a checker must get right. Run all five, plus your own, before you trust a checker.

The empty string. Nothing is open and nothing is closed, so the answer is balanced. The loop never runs, and the final check finds an empty stack.

Only openers. ((( is never balanced. The final check catches it.

Only closers. ))) fails on the first character, because the stack is empty.

Crossed pairs. ([)] and {(}) both fail. Test strings where the pairs cross, not only strings with missing brackets.

Nested pairs that look close. [()] is balanced, but [(]) is not. A quick glance at the counts gives the same answer for both, so these are good test cases for the stack.

Other characters. The checker above assumes the input has only brackets. Real text has letters and spaces too. The checker already skips them, because the if and elif branches act only on brackets. So f(x) + [1] is treated as balanced.

Interview view

The interview version of this problem is often called "valid parentheses". The interviewer usually expects the stack, a clear statement of the rule, and attention to the edge cases. A strong answer names the rule first: "Each closer must match the most recent unclosed opener, which is a stack." Then the answer gives the code, then the two checks at the end, then the complexity: O(n) time and O(n) space.

When you explain this on a whiteboard, say three things in order. First, the rule: each closer must match the newest open bracket. Second, the stack actions: append on an opener, and pop on a closer after an empty check. Third, the final check on the stack. Then trace one bad string, such as ([)]. Most interviewers are satisfied with the reasoning before the code is finished.

Expect follow-ups. "Can you return the minimum number of brackets to add?" The answer uses the counter from worked example 4 when one kind is involved, and a stack when there are several. "What is the longest valid substring?" The answer uses the base-marker method from worked example 5. "Can you do it without extra space?" For the general check, a stack is the usual answer. For one kind of bracket, two counters do the job in constant space. Say which case you are in, and explain why the stack is needed when there are several kinds.

Brackets in real error messages

Your tools report bracket problems in their own words, and those words make more sense once you know how the checker works. Python's parser keeps its own stack of open brackets, and it reports the bracket it could not close.

Suppose a line of Python is missing its closing parenthesis. The file below has one call that never closes.

print("hi"

Python reports this:

  File ".../missing_close.py", line 1
    print("hi"
         ^
SyntaxError: '(' was never closed

The message names the bracket, (, and the caret points at it. The first unclosed opener is the one the checker in worked example 2 would report.

A second error has a closer that matches nothing:

x = (a[1] + len(a))}

Python reports SyntaxError: unmatched '}', which names the closer that has no opener.

A third line has two openers and one closer, so one ( stays open at the end of the line:

total = (price[2] * (tax + 1)

Python reports SyntaxError: '(' was never closed and points at the ( at index 8, the first opener that never closes. The checker would print first unclosed opener at index 8 for the same string.

Real-world uses

Compilers and interpreters. When you write a program, the parser checks that the brackets in each block match. A missing closing bracket is reported at the point where the parser found the problem.

Editors. Code editors highlight the bracket that matches the one under your cursor. Finding it means walking through the text with a stack.

Data formats. JSON, XML and HTML use nested tags and brackets. A checker for these formats uses the same stack idea, with the tag name in place of the bracket kind.

Math expressions. Calculators and spreadsheets turn the text you type into postfix form, then evaluate it with a stack.

Complexity summary

The minimum-additions version uses constant space, because one kind of bracket needs only two counters. The others need a list used as a stack, whose size can reach n in the worst case.

Practice

Try each exercise on paper before you open its answer.

1. Trace {[(])} with the stack and state the step where the check fails.

Show the answer

The stack after {, [, ( is { [ (. The next character ] pops (, which does not match ]. The check fails at the fourth character, which is ].

2. Predict the output of the bracket checker for the input (((, then for ))).

Show the answer

((( prints NO, because three openers remain on the stack at the end. ))) prints NO too, because the first ) finds an empty stack and returns false at once.

3. Write a function that returns True when the string is balanced and contains only round brackets, using a counter and no stack. Explain why it is correct.

Show the answer

def balanced_round_only(s):
    waiting = 0
    for ch in s:
        if ch == "(":
            waiting += 1
        elif ch == ")":
            if waiting == 0:
                return False
            waiting -= 1
    return waiting == 0

With one kind, the only question at each closer is whether an opener is waiting. A counter answers that question as well as a stack does. The call balanced_round_only("(()())") returns True, and balanced_round_only("())(") returns False.

4. For the input )()()), use the longest-valid method and write down the list after each character.

Show the answer

Start with [-1]. Index 0 ) pops -1, the list is empty, so append 0: [0]. Index 1 ( appends: [0, 1]. Index 2 ) pops 1: [0], length 2 - 0 = 2. Index 3 ( appends: [0, 3]. Index 4 ) pops 3: [0], length 4 - 0 = 4. Index 5 ) pops 0: empty, so append 5: [5]. The answer is 4.

5. Change the bracket checker so that it returns the number of pairs in a balanced string. For ([])() the answer is 3, because three openers each found a closer. Return -1 for an unbalanced string.

Show the answer

def count_pairs(s):
    stack = []
    pairs = 0
    for ch in s:
        if ch in "([{":
            stack.append(ch)
        else:
            if not stack:
                return -1
            if stack.pop() != PAIRS[ch]:
                return -1
            pairs += 1
    return pairs if not stack else -1

Each successful pop adds one to pairs. This version needs PAIRS from the checker in worked example 1. The call count_pairs("([])()") returns 3, and count_pairs("(]") returns -1.

6. Predict the answer of the postfix evaluator for the tokens 3 4 + 2 *, then check it.

Show the answer

The answer is 14. The + makes 7, and the * makes 7 times 2, which is 14. Running the evaluator from worked example 3 with the input 3 4 + 2 * prints 14.

7. Explain why the code checks if not stack before stack.pop(), and show the error that appears if the check is removed for the input ()).

Show the answer

Without the check, the second ) pops an empty list. Python raises IndexError: pop from empty list. The check returns False before the pop, so the list is never popped when it is empty.

8. Write a function that returns the index of the first closer that breaks the rule, or -1 if none does. For (()], the answer is 3, because ] meets (.

Show the answer

def first_bad_closer(s):
    stack = []
    for i, ch in enumerate(s):
        if ch in "([{":
            stack.append(ch)
        elif ch in ")]}":
            if not stack:
                return i
            if stack.pop() != PAIRS[ch]:
                return i
    return -1

The function reports the closer's index, not the opener's. An unclosed opener at the end is not a bad closer, so for (() it returns -1.

9. Given the input (a+b)*[c-d], decide whether the brackets are balanced if you ignore letters, digits and operators. Explain why the checker already skips them.

Show the answer

The string is balanced. The checker's if and elif branches act only on brackets. Any other character matches neither branch, so the loop skips it without a change. Only the brackets decide the answer, so the letters and operators cannot break the match.

10. Write a function max_depth(s) that returns the deepest nesting level of a balanced string. For (()(())), the answer is 3.

Show the answer

def max_depth(s):
    depth = 0
    best = 0
    for ch in s:
        if ch in "([{":
            depth += 1
            best = max(best, depth)
        elif ch in ")]}":
            depth -= 1
    return best

The depth is the stack size, so this function keeps only a number, not the stack. It works only for strings that are already balanced. Without that promise, a closer can drive the depth below zero.

What you now know

• A string is balanced when every opener closes in reverse order, and the stack is the tool that remembers which opener is waiting.
• A counter cannot tell ([)] from ([]), so use a stack whenever more than one kind of bracket is involved.
• Check the stack for emptiness before each pop, and check it again at the end.
• The same push and pop pattern evaluates postfix arithmetic. The right operand is the top, and it is popped first.
• For one kind of bracket, two counters can replace the stack.
• The longest valid run uses a stack of positions with a base marker of -1.
• The most useful error reports give the position of both the closer and the opener it failed to match.

The next lesson uses a stack for a different job. It looks at each number in a list and finds the next larger number, in one pass.