Ошибки и проблемы
- При встрече закрывающей скобки делается вызов `stack.pop()` без проверки, пуст ли стек — для входа, начинающегося с `)` или `]`, или при избытке закрывающих, это вызовет `IndexError` (исключение).
- Код игнорирует прочие символы (это не ошибка сама по себе, но стоит уточнить требуемое поведение для некорректных символов).
- Для читаемости и масштабируемости лучше использовать отображение пар скобок и проверять пустоту стека перед `pop()`.
Поведение на некорректных входах (примеры)
- s = ")" — текущая версия выбросит `IndexError`.
- s = "([)]" — текущая версия вернёт `False` (правильно обнаружит несоответствие).
- s = "(((" — вернёт `False` (по окончании стек не пуст).
- s = "a(b)c" — игнорирует буквы и проверяет только скобки (результат зависит только от скобок).
Исправленная версия (без выбрасывания исключения при незакрытой/лишней закрывающей):
def is_balanced(s):
stack = []
pairs = {')': '(', ']': '['}
for c in s:
if c in '([':
stack.append(c)
elif c in ')]':
if not stack or stack.pop() != pairs[c]:
return False
return not stack
Короткие пояснения к исправлению
- Проверяем `if not stack` перед `pop()` — тогда при лишней закрывающей возвращаем `False`, а не получаем исключение.
- Используем словарь `pairs` и `c in ')]'` для ясности и лёгкого расширения (например, добавления `{}`).
Сложность
- Временная: $O(n)$, где $n$ — длина строки `s`.
- Память (дополнительная): в худшем случае $O(n)$ (все символы — открывающие скобки).