Обратная польская запись: вычисление стеком, ловушки Evaluate RPN и сортировочная станция

Коротко

Задача Evaluate RPN решается в десять строк. Сложность в ней не в идее, а в двух деталях: порядке операндов и делении. Их и разберём подробно, а потом дойдём до калькулятора со скобками.

Почему этой записи не нужны скобки

Сравните одни и те же выражения в двух формах:

В инфиксной записи оператор стоит между операндами, поэтому читателю приходится решать, какой оператор к чему относится. Для этого и придуманы приоритеты со скобками.

В постфиксной записи всё однозначно: оператор применяется к двум последним значениям, которые ещё никто не использовал. Других правил нет, и порядок вычислений задан самим порядком токенов.

Есть и другой взгляд. Выражение можно представить деревом, где внутренние узлы — операторы, а листья — числа:

    *
   / \
  +   3       (2 + 1) * 3
 / \
2   1

Обратная польская запись этого дерева — его обход post-order: левое поддерево, правое, корень. Получается 2 1 + 3 *. Обход pre-order даст прямую польскую запись * + 2 1 3, а in-order — привычную инфиксную, но уже без скобок и потому неоднозначную. Если обходы подзабылись, они есть в разборе задач на деревья.

Немного истории: прямую запись придумал логик Ян Лукасевич в 1924 году, отсюда и «польская». Обратный вариант предложили Бёркс, Уоррен и Райт в 1954-м, Чарльз Хэмблин развил идею в середине 1950-х, а Бауэр и Дейкстра независимо переоткрыли её в начале 1960-х.

Условие задачи

На LeetCode это задача 150, уровень Medium. На входе массив строк tokens: числа и операторы +, -, *, /. Нужно вернуть значение выражения.

["2", "1", "+", "3", "*"]   →  9    потому что (2 + 1) * 3
["4", "13", "5", "/", "+"]  →  6    потому что 4 + (13 / 5)

Важные детали условия на LeetCode:

• токенов от 1 до $10^4$, числа от −200 до 200, то есть бывают отрицательные;
• деление целочисленное, с усечением к нулю;
• выражение корректное, деления на ноль нет;
• и ответ, и все промежуточные результаты помещаются в 32 бита.

Решить можно прямо на сайте: задача на практике. Там функция называется evalRPN и лежит в классе Solution.

Наивное решение: сворачиваем выражение

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

import operator


def trunc_div(a: int, b: int) -> int:
    # Почему не a // b, разберём ниже
    quotient = abs(a) // abs(b)
    return quotient if (a < 0) == (b < 0) else -quotient


OPS = {
    "+": operator.add,
    "-": operator.sub,
    "*": operator.mul,
    "/": trunc_div,
}


def eval_rpn_naive(tokens: list) -> int:
    tokens = list(tokens)
    while len(tokens) > 1:
        i = next(k for k, t in enumerate(tokens) if t in OPS)
        value = OPS[tokens[i]](int(tokens[i - 2]), int(tokens[i - 1]))
        tokens[i - 2 : i + 1] = [str(value)]
    return int(tokens[0])

Это работает, но за $O(n^2)$: на каждом шаге мы заново ищем оператор и сдвигаем хвост списка. На входе 1 1 1 ... + + + из 10 001 токена у меня вышло около 300 мс против 1 мс у решения со стеком. В лимиты задачи это, возможно, и уложится, но на собеседовании такой вариант стоит назвать и сразу улучшить.

Решение через стек

Заметим, что при наивном подходе мы всё время смотрим на значения слева от текущего оператора, причём на самые свежие. Последнее записанное используется первым, а это как раз стек.

def eval_rpn(tokens: list) -> int:
    stack = []
    for token in tokens:
        if token in OPS:
            right = stack.pop()  # снимается первым
            left = stack.pop()
            stack.append(OPS[token](left, right))
        else:
            stack.append(int(token))
    return stack[-1]

Разберём второй пример, ["4", "13", "5", "/", "+"]:

Сложность. Каждый токен обрабатывается за $O(1)$, итого $O(n)$ по времени. Память $O(n)$: в худшем случае все числа идут в начале, как в 1 2 3 4 + + +, и стек вырастает примерно до $n/2$ элементов.

Ловушка 1: порядок операндов

Для 10 3 - правильный ответ 7. Первым со стека снимается 3, то есть правый операнд: он попал туда последним.

Ошибка встречается в трёх видах:

stack = [10, 3]
print(stack.pop() - stack.pop())  # -7

stack = [10, 3]
print(operator.sub(stack.pop(), stack.pop()))  # -7

stack = [10, 3]
a = stack.pop()
b = stack.pop()
print(a - b)  # -7, имена a и b только запутывают

Вторая форма особенно коварна. Строка OPS[token](stack.pop(), stack.pop()) выглядит аккуратно, но аргументы вычисляются слева направо, и правый операнд уезжает на место левого.

Ошибка живёт долго, потому что + и * коммутативны. Первый пример из условия её не поймает вообще: там только сложение и умножение. Поэтому заведите привычку называть переменные left и right и прогоняйте руками хотя бы ["10", "3", "-"] и ["13", "5", "/"].

Ловушка 2: деление в Python

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

Вот тест, на котором это видно:

["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]

Это 10 * (6 / (12 * -11)) + 17 + 5. Внутри считается 6 / -132: с усечением получается 0 и итоговый ответ 22, а с // получается −1 и ответ 12.

Как делить правильно

Есть два рабочих способа.

Через модули и знак. Это trunc_div из начала статьи. Считает только в целых, поэтому верен на любых числах.

Через int(a / b). Короче, и обычно пишут именно так. Но / возвращает float, и у этого способа есть граница:

print(int(9007199254740993 / 1))  # 9007199254740992, потеряли единицу
print(trunc_div(9007199254740993, 1))  # 9007199254740993

try:
    int(10**400 / 3)
except OverflowError as error:
    print(error)  # integer division result too large for a float

Где именно проходит граница? В Python деление целых округляется корректно, поэтому относительная погрешность не больше $2^{-53}$, то есть абсолютная не больше $|a/b| \cdot 2^{-53}$. Нецелое частное отстоит от ближайшего целого минимум на $1/|b|$. Значит, пока $|a| < 2^{53}$, округление не может перепрыгнуть через целое и int(a / b) даёт точный ответ. Я дополнительно прогнал по два миллиона случайных пар в 32-битном диапазоне и у границы $2^{53}$: расхождений нет.

Для условий LeetCode int(a / b) полностью безопасен. На собеседовании можно написать его и добавить: «здесь float, это нормально, потому что по условию значения 32-битные, а для больших чисел я бы делил через модули». Такая оговорка показывает, что вы понимаете границы своего решения.

В других языках

Ещё одна мелочь: в Python % согласован с //, поэтому -7 % 2 равно 1, а не −1.

В JavaScript есть своя ловушка, отрицательный ноль:

function evalRPN(tokens) {
  const ops = {
    '+': (a, b) => a + b,
    '-': (a, b) => a - b,
    '*': (a, b) => a * b,
    '/': (a, b) => Math.trunc(a / b),
  }
  const stack = []
  for (const token of tokens) {
    if (token in ops) {
      const right = stack.pop()
      const left = stack.pop()
      stack.push(ops[token](left, right))
    } else {
      stack.push(Number(token))
    }
  }
  // Math.trunc(-1 / 2) и 0 * -5 дают -0, а console.log так его и напечатает
  return stack.pop() + 0
}

-0 === 0 истинно, поэтому сравнение чисел ничего не заметит, но console.log(-0) выводит -0, и проверка по тексту вывода такое не простит. Прибавление нуля превращает -0 в обычный 0. Вариант a / b | 0 тоже усекает к нулю и избавляет от -0, но работает только в 32 битах: 2 ** 32 | 0 равно 0.

Ловушка 3: как отличить число от оператора

Отрицательные числа в токенах ломают самые очевидные проверки:

print("-11".isdigit())  # False: минус не цифра
print("-11"[0] in "+-*/")  # True: число приняли за оператор
print("" in "+-*/", "+-" in "+-*/")  # True True: это поиск подстроки

Надёжнее всего проверять токен целиком по словарю или множеству операторов, а всё остальное считать числом. Именно так сделано в eval_rpn выше: if token in OPS.

Что могут спросить дальше

Как проверить корректность записи?

Вычислять не нужно, достаточно следить за глубиной стека. Число добавляет единицу. Бинарный оператор требует глубину не меньше 2 и уменьшает её на один. В конце должно остаться ровно одно значение.

def is_valid_rpn(tokens: list) -> bool:
    depth = 0
    for token in tokens:
        if token in OPS:
            if depth < 2:
                return False
            depth -= 1
        else:
            depth += 1
    return depth == 1

["1", "+"] не пройдёт на операторе, а ["1", "2"] на финальной проверке. Отсюда же следует, что в корректном выражении чисел всегда на одно больше, чем операторов.

Можно ли обойтись без явного стека?

Можно через рекурсию: читаем токены с конца, и оператор сам собирает свои операнды.

def eval_rpn_recursive(tokens: list) -> int:
    tokens = list(tokens)

    def solve() -> int:
        token = tokens.pop()
        if token not in OPS:
            return int(token)
        right = solve()  # с конца первым собирается правый операнд
        left = solve()
        return OPS[token](left, right)

    return solve()

Стек здесь никуда не делся, он стал стеком вызовов. И в Python это проблема: на ["1"] + ["1", "+"] * 5000 глубина уйдёт в 5000 вызовов, а лимит по умолчанию равен 1000, и мы получим RecursionError.

Дополнительной памяти можно не тратить, если разрешено портить вход: начало самого tokens играет роль стека. Запись никогда не обгоняет чтение, поэтому непрочитанные токены остаются целыми.

def eval_rpn_in_place(tokens: list) -> int:
    top = 0  # tokens[:top] и есть стек
    for token in tokens:
        if token in OPS:
            top -= 2
            value = OPS[token](tokens[top], tokens[top + 1])
        else:
            value = int(token)
        tokens[top] = value
        top += 1
    return tokens[top - 1]

А если запись прямая?

Читаем справа налево тем же стеком, но порядок становится зеркальным: теперь первым снимается левый операнд. Хороший повод показать, что вы понимаете, откуда порядок берётся, а не выучили его.

def eval_prefix(tokens: list) -> int:
    stack = []
    for token in reversed(tokens):
        if token in OPS:
            left = stack.pop()
            right = stack.pop()
            stack.append(OPS[token](left, right))
        else:
            stack.append(int(token))
    return stack[-1]


print(eval_prefix(["-", "10", "3"]))  # 7

Как получить RPN: сортировочная станция

Самый естественный следующий вопрос: откуда вообще взять постфиксную запись, если на входе строка 2 * (3 + 4) - 5? Для этого есть алгоритм сортировочной станции (shunting yard), который Дейкстра описал в отчёте 1961 года о трансляции Algol 60. Название из железной дороги: числа сразу едут на выходной путь, а операторы ждут своей очереди в тупике, то есть в стеке.

Правила такие:

1. Число сразу идёт в выход.
2. ( кладём в стек.
3. ) выталкивает операторы в выход до ближайшей (, а саму скобку выбрасывает.
4. Оператор сначала выталкивает со стека всё, что должно выполниться раньше него, затем кладётся сам.
5. В конце выталкиваем весь остаток стека.

Единственное нетривиальное правило четвёртое. Вершину стека выталкиваем, если её приоритет выше или если приоритеты равны, а входящий оператор левоассоциативный.

PRECEDENCE = {"+": 1, "-": 1, "*": 2, "/": 2, "^": 4}
RIGHT_ASSOC = {"^"}


def must_pop(top: str, incoming: str) -> bool:
    if top == "(":
        return False
    if PRECEDENCE[top] != PRECEDENCE[incoming]:
        return PRECEDENCE[top] > PRECEDENCE[incoming]
    return incoming not in RIGHT_ASSOC


def to_rpn_simple(tokens: list) -> list:
    output, ops = [], []
    for token in tokens:
        if token.isdigit():
            output.append(token)
        elif token == "(":
            ops.append(token)
        elif token == ")":
            while ops[-1] != "(":
                output.append(ops.pop())
            ops.pop()
        else:
            while ops and must_pop(ops[-1], token):
                output.append(ops.pop())
            ops.append(token)
    while ops:
        output.append(ops.pop())
    return output

Прогоним 2 * (3 + 4) - 5:

На токене - умножение вытолкнулось, потому что у него приоритет выше. Каждый токен попадает в стек и выходит из него не больше одного раза, поэтому алгоритм линейный: $O(n)$ по времени и памяти.

Ассоциативность

Вычитание левоассоциативно: 10 - 3 - 2 это (10 - 3) - 2 = 5. Поэтому равный приоритет выталкивает, и получается 10 3 - 2 -. Без этого выйдет 10 3 2 - -, а это уже 9.

Степень правоассоциативна: 2 ^ 3 ^ 2 это 2 ^ 9 = 512. Здесь равный приоритет не выталкивает, и получается 2 3 2 ^ ^.

Унарный минус и проверка ошибок

Простая версия не отличает - в 5 - 3 от - в -3 и молча принимает мусор вроде 2 3 +. Обе проблемы решаются одним флагом: ждём ли мы сейчас операнд. Минус на месте операнда — унарный.

Унарному минусу нужен отдельный токен, потому что в RPN он снимает со стека одно значение, а не два. Обозначим его ~. У него две особенности:

• как любой префиксный оператор, он ничего не выталкивает при входе, иначе 2 ^ -3 развалится;
• его приоритет выше *, но ниже ^, чтобы -2 ^ 2 было -(2 ^ 2), как в Python.

import re

TOKEN = re.compile(r"\s*(\d+|[-+*/^()])")
PRECEDENCE["~"] = 3
RIGHT_ASSOC.add("~")


def tokenize(expr: str) -> list:
    expr = expr.strip()
    tokens, pos = [], 0
    while pos < len(expr):
        match = TOKEN.match(expr, pos)
        if match is None:
            raise ValueError(f"не разобрать: {expr[pos:]!r}")
        tokens.append(match.group(1))
        pos = match.end()
    return tokens


def to_rpn(expr: str) -> list:
    output, ops = [], []
    expect_operand = True

    for token in tokenize(expr):
        if token.isdigit():
            if not expect_operand:
                raise ValueError(f"два числа подряд: {token}")
            output.append(token)
            expect_operand = False
        elif token == "(":
            if not expect_operand:
                raise ValueError("перед скобкой нет оператора")
            ops.append(token)
        elif token == ")":
            if expect_operand:
                raise ValueError("перед ) нет числа")
            while ops and ops[-1] != "(":
                output.append(ops.pop())
            if not ops:
                raise ValueError("лишняя )")
            ops.pop()
        elif expect_operand:
            if token != "-":
                raise ValueError(f"оператор {token} без левого операнда")
            ops.append("~")
        else:
            while ops and must_pop(ops[-1], token):
                output.append(ops.pop())
            ops.append(token)
            expect_operand = True

    if expect_operand:
        raise ValueError("выражение оборвалось")
    while ops:
        if ops[-1] == "(":
            raise ValueError("не закрыта (")
        output.append(ops.pop())
    return output


print(" ".join(to_rpn("-2 ^ 2")))  # 2 2 ^ ~
print(" ".join(to_rpn("2 ^ -3")))  # 2 3 ~ ^
print(" ".join(to_rpn("-(2 + 3) * 4")))  # 2 3 + ~ 4 *

Обратите внимание на токенизатор: re.findall здесь был бы ошибкой, он молча пропустит $ в 2 $ 3. Проверка позиции такой мусор не пропускает.

Я сверил to_rpn с вычислением тех же выражений интерпретатором Python на 100 000 случайных выражений со скобками, унарным минусом и степенями. Расхождений нет.

Калькулятор на двух стеках

Промежуточный список токенов не обязателен. Если вместо записи оператора в выход сразу применять его к стеку значений, получится готовый калькулятор. Это и есть решение семейства Basic Calculator с LeetCode: в задаче 224 есть скобки и + -, в 227 есть + - * / без скобок, а в 772 есть всё сразу.

BINARY = {**OPS, "^": operator.pow}


def apply_top(values: list, ops: list) -> None:
    op = ops.pop()
    if op == "~":
        values.append(-values.pop())
        return
    right = values.pop()
    left = values.pop()
    values.append(BINARY[op](left, right))


def calculate(expr: str) -> int:
    values, ops = [], []
    expect_operand = True

    for token in tokenize(expr):
        if token.isdigit():
            values.append(int(token))
            expect_operand = False
        elif token == "(":
            ops.append(token)
        elif token == ")":
            while ops[-1] != "(":
                apply_top(values, ops)
            ops.pop()
        elif expect_operand:
            ops.append("~")
        else:
            while ops and must_pop(ops[-1], token):
                apply_top(values, ops)
            ops.append(token)
            expect_operand = True

    while ops:
        apply_top(values, ops)
    return values[-1]


print(calculate("2 * (3 + 4) - 5"))  # 9
print(calculate("3 + 4 * 2 / (1 - 5)"))  # 1
print(calculate("-7 / 2"))  # -3
print(calculate("2 ^ 3 ^ 2"))  # 512

Проверки ошибок я здесь опустил, они такие же, как в to_rpn. И учтите, что 2 ^ -3 даст float: в чисто целочисленном калькуляторе отрицательную степень лучше запретить.

Где это встречается вживую

RPN не только учебная задача.

Калькуляторы. HP-9100A (1968) и HP-35 (1972), а из советских Б3-34 и МК-61.

Языки. Forth и PostScript построены вокруг стека, а утилита dc до сих пор есть во многих Unix-системах:

echo "2 1 + 3 * p" | dc   # 9

Виртуальные машины. Байткод JVM, CPython и WebAssembly устроен как стековая машина. Посмотрите сами на (a + b) * c:

import dis


def f(a, b, c):
    return (a + b) * c


dis.dis(f)

В Python 3.9 внутри окажутся a, b, BINARY_ADD, c, BINARY_MULTIPLY, то есть та самая запись a b + c *. В свежих версиях CPython имена инструкций другие, но принцип тот же. Именно поэтому компилятор и генерирует код обходом дерева post-order.

Чек-лист перед сдачей

1. Правый операнд снимается первым, переменные названы left и right.
2. Деление усекает к нулю, а не округляет вниз.
3. Токен сверяется со множеством операторов, поэтому -11 считается числом.
4. Проговорены тесты: ["5"], ["10", "3", "-"], ["-7", "2", "/"], ["-1", "2", "/"].
5. Названа сложность: $O(n)$ по времени и памяти.

В инфиксной части добавляются ещё три пункта: ассоциативность равных приоритетов, унарный минус как отдельный токен и незакрытые скобки.

Прорешайте Evaluate RPN без подсказок, затем напишите to_rpn с чистого листа. Для других применений стека пригодятся валидные скобки и монотонный стек.