Проверка скобок в выражении

Решение

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

Проверить, что все скобки в выражении расставлены корректно. Для этого нужно:

• Каждой открывающей скобке соответствует закрывающая
• Порядок соответствия правильный (нет пересечений)
• Поддерживать три типа скобок: (), [], {}

Оптимальный алгоритм: Stack

def is_valid_parentheses(s):
    stack = []
    mapping = {')': '(', ']': '[', '}': '{'}
    
    for char in s:
        if char in mapping:
            # Закрывающая скобка
            if not stack or stack[-1] != mapping[char]:
                return False
            stack.pop()
        elif char in mapping.values():
            # Открывающая скобка
            stack.append(char)
    
    # Stack должен быть пустой
    return len(stack) == 0

Как это работает

Пример 1: (1 + 2) * (3 + 4)

Шаг 1: Видим '(' -> добавляем в stack: ['('] Шаг 2: Видим ')' -> проверяем top: '(' совпадает, удаляем: [] Шаг 3: Видим '(' -> добавляем: ['('] Шаг 4: Видим ')' -> совпадает, удаляем: [] Результат: stack пустой -> True

Пример 2: ((1 + 2) * 3

Шаг 1: '(' -> stack: ['('] Шаг 2: '(' -> stack: ['(', '('] Шаг 3: ')' -> совпадает, stack: ['('] Конец строки -> stack не пустой -> False

Сложность

• Временная: O(n) — каждый символ посещаем один раз
• Пространственная: O(n) — в худшем случае все открывающие скобки

Расширенная версия с поддержкой всех типов скобок

def is_valid_all_brackets(s):
    """
    Проверяет корректность всех типов скобок: (), [], {}
    """
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}
    
    for char in s:
        if char in pairs:
            # Закрывающая скобка
            if not stack or stack[-1] != pairs[char]:
                return False
            stack.pop()
        elif char in pairs.values():
            # Открывающая скобка
            stack.append(char)
    
    return len(stack) == 0

Тестирование

# Валидные выражения
assert is_valid_parentheses("()") == True
assert is_valid_parentheses("([])") == True
assert is_valid_parentheses("()[]{}") == True
assert is_valid_parentheses("(1 + 2) * (3 + 4)") == True
assert is_valid_parentheses("") == True

# Невалидные выражения
assert is_valid_parentheses("(") == False
assert is_valid_parentheses(")") == False
assert is_valid_parentheses("(()") == False
assert is_valid_parentheses("((1 + 2) * 3") == False
assert is_valid_parentheses("([)]") == False
assert is_valid_parentheses("([)][") == False

Альтернативные подходы

Способ 1: Счётчик (только одного типа скобок)

def is_valid_simple_count(s):
    count = 0
    for char in s:
        if char == '(':
            count += 1
        elif char == ')':
            count -= 1
            if count < 0:
                return False
    return count == 0

• O(n) время, O(1) память
• Работает только для одного типа скобок
• Не ловит пересечение скобок

Способ 2: Регулярные выражения (менее эффективно)

import re

def is_valid_regex(s):
    while '()' in s or '[]' in s or '{}' in s:
        s = s.replace('()', '').replace('[]', '').replace('{}', '')
    return s == ''

• O(n²) время в худшем случае
• Менее эффективно

Граничные случаи

# Пустая строка - валидна
assert is_valid_parentheses("") == True

# Только открывающие скобки
assert is_valid_parentheses("(((") == False

# Только закрывающие скобки
assert is_valid_parentheses(")))") == False

# Смешанные типы с пересечениями
assert is_valid_parentheses("([)]") == False
assert is_valid_parentheses("{[}]") == False

# Вложенные скобки
assert is_valid_parentheses("[[[[]]]]" ) == True

Выводы

• Stack — идеальная структура для этой задачи
• O(n) время, O(n) память — оптимальная сложность
• Работает для всех типов скобок — легко расширяется
• Для QA: проверить граничные случаи, смешанные скобки, пересечения