Check whether every bracket (), [] and {} in a line is closed in the right order. Other characters are ignored.
What to build
A stack-based check that handles three kinds of brackets.
Requirements
- Read a line.
- Print
YESif every bracket is closed in the right order, otherwiseNO.
Input
One line of text.
Output
YES if the brackets are balanced, otherwise NO.
Constraints
The line has at most 10000 characters.
Example
Input:
(a[b]{c})
Output:
YES
Why it works
The most recent opening bracket is always the next one that must be closed, which is exactly the order a stack gives you.
Examples
Example 1 · Input
(a[b]{c})
Expected output
YES
Example 2 · Input
(]
Expected output
NO
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Push opening brackets; each closing bracket must match the top of the stack.
Hint 2
At the end the stack must be empty.
Solution
Show one correct solution (try it yourself first)
text = input()
pairs = {")": "(", "]": "[", "}": "{"}
stack = []
ok = True
for ch in text:
if ch in "([{":
stack.append(ch)
elif ch in ")]}":
if not stack or stack.pop() != pairs[ch]:
ok = False
break
print("YES" if ok and not stack else "NO")