Evaluate Reverse Polish Notation

Q: Какова временная сложность вычисления обратной польской записи?

Решение со стеком работает за время O(n) для n токенов: каждое число добавляется в стек один раз, а для каждого оператора выполняются два извлечения и одно добавление. В стеке хранится до примерно n/2 значений, поэтому затраты памяти составляют O(n) .

Q: Почему для обратной польской записи не нужны скобки?

В обычной записи для выражения 3 + 4 * 2 нужно правило приоритета или скобки, чтобы указать, какая операция выполняется первой. В обратной польской записи оператор всегда применяется к двум значениям непосредственно перед ним, поэтому порядок токенов всё определяет: 3 4 2 * + — это 11, а 3 4 + 2 * — 14.

Q: Как выполнить деление с округлением к нулю в Python?

Используй int(a / b) . Оператор // округляет вниз, поэтому -7 // 2 равно -4, а int(-7 / 2) равно -3. Деление с плавающей точкой достаточно точное для 32-битных значений. Для больших целых чисел раздели абсолютные значения с помощью // и верни знак.

СреднеСтек

+10

Тебе дано арифметическое выражение в обратной польской записи в виде массива токенов. Каждый оператор стоит сразу после двух своих операндов, поэтому 3 4 + означает 3 + 4, а 3 4 + 2 * означает (3 + 4) * 2, без скобок. Каждый токен — это целое число или один из операторов +, -, * и /.

Верни значение выражения. При делении дробная часть отбрасывается в сторону нуля: 7 / 2 — это 3, а -7 / 2 — это -3.

Функция

evalRPN(tokens: string-array) → integer

tokensstring-array: числа и операторы выражения по порядку
Возвращаетinteger: значение выражения

Ограничения

1 ≤ tokens.length ≤ 10⁴
Каждый токен — это +, -, *, / или целое число от -200 до 200, записанное в десятичной системе счисления, с ведущим знаком минус, если оно отрицательное.
tokens — допустимое выражение в обратной польской нотации.
Деления на ноль не происходит, и каждое промежуточное и конечное значение больше -2³¹ и меньше 2³¹.

Примеры

Ввод: tokens = ["8", "3", "-", "4", "*"]
Вывод: 20
Пояснение: - применяется сначала к 8, затем к 3, поэтому результат равен 5, а не -5. Затем * умножает это 5 на 4, что даёт 20.

Ввод: tokens = ["6", "2", "9", "3", "/", "-", "*"]
Вывод: -6
Пояснение: / использует два последних значения: 9, делённое на 3, равно 3. Затем - вычисляет 2 минус 3, что равно -1, а * умножает 6 на -1.

Ввод: tokens = ["10", "-7", "2", "/", "+"]
Вывод: 7
Пояснение: Токен -7 — это число, а не оператор. -7, делённое на 2, равно -3.5; при усечении к нулю получается -3, а не -4, и 10 плюс -3 равно 7.

Дополнительный вопрос

Можешь ли ты восстановить выражение в обычной записи, например (3 + 4) * 2, добавив скобки только там, где они меняют смысл?

Решение

Каждый оператор применяется к двум значениям непосредственно перед ним, причём любое из них может быть результатом предыдущего оператора. Поэтому стек значений позволяет вычислить выражение за один проход. Подводные камни — порядок операндов для - и /, различение оператора - и числа -7, а также целочисленное деление с отбрасыванием дробной части.

Сверни первый оператор, повтори

Верно, но не успевает на самых больших тестах

Идея

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

Каждый раунд поиск начинается заново с начала. Если за 5,000 числами следуют 4,999 операторов, то в каждом раунде первый оператор находится примерно посередине, поэтому только на поиск просматривается около 1.25 × 10^7 токенов.

Алгоритм

Скопируй токены в список, который можно изменять.
Просматривай список с начала до первого оператора на позиции k.
Примени его к числам на позициях k-2 (слева) и k-1 (справа).
Замени три токена на позициях k-2, k-1 и k результатом.
Повторяй, пока не останется один токен, и верни его как число.

def evalRPN(tokens):
    items = list(tokens)
    while len(items) > 1:
        # Find the first operator. Everything to its left is a plain number.
        k = 0
        while items[k] not in ("+", "-", "*", "/"):
            k += 1
        left, right, op = int(items[k - 2]), int(items[k - 1]), items[k]
        if op == "+":
            value = left + right
        elif op == "-":
            value = left - right
        elif op == "*":
            value = left * right
        else:
            value = int(left / right)  # int() truncates toward zero
        # Replace the three tokens "left right op" with the number they stand for.
        items[k - 2:k + 1] = [str(value)]
    return int(items[0])

Один проход со стеком значений

Идея

Храните значения слева от оператора в стеке, вместо того чтобы считывать их заново. Число помещается в стек. Оператор извлекает из стека два значения, объединяет их и помещает результат обратно — там он ждёт следующего оператора, как и любое другое значение. В стеке всегда хранятся значения всех обработанных к этому моменту частей в исходном порядке, поэтому оператор всегда применяется к двум верхним значениям. Верхнее значение — правый операнд, поскольку оно было получено последним.

В 6 2 9 3 / - * оператор / извлекает из стека сначала 3, затем 9 и помещает обратно 3, оператор - извлекает из стека сначала 3, затем 2 и помещает обратно -1, а оператор * вычисляет 6 × -1 = -6. Каждый токен обрабатывается один раз: время O(n) и память O(n).

Алгоритм

Начните с пустого стека.
Для каждого токена, являющегося числом, поместите его значение в стек.
Для каждого оператора извлеките из стека правый операнд, затем левый.
Вычислите left op right, округляя результат деления / к нулю, и поместите результат в стек.
После последнего токена верните единственное значение в стеке.

def evalRPN(tokens):
    stack = []  # values of the parts read so far, the newest on top
    for token in tokens:
        if token in ("+", "-", "*", "/"):
            # The right operand was pushed last, so it comes off first.
            right = stack.pop()
            left = stack.pop()
            if token == "+":
                stack.append(left + right)
            elif token == "-":
                stack.append(left - right)
            elif token == "*":
                stack.append(left * right)
            else:
                # int() truncates toward zero; // would round -7 / 2 down to -4.
                stack.append(int(left / right))
        else:
            stack.append(int(token))
    return stack[0]

Ловушки и крайние случаи

Перестановка операндов. Первый извлечённый элемент — правый операнд: ["3", "5", "-"] равно -2, а ["2", "9", "/"] равно 0, а не 4.
Определение операторов по первому символу. -7 начинается со знака минус, но это число, поэтому сравнивайте токен целиком.
Округление вниз вместо усечения. // в Python, / в Ruby, %/% в R и math.floor в Lua превращают -7 / 2 в -4, а -1 / 3 — в -1.
Вывод -0. В JavaScript и Lua 0 * -5 и Math.trunc(-1 / 3) дают отрицательный ноль. Добавьте 0 к конечному значению.

Частые вопросы4

Какова временная сложность вычисления обратной польской записи?

Решение со стеком работает за время O(n) для n токенов: каждое число добавляется в стек один раз, а для каждого оператора выполняются два извлечения и одно добавление. В стеке хранится до примерно n/2 значений, поэтому затраты памяти составляют O(n).

Почему для обратной польской записи не нужны скобки?

В обычной записи для выражения 3 + 4 * 2 нужно правило приоритета или скобки, чтобы указать, какая операция выполняется первой. В обратной польской записи оператор всегда применяется к двум значениям непосредственно перед ним, поэтому порядок токенов всё определяет: 3 4 2 * + — это 11, а 3 4 + 2 * — 14.

Как выполнить деление с округлением к нулю в Python?

Используй int(a / b). Оператор // округляет вниз, поэтому -7 // 2 равно -4, а int(-7 / 2) равно -3. Деление с плавающей точкой достаточно точное для 32-битных значений. Для больших целых чисел раздели абсолютные значения с помощью // и верни знак.

Как преобразовать обычное выражение в обратную польскую запись?

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

def evalRPN(tokens):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргумент

tokens = ["8", "3", "-", "4", "*"]

Ожидаемый вывод