Постфиксная запись В постфиксной записи (или обратной польской записи) операция записывается после двух операндов. Например, сумма двух чисел A и B записывается как A B +. Запись B C + D ∗ обозначает привычное нам (B+C)∗D, а запись A B C + D ∗ + означает A+(B+C)∗D. Достоинство постфиксной записи в том, что она не требует скобок и дополнительных соглашений о приоритете операторов для своего чтения — все операции выполняются подряд слева направо. Входные данные В единственной строке записано выражение в постфиксной записи, содержащее цифры и операции +, −, ∗. Цифры и операции разделяются пробелами. В конце строки может быть произвольное количество пробелов. Выходные данные Необходимо вывести значение записанного выражения. Гарантируется, что результат по модулю не превосходит 2⋅109. Примеры Ввод 8 9 + 1 7 - * Вывод -102 Решите на c++ или Python
stack = []
a = list(map(str, input().split()))
for elem in A:
if elem in '+-*':
a = stack[-2]
b = stack[-1]
stack.pop()
stack.pop()
if elem == '+':
result = a+b
elif elem == '-':
result = a - b
else:
result = a * b
stack.append(result)
else:
stack.append(int(elem))
print(stack[0])
Объяснение:
python
Шаг 1: Создайте пустой стек.
Шаг 2: Прочитайте выражение посимвольно слева направо.
Шаг 3: Если прочитанный символ является числом, преобразуйте его в число и поместите его в стек.
Шаг 4: Если прочитанный символ является оператором, значит, в стеке уже есть два числа, над которыми нужно выполнить эту операцию. Извлеките эти два числа из стека и выполните операцию. Затем поместите полученный результат обратно в стек.
Шаг 5: Повторяйте шаги 3 и 4, пока не прочитаете всё выражение.
Шаг 6: В конце, когда весь стек прочитан и обработан, в стеке останется только одно число — значение выражения. Извлеките это число из стека и выведите его.
Теперь давайте решим пример, указанный в задаче.
Входные данные: 8 9 + 1 7 - *
Шаг 1: Создаем пустой стек.
Шаг 2: Читаем выражение слева направо.
Шаг 3: Прочитываем "8". Это число, поэтому помещаем его в стек.
Стек: [8]
Шаг 4: Прочитываем "9". Это также число, поэтому помещаем его в стек.
Стек: [8, 9]
Шаг 4: Прочитываем "+". Это оператор, поэтому извлекаем два числа из стека (последние два числа) и выполняем операцию сложения. Результат (8 + 9 = 17) помещаем обратно в стек.
Стек: [17]
Шаг 4: Прочитываем "1". Это число, поэтому помещаем его в стек.
Стек: [17, 1]
Шаг 4: Прочитываем "7". Это число, поэтому помещаем его в стек.
Стек: [17, 1, 7]
Шаг 4: Прочитываем "-". Это оператор, поэтому извлекаем два числа из стека (последние два числа) и выполняем операцию вычитания. Результат (1 - 7 = -6) помещаем обратно в стек.
Стек: [17, -6]
Шаг 4: Прочитываем "*". Это оператор, поэтому извлекаем два числа из стека (последние два числа) и выполняем операцию умножения. Результат (-6 * 17 = -102) помещаем обратно в стек.
Стек: [-102]
Шаг 5: Вся строка прочитана и обработана. В стеке осталось только одно значение, -102.
Шаг 6: Извлекаем это значение из стека и выводим его.
Выходное значение: -102
Таким образом, ответ на данный пример равен -102.
Мы решили данную задачу, используя алгоритм преобразования постфиксной записи в выражение.