The Syntax Sentinel

An easy Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
easy
Seniority
L3
Asked in
Walmart

Problem

A linter pass over template source needs to flag mismatched brackets before a file ships. Given a string s that may hold any characters, return whether every (), [], and {} pair closes in the correct order, so ([)] is rejected even though the counts match. Characters that aren't brackets don't affect the result, and a string with no brackets is balanced.

Brackets opened and closed. The nesting might be off.

Example 1

Input:

s = "{a + [b * (c - d)]}"

Output:

true

Example 2

Input:

s = "([)]"

Output:

false

Worked solution and explanation

What this really is

Strip the linter costume off and this is the canonical order-sensitive matching problem: every closer has to pair with the most recent unmatched opener of the same type. The tell that separates candidates is whether they reach for a stack or a counter. A counter that just balances open-minus-close looks right on ()() and quietly passes ([)], where the counts are even but the nesting crosses. Get that wrong and your validator green-lights source that won't parse.

Working through it

Step 1: Push each opener

Every time you see (, [, or {, push it. You are recording an obligation: this must be closed later, and before anything opened before it.

Step 2: Match each closer against the top

On ), ], or }, the top of the stack must be the matching opener. If the stack is empty (a closer with nothing open) or the top is the wrong type (crossed nesting), you can fail immediately.

Step 3: Walk past everything else

Letters, digits, spaces, operators: none of them touch the stack. Skipping them is what lets the same routine validate real source, not just bare bracket strings.

Step 4: Check the stack is empty at the end

A leftover opener on the stack means it was never closed. Balanced means the stack is empty when you finish, which is why the empty string and a bracket-free string both come back True.

The solution

Stack-based bracket matching
def is_balanced(s: str) -> bool:
    stack = []
    matching = {')': '(', ']': '[', '}': '{'}
    for ch in s:
        if ch in '([{':
            stack.append(ch)
        elif ch in ')]}':
            if not stack or stack[-1] != matching[ch]:
                return False
            stack.pop()
    return not stack

One pass, fail fast on the first crossed or orphaned bracket.

Counter approach
Track an integer per bracket type, increment on open, decrement on close. Balances the counts but has no memory of order, so '([)]' passes even though it is invalid.
Stack approach
The stack remembers which opener is still waiting. '([)]' fails the moment ')' meets a '[' on top, because the types cross.

Common follow-up questions