Evaluate Reverse Polish Notation

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

Решение со стеком работает за время O(n) для n токенов: каждое число помещается в стек один раз, а каждый оператор выполняет два извлечения и одно добавление. Стек может содержать до примерно n/2 значений, поэтому пространственная сложность составляет O(n) . Последовательное свёртывание первого оператора занимает 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.

+18 скрытых тестов при отправке

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

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

Решение

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

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

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

Идея

Именно так вы вычислили бы значение на бумаге. Найдите самый левый оператор. Перед ним нет операторов, поэтому два токена непосредственно перед ним — это обычные числа, и они являются его операндами. Вычислите результат и замените эти три токена одним числом. Выражение стало короче, но по-прежнему означает то же самое. Повторяйте, пока не останется одно число.

Возьмём ["6", "2", "9", "3", "/", "-", "*"]. Первый оператор — /, поэтому 9 3 / превращается в 3: ["6", "2", "3", "-", "*"]. Затем 2 3 - превращается в -1: ["6", "-1", "*"]. Затем 6 -1 * превращается в -6 — это и есть ответ.

Это правильно, потому что на каждом шаге законченный фрагмент a b op заменяется своим значением, и следующие за ним операторы видят это значение именно там, где находился фрагмент. Это медленно, потому что на каждом шаге поиск начинается заново с начала, а затем в середине массива закрывается пробел. Если взять 5,000 чисел, за которыми следуют 4,999 операторов, первый оператор будет находиться примерно посередине на протяжении всех 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", "/", "-", "*"]. Четыре числа помещаются в стек: [6, 2, 9, 3]. Оператор / снимает 3, а затем 9 и помещает результат 9 / 3 = 3: [6, 2, 3]. Оператор - снимает 3, а затем 2 и помещает результат 2 - 3 = -1: [6, -1]. Оператор * снимает -1, а затем 6 и помещает результат 6 * -1 = -6. Остаётся одно значение — это и есть ответ.

Почему это работает: в каждый момент стек содержит значения всех прочитанных к этому моменту целых частей в исходном порядке, а оператор всегда применяется к последним двум из них. Верхнее значение стека — правый операнд, потому что оно было получено последним, поэтому снимайте его первым. Ошибка в порядке проявляется только с операторами - и /, где результатом 8 3 - должно быть 5, а не -5.

В некоторых языках при делении нужно быть внимательным. Выражение округляет в сторону нуля, но // в Python, / в Ruby и %/% в R округляют вниз, превращая -3.5 в -4. Каждое число помещается в стек один раз, а каждый оператор снимает два значения и помещает одно, поэтому проход занимает O(n) времени, а в стеке никогда не бывает больше 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 начинается со знака минуса, но это число. Сравнивай токен целиком или проверяй, что он состоит из одного символа.
Округлять вниз вместо усечения. -7 / 2 должно давать -3, а -1 / 3 — 0. // в Python, / в Ruby, %/% в R и math.floor в Lua дают -4 и -1.
Выводить -0. В JavaScript и Lua каждое число — число с плавающей точкой, поэтому 0 * -5 и Math.trunc(-1 / 3) дают отрицательный ноль, который выводится как -0. Добавь 0 к итоговому значению, чтобы получить 0.
Считывать число по одной цифре за раз. Токены вроде 13 и -200 состоят из нескольких символов; разбирай токен целиком.
Предполагать, что последний токен — оператор. Одно число, например ["7"], — это корректное выражение со значением 7.

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

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

Решение со стеком работает за время O(n) для n токенов: каждое число помещается в стек один раз, а каждый оператор выполняет два извлечения и одно добавление. Стек может содержать до примерно n/2 значений, поэтому пространственная сложность составляет O(n). Последовательное свёртывание первого оператора занимает 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 бита. Для сколь угодно больших целых чисел раздели абсолютные значения с помощью //, а затем верни знак.

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

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

Python

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

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

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

Ожидается