Стеки для сопоставления скобок
Проверяйте скобки с помощью стека
«Стеки для сопоставления скобок» — бесплатный урок Competitive Programming Academy на CoddyKit. Это урок 1 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Competitive Programming Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Competitive Programming Academy содержит 4 уроков всего.
Последним вошёл — первым вышел
Стек — это стопка, в которой последним добавленный элемент извлекается первым, как тарелки в стопке. 🍽️
Списки Python работают как стеки
В Python Вам не нужен специальный класс. Обычный список уже работает как быстрый готовый стек для соревнований.
stack = []Добавляйте с помощью append
Чтобы добавить элемент на вершину стека, вызовите append: значение окажется в конце списка за время O(1).
stack.append('(')
stack.append('[')Извлекайте с вершины
Вызов pop без индекса удаляет и возвращает последний элемент — тот, который был последним помещён в стек.
top = stack.pop() # removes '['Просматривайте без удаления
Чтобы посмотреть на элемент на вершине, не снимая его, просто прочитайте stack[-1]. Такой просмотр полезен перед решением об извлечении.
if stack:
top = stack[-1]Всегда проверяйте, пуст ли стек
Извлечение из пустого стека вызывает ошибку. Перед каждым извлечением проверяйте if stack, чтобы решение никогда не завершалось сбоем.
Идея сопоставления скобок
Скобки идеально вкладываются друг в друга, поэтому здесь отлично подходит стек. Помещайте каждую открывающую скобку в стек, а закрывающая должна соответствовать его вершине.
Свяжите закрывающие с открывающими
Храните небольшой словарь, сопоставляющий каждой закрывающей скобке ожидаемую открывающую, чтобы проверки оставались понятными.
pairs = {')': '(', ']': '[', '}': '{'}Просмотрите и примите решение
Пройдите строку один раз. Помещайте открывающие скобки в стек, а при встрече закрывающей сравнивайте её с извлечённой вершиной с помощью карты пар.
for c in s:
if c in pairs.values():
stack.append(c)Несовпадение означает недопустимую строку
Если извлечённая открывающая скобка не совпадает или стек пуст, когда он нужен, строка сразу становится недопустимой.
elif not stack or stack.pop() != pairs[c]:
return FalseПустой стек в конце
Оставшаяся после просмотра открывающая скобка означает, что какая-то скобка не была закрыта. Строка допустима только тогда, когда стек в конце полностью пуст.
return not stackБыстрая проверка
Вы проверяете скобки с помощью стека. О чём говорит непустой стек в самом конце?
Итоги: стеки укрощают скобки
Вы узнали, что список работает как стек: помещайте открывающие скобки, извлекайте их при встрече закрывающих, а пустой стек в конце означает правильную вложенность. Отличная работа! 🎉
Часто задаваемые вопросы
Урок «Стеки для сопоставления скобок» бесплатный?
Да — полный текст урока «Стеки для сопоставления скобок» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Competitive Programming Academy, подпишись на CoddyKit PRO. Курс Competitive Programming Academy содержит 4 уроков всего.
Чему я научусь в уроке «Стеки для сопоставления скобок»?
Проверяйте скобки с помощью стека Ты практикуешь Competitive Programming Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Competitive Programming Academy?
Предыдущий опыт не требуется. Competitive Programming Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 1 из 4.
Сколько времени занимает урок «Стеки для сопоставления скобок»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Competitive Programming Academy?
Да. Каждый урок Competitive Programming Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Стеки для сопоставления скобок
- Монотонный стек: следующий больший элемент
- Очереди и collections.deque
- Максимум в скользящем окне с деком