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

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

Описание задачи

Требуется реализовать функцию для проверки сбалансированности скобок (balanced parentheses) в строке. Скобки считаются сбалансированными, если каждой открывающей скобке соответствует закрывающая скобка того же типа в правильном порядке. Задача может включать различные типы скобок: круглые (), квадратные [] и фигурные {}. Это классическая задача на использование структуры данных Stack (стек) и часто встречается при тестировании парсеров, валидаторов кода и обработчиков выражений.

Решение на Python

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

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

1. С использованием счётчика (только круглые скобки)

def is_balanced_counter(s):
    """
    Простой подход с счётчиком.
    Работает только если в строке круглые скобки ()!
    """
    count = 0
    
    for char in s:
        if char == '(':
            count += 1
        elif char == ')':
            count -= 1
            # Если в любой момент закрывающих больше открывающих
            if count < 0:
                return False
    
    return count == 0

2. С использованием встроенной функции count

def is_balanced_count(s):
    """
    Очень простой способ для одного типа скобок.
    """
    # Работает только если нет других типов скобок
    return s.count('(') == s.count(')') and '(' in s or s.count(')') == 0

3. С фильтрацией скобок

def is_balanced_filtered(s):
    """
    Фильтрует только скобки и проверяет их.
    """
    # Оставляем только скобки
    brackets = ''.join(c for c in s if c in '()[]{}' )
    
    while '()' in brackets or '[]' in brackets or '{}' in brackets:
        brackets = brackets.replace('()', '').replace('[]', '').replace('{}', '')
    
    return len(brackets) == 0

4. С использованием regex

import re

def is_balanced_regex(s):
    """
    Использует регулярные выражения.
    """
    # Повторно удаляем правильные пары, пока есть
    while re.search(r'(\(\)|\[\]|\{\})', s):
        s = re.sub(r'(\(\)|\[\]|\{\})', '', s)
    
    return len(s) == 0

5. С явным логированием для отладки

def is_balanced_debug(s, debug=False):
    """
    Версия со встроенной отладкой.
    """
    stack = []
    matching = {
        ')': '(',
        ']': '[',
        '}': '{'
    }
    
    for i, char in enumerate(s):
        if char in '([{':
            stack.append(char)
            if debug:
                print(f'{i}: {char} добавлена, стек: {stack}')
        elif char in ')]}':
            if debug:
                print(f'{i}: {char} найдена')
            if not stack or stack[-1] != matching[char]:
                if debug:
                    print(f'   Ошибка: нет соответствующей открывающей скобки')
                return False
            stack.pop()
            if debug:
                print(f'   OK, стек: {stack}')
    
    if debug:
        print(f'Итог: стек = {stack}')
    
    return len(stack) == 0

Тестовые примеры

import unittest

class TestIsBalanced(unittest.TestCase):
    
    def test_basic_balanced_1(self):
        # Первый базовый случай
        assert is_balanced('()()') == True
    
    def test_basic_balanced_2(self):
        # Второй базовый случай
        assert is_balanced('(())') == True
    
    def test_basic_unbalanced(self):
        # Третий базовый случай
        assert is_balanced('(()') == False
    
    def test_multiple_types(self):
        # Различные типы скобок
        assert is_balanced('([{}])') == True
    
    def test_empty_string(self):
        # Пустая строка
        assert is_balanced('') == True
    
    def test_single_pair(self):
        # Одна пара
        assert is_balanced('()') == True
    
    def test_single_open(self):
        # Только открывающая
        assert is_balanced('(') == False
    
    def test_single_close(self):
        # Только закрывающая
        assert is_balanced(')') == False
    
    def test_wrong_order(self):
        # Неправильный порядок
        assert is_balanced('([)]') == False
    
    def test_nested(self):
        # Вложенные скобки
        assert is_balanced('(((([[[{{}}]]]))))') == True
    
    def test_mixed_unbalanced(self):
        # Смешанные неправильные
        assert is_balanced('([{)}]') == False
    
    def test_extra_open(self):
        # Лишние открывающие
        assert is_balanced('((()))') == False  # Лишняя скобка
        assert is_balanced('(()())') == True
    
    def test_with_text(self):
        # Со строками/текстом
        assert is_balanced('function(arg1, [item1, item2], {key: value})') == True
    
    def test_unbalanced_closing(self):
        # Закрывающих больше
        assert is_balanced('(()))') == False
    
    def test_mismatched_types(self):
        # Неправильные пары
        assert is_balanced('[)') == False
        assert is_balanced('(]') == False
        assert is_balanced('{)') == False

class TestBalancedPerformance(unittest.TestCase):
    
    def test_large_string(self):
        # Большая строка со скобками
        balanced = '(' * 1000 + ')' * 1000
        assert is_balanced(balanced) == True
    
    def test_large_unbalanced(self):
        # Большая неправильная строка
        unbalanced = '(' * 1000 + ')' * 999
        assert is_balanced(unbalanced) == False
    
    def test_many_types(self):
        # Много типов скобок
        s = '[({[({[({[' + ']})]})]})]}'
        assert is_balanced(s) == True

Анализ сложности

Применение в QA Automation

• Валидация синтаксиса кода — проверка сбалансированности скобок в исходном коде
• Парсинг выражений — валидация математических и логических выражений
• Обработка JSON/XML — проверка корректности вложенности тегов
• Тестирование компиляторов — убедиться, что парсер правильно обрабатывает скобки
• Граничные случаи — пустые строки, одна скобка, много уровней вложенности
• Регрессионное тестирование — проверка после изменений парсера

Ключевые моменты

1. Порядок важен — ([)] неправильно, ([)] должно быть ([])
2. Типы должны совпадать — (] неправильно
3. Ранний выход — если закрывающих больше открывающих, можно вернуть False
4. Пустая строка валидна — нет скобок = сбалансировано

Рекомендация

Для стандартного использования в QA рекомендуется подход со стеком — он:

1. Универсален — работает со всеми типами скобок
2. Эффективен — O(n) время и память
3. Понятен — классическая структура данных
4. Легко расширяется — добавление новых типов скобок

Для интервью покажите понимание стека и алгоритма. Для простых случаев (только круглые скобки) можно использовать счётчик.