1. Идея

Нужно проверить, правильно ли расставлены скобки трёх типов: (), [], {}.

Главная идея — использовать стек.

• Когда встречаем открывающую скобку, кладём её в стек.
• Когда встречаем закрывающую скобку, нужно проверить, что:
  • в стеке вообще есть незакрытая скобка;
  • последняя открытая скобка соответствует текущей закрывающей.

Если хотя бы в один момент это не так, ответ сразу NO.

После обработки всей строки стек должен оказаться пустым. Если в нём что-то осталось, значит какие-то скобки не закрылись.

2. Наблюдения

Наблюдение 1

Проверять скобки нужно именно в обратном порядке открытия.

Например, в строке ([]):

• сначала открыли (
• потом открыли [
• значит сначала обязана закрыться ], и только потом )

Это поведение полностью совпадает со структурой стека: последний добавленный элемент извлекается первым.

Наблюдение 2

Если встретили закрывающую скобку, а стек пуст, то строка некорректна.

Пример: ")("

Первая же скобка закрывающая, но закрывать нечего.

Наблюдение 3

Если типы скобок не совпали, строка тоже некорректна.

Пример: ([)]

После ( и [ в стеке сверху стоит [, но встретилась ). Значит нарушен порядок вложенности.

Наблюдение 4

Даже если по ходу не было ошибок, в конце могут остаться незакрытые скобки.

Пример: "(()"

Все символы обработаны, но одна открывающая скобка так и не закрылась.

3. Алгоритм

1. Считать строку s.
2. Создать пустой стек st.
3. Пройти по всем символам строки:
   • если символ — одна из открывающих скобок (, [ или {, добавить его в стек;
   • иначе это закрывающая скобка:
     • если стек пуст, вывести NO и завершить программу;
     • взять верхний элемент стека и удалить его;
     • проверить, образуют ли верхний элемент и текущая скобка правильную пару:
       • ( и )
       • [ и ]
       • { и }
     • если нет, вывести NO и завершить программу.
4. После обхода:
   • если стек пуст, вывести YES;
   • иначе вывести NO.

4. Почему это работает

Докажем по смыслу работы стека.

Когда встречается открывающая скобка, она ждёт свою закрывающую. Мы сохраняем её в стеке.

Почему достаточно смотреть только на верхушку стека? Потому что закрываться должна последняя из ещё не закрытых открывающих скобок. Это и есть правило вложенности.

Например, в строке {[()]}:

• открыли {
• открыли [
• открыли (
• теперь первой должна закрыться именно (

То есть при встрече закрывающей скобки нужно сравнивать её не с любой прошлой открывающей, а именно с самой последней незакрытой. Стек делает это автоматически.

Если в какой-то момент:

• стек пуст, а пришла закрывающая скобка, значит закрывать нечего;
• верхняя скобка в стеке другого типа, значит нарушен порядок или тип скобок.

В обоих случаях строка не может быть корректной.

Если после обработки всей строки стек пуст, значит каждая открывающая скобка нашла свою правильную закрывающую в нужном порядке. Тогда последовательность корректна.

Если стек не пуст, значит остались незакрытые скобки, и последовательность некорректна.

Следовательно, алгоритм верно определяет ответ.

5. Сложность

Пусть длина строки равна n.

• Каждый символ обрабатывается ровно один раз.
• Каждая скобка не более одного раза добавляется в стек и не более одного раза удаляется.

Поэтому:

• время работы: O(n)
• память: O(n) в худшем случае, если все скобки открывающие

При n до 2 * 10^5 такой алгоритм легко проходит.

6. Код на C++17

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main() {
    string s;
    cin >> s;

    vector<char> st;

    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            st.push_back(c);
        } else {
            if (st.empty()) {
                cout << "NO\n";
                return 0;
            }

            char top = st.back();
            st.pop_back();

            bool ok = (c == ')' && top == '(') ||
                      (c == ']' && top == '[') ||
                      (c == '}' && top == '{');

            if (!ok) {
                cout << "NO\n";
                return 0;
            }
        }
    }

    if (st.empty()) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }

    return 0;
}

7. Код на Python 3

s = input().strip()

st = []

for c in s:
    if c in "([{":
        st.append(c)
    else:
        if not st:
            print("NO")
            break
        top = st.pop()
        if not ((c == ')' and top == '(') or
                (c == ']' and top == '[') or
                (c == '}' and top == '{')):
            print("NO")
            break
else:
    if not st:
        print("YES")
    else:
        print("NO")