Decide whether each string of brackets is balanced: every bracket closes in the right order with a bracket of the same kind.
Input
The first line has t (1 ≤ t ≤ 100). Each of the next t lines has a string of 1 to 10⁴ characters from ()[]{}.
Output
yes or no for each string.
Examples
Example 1 · Input
4
()[]{}
([)]
{[]}
((
Expected output
yes no yes no
Example 2 · Input
2 )( ()
Expected output
no yes
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Push every opening bracket on a stack.
Hint 2
A closing bracket needs a matching opening one on top of the stack.
Hint 3
At the end, the stack must be empty.
Solution
Show one correct solution (try it yourself first)
partner = {")": "(", "]": "[", "}": "{"}
t = int(input())
for _ in range(t):
stack = []
ok = True
for ch in input():
if ch in "([{":
stack.append(ch)
elif not stack or stack.pop() != partner[ch]:
ok = False
break
print("yes" if ok and not stack else "no")