Проверка правильности расположения скобок в строке

Условие

Дана строка, состоящая из открывающих и закрывающих скобок. Требуется определить, правильно ли расставлены скобки. Строка считается корректной, если:

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

Ответ

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

def valid_brackets(text):
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for char in text:
        if char in '([{':
            stack.append(char)
        elif char in pairs:
            if not stack or stack.pop() != pairs[char]:
                return False
        else:
            return False
    return not stack

Пустая строка считается корректной. ([{}]) проходит проверку, ([)] — нет, хотя число скобок каждого типа совпадает. Поэтому одного подсчёта количества недостаточно. По условию разрешены только скобки; если нужно проверять скобки внутри произвольного текста, обработку остальных символов следует изменить. Время O(n), память O(n).