Сбалансированные скобки

Сбалансированные скобки: Решение через стек

Понимание задачи

Нужно проверить, что все скобки в строке правильно открыты и закрыты в нужном порядке. Например, ([)] — неправильно (скобки пересекаются), а ([]) — правильно (вложены корректно).

Это классическая задача на стек — одна из первых алгоритмических задач для собеседования.

Оптимальный подход: Stack O(n)

def is_balanced(s: str) -> bool:
    """
    Проверяет сбалансированность скобок за O(n) время.
    
    Args:
        s: строка с потенциальными скобками
    
    Returns:
        True если все скобки сбалансированы, иначе False
    """
    # Соответствие открывающих и закрывающих скобок
    bracket_map = {')': '(', ']': '[', '}': '{'}
    stack = []
    
    for char in s:
        if char in bracket_map:  # Закрывающая скобка
            # Если стек пуст или верхний элемент не совпадает — ошибка
            if not stack or stack[-1] != bracket_map[char]:
                return False
            stack.pop()
        elif char in bracket_map.values():  # Открывающая скобка
            stack.append(char)
    
    # Стек должен быть пуст (все скобки закрыты)
    return len(stack) == 0

Пример пошагово для "([)]":

Шаг 0: char='(' -> открывающая, stack=['(']
Шаг 1: char='[' -> открывающая, stack=['(', '[']
Шаг 2: char=')' -> закрывающая
  - bracket_map[')'] = '('
  - stack[-1] = '[' != '('
  - return False ✗

Пример пошагово для "([])":

Шаг 0: char='(' -> stack=['(']
Шаг 1: char='[' -> stack=['(', '[']
Шаг 2: char=']' -> bracket_map[']'] = '['
  - stack[-1] = '[' == '[' ✓
  - stack.pop() -> stack=['(']
Шаг 3: char=')' -> bracket_map[')'] = '('
  - stack[-1] = '(' == '(' ✓
  - stack.pop() -> stack=[]
Возвращаем len(stack) == 0 -> True ✓

Альтернатива: С набором открывающих скобок

def is_balanced_v2(s: str) -> bool:
    """Немного другой стиль записи."""
    opening = {'(', '[', '{'}
    closing = {')', ']', '}'}
    pairs = {'(': ')', '[': ']', '{': '}'}
    stack = []
    
    for char in s:
        if char in opening:
            stack.append(char)
        elif char in closing:
            if not stack or pairs[stack[-1]] != char:
                return False
            stack.pop()
    
    return len(stack) == 0

Тесты для проверки

def test_is_balanced():
    # Базовые случаи
    assert is_balanced("()") == True
    assert is_balanced("[]") == True
    assert is_balanced("{}") == True
    
    # Вложение
    assert is_balanced("([{}])") == True
    assert is_balanced("([]{})") == True
    
    # Пересечение (неправильно)
    assert is_balanced("([)]") == False
    assert is_balanced("({[}])") == False
    
    # Незакрытые
    assert is_balanced("((())") == False
    assert is_balanced("((") == False
    assert is_balanced("))") == False
    
    # Пустая строка
    assert is_balanced("") == True
    
    # Строка без скобок
    assert is_balanced("hello world") == True
    
    # Со смешанными символами
    assert is_balanced("a(b[c]d)e") == True
    assert is_balanced("a(b[c)d]e") == False
    
    print("Все тесты пройдены!")

Сложность анализ

Временная сложность: O(n)

• Один проход по строке
• Каждый элемент добавляется/удаляется из стека один раз

Пространственная сложность: O(n)

• Стек может содержать до n/2 элементов (для строки вида "(((())))")

Оптимизация для известных длин

Если известно максимальное количество вложенности, можно использовать деке:

from collections import deque

def is_balanced_deque(s: str) -> bool:
    bracket_map = {')': '(', ']': '[', '}': '{'}
    stack = deque()
    
    for char in s:
        if char in bracket_map:
            if not stack or stack[-1] != bracket_map[char]:
                return False
            stack.pop()
        elif char in bracket_map.values():
            stack.append(char)
    
    return len(stack) == 0

Деке работает быстрее для большого количества операций с концами.

Вариант с регулярными выражениями

Не рекомендуется для интервью, но интересно знать:

import re

def is_balanced_regex(s: str) -> bool:
    """Удаляет вложенные пары скобок, пока они есть."""
    while '()' in s or '[]' in s or '{}' in s:
        s = s.replace('()', '').replace('[]', '').replace('{}', '')
    return s == ''

Проблема: O(n²) в худшем случае (для "(((())))"), медленнее.

Ключевые моменты для интервью

1. Основное решение: Стек, O(n) время
2. Инвариант: Стек содержит несопоставленные открывающие скобки
3. Edge cases:
   • Пустая строка -> True
   • Только открывающие -> False
   • Только закрывающие -> False
   • Пересекающиеся скобки -> False
4. Оптимизация: Регулярные выражения O(n²), избегать

Практическое применение

• Парсинг исходного кода (компиляторы)
• Проверка синтаксиса в редакторах
• Валидация структур данных JSON/XML