Заклинание из скобок

В одной игре дверь в подземелье открывается заклинанием — строкой из скобок. Дверь принимает заклинание только если оно «аккуратно вложено»: каждая открывающая скобка когда‑то закрывается скобкой того же типа, и закрытия идут в правильном порядке.

Скобки бывают трёх видов: (), [], {}.

Определи, откроется ли дверь.

Формат ввода

Одна строка s, состоящая только из символов ( ) [ ] { }.

Формат вывода

Выведи YES, если строка является правильной скобочной последовательностью, иначе выведи NO.

Ограничения

• 1 ≤ |s| ≤ 200000

Пример

Ввод:

([{}])

Вывод:

YES

Главное слово здесь — вложенность. Если открыли (, потом [, то сначала нужно закрыть именно [, и только потом (. Значит, всегда важна последняя ещё не закрытая скобка. Для этого подходит стек — структура данных по правилу «последним пришёл, первым вышел».

Идём по строке слева направо:

• Если встретили открывающую скобку (, [ или {, кладём её в стек: она ждёт свою пару.
• Если встретили закрывающую скобку, проверяем стек. Пустой стек означает, что закрывать нечего — ответ сразу NO.
• Иначе снимаем верхнюю скобку стека и проверяем тип пары: для ) сверху должна быть (, для ] — [, для } — {.
• Если типы не совпали, порядок вложенности нарушен, поэтому NO.
• После просмотра всей строки стек должен оказаться пустым. Если в нём что-то осталось, некоторые открывающие скобки так и не закрылись.

Удобно завести соответствие закрывающей скобки её открывающей: ')': '(', ']': '[', '}': '{'.

Каждый символ добавляется в стек и удаляется из него не более одного раза, поэтому время работы — O(n), где n — длина строки. Память в худшем случае — O(n).

Частая ошибка: проверять только одинаковое число открывающих и закрывающих скобок. Например, ([)] имеет правильные количества, но неправильный порядок, поэтому это NO.