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
yesornofor 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")