Проверь валидность скобочной последовательности

Валидные скобки — задача-обманка, которую обожают на алгоритмических секциях. Она выглядит настолько простой, что первое решение пишется за минуту. Проблема в том, что минимум два «очевидных» подхода к ней неверны — и собеседующий ждёт, что ты сам найдёшь контрпримеры. Это жемчужина: она проверяет не умение писать код, а умение его ломать.

Задача

Строка состоит из круглых скобок ( и ). Последовательность валидна, если каждая открывающая скобка закрыта соответствующей закрывающей в правильном порядке.

Напиши функцию is_valid(s), возвращающую True/False. Ожидаемые ответы на наборе:

check_list = ['()', ')(', '(())', '()()', '()))']
answer_list = [True, False, True, True, False]

Решение

def is_valid(s):
    stack = []
    for c in s:
        if c == "(":
            stack.append(c)
        elif stack:
            stack.pop()
        else:
            return False
    return not stack


cases = ["()", ")(", "(())", "()()", "()))"]
for s in cases:
    print(f"{s!r} -> {is_valid(s)}")

Разбор

Интереснее всего здесь не правильный ответ, а два неправильных — потому что оба приходят в голову первыми.

Неверная попытка №1: считать скобки. Логика кажется железной: если открывающих столько же, сколько закрывающих, — значит, всё сбалансировано.

def check_bracket(s):
    open_cnt = sum(1 for c in s if c == "(")
    close_cnt = len(s) - open_cnt
    return open_cnt == close_cnt

Контрпример — ')('. Здесь одна открывающая и одна закрывающая, счётчики равны, функция радостно возвращает True. Но последовательность-то невалидна: закрывающая идёт раньше открывающей. Счётчик игнорирует порядок — а порядок и есть вся суть задачи. Именно на ')(' этот подход разваливается.

Неверная попытка №2: рекурсия с краёв. Ещё одна красивая идея: валидная строка начинается на ( и кончается на ), а между ними — снова валидная строка. Значит, отрежем края и вызовем себя рекурсивно:

def check_bracket(s):
    if not s:
        return True
    if s[0] != "(" or s[-1] != ")":
        return False
    return check_bracket(s[1:-1])

Контрпример — '()()'. Первый символ (, последний ) — проверка проходит. Отрезаем края, остаётся ')(' — а вот у него первый символ ), и функция возвращает False. Но '()()' абсолютно валидна! Подход ломается, потому что валидная строка не обязана быть «одной большой скобкой» — она может быть склейкой нескольких независимых пар.

Правильный ответ — стек. Единственная структура, которая учитывает порядок: идём по строке, каждую ( кладём на стек, на каждую ) снимаем со стека пару. Если снимать нечего (стек пуст, а пришла закрывающая) — сразу False: закрылось то, что не открывали. В конце стек должен быть пустым — иначе остались незакрытые скобки.

Пройдёмся по контрпримерам: на ')(' первая же ) встречает пустой стек → False. На '()()' стек аккуратно наполняется и опустошается дважды, в конце пуст → True. Стек работает именно потому, что моделирует вложенность: последняя открытая скобка закрывается первой — это LIFO в чистом виде.

Сложность — O(n) по времени и памяти. Мораль задачи шире скобок: интуитивно «очевидное» решение алгоритмической задачи стоит первым делом попробовать сломать контрпримером. Тот же навык «а что если данные придут не в том порядке» пригодится в задаче про скользящее среднее.

Ожидаемый результат

'()' -> True
')(' -> False
'(())' -> True
'()()' -> True
'()))' -> False