A string contains only the characters ()[]{}. It is balanced if every opening bracket is closed by the same type, in the correct order. Print YES if it is balanced and NO otherwise.
Constraints
- 1 ≤ length ≤ 100000
Input and output
- Input
- One line: the string
- Output
- YES or NO
Examples
Input 1
{[()]}Output
YESNested correctly.
Input 2
([)]Output
NOCrossed.
Show hints
- The most recent unclosed bracket must be closed first.
Show the explanation
Push opening brackets on a stack. For a closing bracket, the stack must be non-empty and its top must be the matching opener; pop it. At the end the stack must be empty (otherwise something was never closed). O(n) time, O(n) space in the worst case.
Original UniCircle question. Last reviewed 21 Oct 2026.