Курсы

C++. Динамические структуры данных

C++. Практика работы со стеком

Модуль: C++. Практика работы со стеком

2. Применяем стек

Задача
Дана строка со скобками (), [], {}. Проверить, правильно ли расставлены скобки.

Примеры:

Вход: "({[]})"    → Выход: true
Вход: "([)]"      → Выход: false  
Вход: "{(})"      → Выход: false
Вход: "((()))"    → Выход: true

Решение

#include <iostream>
#include <stack>
#include <string>
using namespace std;

bool isValid(string s) {
    stack<char> st;
    
    for (char c : s) {
        // Если открывающая скобка - кладем в стек
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        }
        // Если закрывающая скобка
        else {
            // Стек пуст - несоответствие
            if (st.empty()) return false;
            
            // Проверяем соответствие скобок
            char top = st.top();
            if ((c == ')' && top == '(') ||
                (c == ']' && top == '[') ||
                (c == '}' && top == '{')) {
                st.pop();  // скобки совпали - убираем из стека
            } else {
                return false;  // несоответствие скобок
            }
        }
    }
    
    // Если стек пуст - все скобки закрыты правильно
    return st.empty();
}

int main() {
    string str;
    cin >> str;
    
    if (isValid(str)) {
        cout << "true" << endl;
    } else {
        cout << "false" << endl;
    }
    
    return 0;
}

Пошаговое объяснение для "({[]})":

( → стек: [ '(' ]
{ → стек: [ '(', '{' ]
[ → стек: [ '(', '{', '[' ]
] → '[' совпадает → стек: [ '(', '{' ]
} → '{' совпадает → стек: [ '(' ]
) → '(' совпадает → стек: [ ]

Результат: true (стек пуст)

Объяснение для "([)]":

( → стек: [ '(' ]
[ → стек: [ '(', '[' ]
) → '[' ≠ '(' → false

time 1000 ms
memory 256 Mb

Комментарий учителя

Обсуждения (0)

Чтобы оставить комментарий нужна авторизация

Решения (0)

Решения:

Нет доступных решений

Курсы C++. Динамические структуры данных C++. Практика работы со стеком