В какой момент можно определить, что скобочная последовательность уже некорректна?

Question

Некорректность можно определить сразу, как только встречается закрывающая скобка, которой не соответствует последняя открывающая. Также ошибка есть, если закрывающая скобка встретилась, когда стек пуст. Эти случаи означают, что дальнейший разбор строки уже не исправит проблему. В конце проверки ещё одна причина некорректности — если стек не пуст.

YeaHub · Accepted Answer

ОпределениеРаннее обнаружение некорректности — это способность алгоритма завершиться до конца строки, как только становится ясно, что корректного результата быть не может.Инвариант проверкиПеред тем как формулировать условия ошибки, полезно держать в голове правило:в стеке всегда лежат только незакрытые открывающие скобки в правильном порядке.Ситуации, когда можно сразу вернуть FalseЗакрывающая скобка при пустом стекеПример: ")..."Причина: нечего закрыватьТип закрывающей скобки не совпадает с последней открывающейПример: "([)]" при встрече ) последняя открытая — [Причина: нарушена вложенностьПример кода с ранним выходомdef is_valid(s: str) -> bool:
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}

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

return not stack
Отдельный момент: ошибка, которую видно только в концеДаже если ранних ошибок не было, строка некорректна, если остались незакрытые скобки.Пример: "(()"После прохода стек не пуст → FalseКраткий выводНекорректность часто определяется “на лету” при обработке закрывающих скобок, а финальная проверка — пустой ли стек — закрывает случаи незавершённого закрытия.