Как проверить корректность открытия и закрытия скобок в строке?

Question

Корректность скобок обычно проверяют с помощью стека. Мы идём по строке слева направо и кладём открывающие скобки в стек. Когда встречаем закрывающую скобку, проверяем, что в стеке есть соответствующая открывающая. Если в конце строка обработана и стек пуст — последовательность корректна.

YeaHub · Accepted Answer

ОпределениеПроверка корректности скобок — это алгоритмическая задача, цель которой определить, правильно ли открывающие и закрывающие скобки сбалансированы и вложены в строке.Базовая идея алгоритмаПеред использованием конкретных шагов важно понимать общий принцип:алгоритм должен учитывать порядок, тип и вложенность скобок.Основные шаги проверкиСоздать пустую структуру данных для хранения открывающих скобок.Последовательно пройти по всем символам строки.Если символ — открывающая скобка, сохранить её.Если символ — закрывающая скобка:Проверить, что ранее была открывающая.Проверить, что тип скобок совпадает.После обработки строки убедиться, что не осталось незакрытых скобок.Пример на Pythondef is_valid_brackets(s: str) -> bool:
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}

for char in s:
        if char in pairs.values():
            stack.append(char)
        elif char in pairs:
            if not stack or stack.pop() != pairs[char]:
                return False

return not stack
Типичные ошибкиПроверка только количества скобок без учёта порядкаОтсутствие проверки на пустой стекИгнорирование разных типов скобокКраткий выводИспользование стека — надёжный и простой способ проверки корректности скобочной последовательности. Такой алгоритм легко читается, работает за один проход и подходит для production-кода.