Дана последовательность из N круглых, квадратных и фигурных скобок. Узнайте, можно ли добавить числа и арифметические операции, чтобы получить правильное арифметическое выражение.

Вход
Первая строка содержит количество скобок N (1 ≤ N ≤ 100 000).
Вторая строка содержит последовательность из N символов из множества (, ), [, ], {, }.
Выход
Отображает слово «Да», если вы можете получить правильное арифметическое выражение, или «Нет», если вы не можете.

Нужно проверить, является ли данная скобочная последовательность правильной с учётом трёх типов скобок:

(), [], {}.

Если скобки стоят правильно, то между ними всегда можно добавить числа и операции так, чтобы получить корректное арифметическое выражение. Например:

([])  →  (1 + [2])

Здесь квадратные и фигурные скобки можно рассматривать как допустимые группирующие скобки.

Если же порядок скобок нарушен, например:

([)]

то никакие числа и операции уже не помогут.

Идея решения

Используем стек.

Проходим строку слева направо:

1. Если символ — открывающая скобка (, [, {, кладём её в стек.

2. Если символ — закрывающая скобка:

   • стек не должен быть пустым;

   • верхняя скобка в стеке должна быть соответствующей открывающей.

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

Если все условия выполняются, ответ — Да, иначе — Нет.

Примеры

Последовательность:

([])

Обработка:

(  кладём в стек
[  кладём в стек
]  закрывает [
)  закрывает (

Стек пуст, значит ответ:

Да

Последовательность:

([)]

Обработка:

(  кладём в стек
[  кладём в стек
)  пытается закрыть (, но сверху лежит [

Ошибка, ответ:

Нет

Сложность

Каждая скобка обрабатывается один раз.

Время: O(N)
Память: O(N)

При N ≤ 100000 это подходит.

Решение на C++

C++
#include 
#include 
#include 

using namespace std;

int main() {
    int N;
    string s;

    cin >> N;
    cin >> s;

    stack<char> st;

    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else {
            if (st.empty()) {
                cout << "Нет";
                return 0;
            }

            char top = st.top();
            st.pop();

            if (c == ')' && top != '(') {
                cout << "Нет";
                return 0;
            }

            if (c == ']' && top != '[') {
                cout << "Нет";
                return 0;
            }

            if (c == '}' && top != '{') {
                cout << "Нет";
                return 0;
            }
        }
    }

    if (st.empty()) {
        cout << "Да";
    } else {
        cout << "Нет";
    }

    return 0;
}

Главное условие: закрывающая скобка должна закрывать именно последнюю ещё не закрытую открывающую скобку того же типа.