Evaluate Reverse Polish Notation

Средняя№150вычисление

Дано арифметическое выражение в обратной польской записи — список токенов: целые числа и операции + − × ÷, каждая операция стоит после двух своих операндов. Нужно вычислить его значение. Деление оставляет только целую часть, округляя к нулю, а выражение всегда правильное. Наш пример: 3 10 − 4 × 5 ÷, то есть (3 − 10) × 4 ÷ 5 — ответ −5.

150 Evaluate Reverse Polish NotationРазбор · 1×

Пример: 3 10 − 4 × 5 ÷. Под токенами — стек чисел, самое новое справа, под ним — операция, которую считаем.

токены031102−344×556÷nums—
ещё не прочитанt, читаем сейчас; только что положенное числов стекеснятые операндыуже прочитанответ

Начинаем с пустого стека чисел

01/25
сначала · назад · пуск · шаг
Скорость
1function evalRPN(tokens):
2 nums = empty stack
3 for each t in tokens:
4 if t is an operator:
5 right = pop from nums
6 left = pop from nums
7 push calc(left, t, right) onto nums
8 else:
9 push int(t) onto nums
10 return the only number in nums
состояние
tokens
["3", "10", "-", "4", "*", "5", "/"]
nums
[]
t
–
left
–
right
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. В этой записи операция стоит сразу после того, как оба её операнда готовы, поэтому это два самых новых числа — два верхних в стеке.
  2. Результат кладём обратно одним числом — ровно таким, какое может понадобиться следующей операции как операнд, поэтому выражение сворачивается изнутри наружу.
  3. Верх записан последним, значит, это правый операнд: для − и ÷ первое снятое число идёт справа. Отбрасывание к нулю превращает −5,6 в −5.

Сложность

Время O(n): каждый токен читаем один раз, а push и pop — O(1). Память O(n): если числа идут подряд в начале, почти все ждут в стеке.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.