Theory: Balanced brackets with a stack

Use a stack, the PDA's memory, to check nesting.

What to build

A program that checks whether each line of brackets is balanced.

Requirements

  • Support (), [] and {}; every bracket must close in the right order.
  • Print yes or no for each line.

Input

Line 1: n. Then n lines of brackets (a line may be empty).

Output

n lines.

Constraints

n ≤ 20; lines have at most 60 characters.

Example

Input:

3
([]{})
([)]
((

Output:

yes
no
no

Why it works

The most recent unclosed bracket must close first, which is exactly what the top of a stack gives.

Examples

Example 1 · Input
3
([]{})
([)]
((
Expected output
yes
no
no
Example 2 · Input
2
{[()()]}
}
Expected output
yes
no

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Push each opening bracket; on a closing bracket, the top must be its partner.

Hint 2

At the end the stack must be empty.

Solution

Show one correct solution (try it yourself first)
pairs = {")": "(", "]": "[", "}": "{"}
for _ in range(int(input())):
    stack = []
    ok = True
    for c in input():
        if c in "([{":
            stack.append(c)
        elif not stack or stack.pop() != pairs[c]:
            ok = False
            break
    print("yes" if ok and not stack else "no")

Lesson: Pushdown automata →