Определение сбалансированности скобок в строке

Условие

Необходимо написать функцию 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

Финальная проверка нужна для случаев вроде '(()': закрывающих ошибок нет, но остаётся открывающая скобка. Время O(n), память O(n); пустая строка корректна.