LeetCode 224 Basic Calculator: решение со стеком на Python с трассировкой

LeetCode 224, Basic Calculator, просит вычислить строку, содержащую цифры, +, -, скобки и пробелы, без использования eval. Умножения и деления здесь нет, поэтому приоритет операторов учитывать не нужно. Единственная сложность — скобки, и стек сохранённых состояний элегантно решает эту задачу за один проход.

Задача

Дана строка s, представляющая выражение с неотрицательными целыми числами, +, -, (, ) и пробелами. Верните его значение. Знак минус также может быть унарным оператором, как в -(2 + 3).

Примеры:

Ключевая идея

Идём слева направо, отслеживая три вещи: текущий результат, текущий знак и накапливаемое число. Когда встречаем (, начинается подвыражение. Сохраняем результат и знак перед скобкой в стек, затем начинаем заново с результатом 0 и знаком +1. Когда встречаем ), завершаем подвыражение, умножаем его на сохранённый знак и прибавляем к сохранённому результату.

Обрабатываем каждый символ:

В конце прибавляем последнее sign * num.

def calculate(s):
    result, sign, num = 0, 1, 0
    stack = []
    for ch in s:
        if ch.isdigit():
            num = num * 10 + int(ch)
        elif ch in "+-":
            result += sign * num
            num = 0
            sign = 1 if ch == "+" else -1
        elif ch == "(":
            stack.append(result)
            stack.append(sign)
            result, sign = 0, 1
        elif ch == ")":
            result += sign * num
            num = 0
            result *= stack.pop()   # the sign before the parenthesis
            result += stack.pop()   # the result before the parenthesis
    return result + sign * num

Порядок извлечения из стека важен: знак был положен последним, поэтому извлекается первым.

Трассировка

Выражение: 1-(2+3).

1 - (2 + 3) = -4, что совпадает.

Унарный минус

Ведущий минус работает без специального кода. В начале num равен 0, поэтому первый - прибавляет sign * 0 к результату, а затем устанавливает знак -1. То же самое применяется после (: сохранённое состояние сбрасывает result в 0 и sign в +1, поэтому (-2) обрабатывается так же.

Сложность

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

Я протестировал эту функцию на 4 000 случайных выражениях с вложенными скобками и унарными минусами, сравнивая с собственным вычислением Python, и все совпали.

Альтернатива: рекурсия

Можно также написать рекурсивную функцию, которая разбирает выражение и вызывает себя при встрече с (. Она читается естественно, но рискует упереться в лимит рекурсии на глубоко вложенном входе, поэтому версия со стеком безопаснее в Python.

Расширения, о которых спрашивают интервьюеры

Краевые случаи

Частые ошибки

1. Обработка каждой цифры как отдельного числа.
2. Забыли прибавить последнее sign * num в конце.
3. Извлечение из стека в неправильном порядке.
4. Не сбросили num после оператора.
5. Неправильная обработка ведущего минуса.

Как объяснить это на интервью

1. Уточните допустимые символы и встречается ли унарный минус.
2. Скажите, что проблемы приоритета нет, поэтому скобки — единственная сложность.
3. Опишите три переменные и что сохраняет стек.
4. Пройдитесь по 1-(2+3) на доске.
5. Назовите сложность, затем упомяните расширение Calculator II.

Связанная практика

Смотрите нашу шпаргалку по Big O для терминов сложности, руководство по AI-тренажёру LeetCode и руководство по ассистенту для собеседований по программированию. Valid Parentheses и Decode String используют ту же идею со стеком.

Проговаривайте трассировку вслух во время практики. Транскрипт mock-интервью показывает, объяснили ли вы назначение стека. Соблюдайте правила работодателя об AI-инструментах на любом живом ассессменте.