Проверка корректности вложения скобок

Условие

Необходимо написать функцию areBracketsBalanced, которая определяет, правильно ли распределены скобки в переданной строке expr. В строке допускаются только символы круглых, квадратных и фигурных скобок – ()[]{}. Функция должна возвращать True, когда каждая открывающая скобка имеет соответствующую закрывающую в правильном порядке, и False в противном случае.

def areBracketsBalanced(expr):
    stack = []

    for char in expr:
        if char in ["(", "{", "["]:
            stack.append(char)
        else:
            if not stack:
                return False
            current_char = stack.pop()
            if current_char == "(":
                if char != ")":
                    return False
            if current_char == "{":
                if char != "}":
                    return False
            if current_char == "[":
                if char != "]":
                    return False

    return not stack

Ответ

Используйте стек открывающих скобок. Каждая закрывающая должна соответствовать вершине стека; в конце стек обязан быть пустым. Исходный алгоритм корректен для указанного алфавита.

Ту же проверку можно записать компактнее:

def areBracketsBalanced(expr):
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for char in expr:
        if char in '([{':
            stack.append(char)
        elif char in pairs:
            if not stack or stack.pop() != pairs[char]:
                return False
        else:
            return False
    return not stack

Примеры: '([])' — True, '([)]' — False, '(' — False. Пустая строка считается корректной. Время O(n), дополнительная память O(n) в случае множества вложенных открывающих скобок.