Напишите программу, которая производит вычисление выражения, записанного в обратной польской нотации (ОПН).
В ОПН нет ни скобок, ни приоритета операторов («умножение раньше сложения»).
Чтобы прочитать выражение, записанное в таком формате, нужно просматривать выражение строго последовательно. Вводимые значения последовательно добавляются в стек. Когда встречается символ операции, то из стека извлекаются последние положенные туда значения, с ними проделывается эта операция и результат возвращается в стек.
Если для операции важен порядок значений, с которыми она производится, то первым идёт число, лежавшее в стеке глубже. В частности, если операция — вычитание, то из предпоследнего числа в стеке вычитается последнее, а не наоборот.
Изначально стек пустой, в результате полного вычисления выражения в нём должно остаться одно значение — результат вычислений.
Первый пример следует читать так: в стек последовательно добавляются значения 7 2 3
, а затем встречаем знак операции *
. Тогда значения 2
и 3
извлекаются, перемножаются, результат 6
кладётся обратно в стек. Следующий знак извлекает из стека два оставшихся в нём значения 7
и 6
, вычитает одно из другого и кладёт результат снова в стек. Выражение закончилось, в стеке одно число — 1
, это и есть результат вычисления.
Формат ввода
Вводится одна строка, содержащая разделённые пробелами целые числа и знаки операций +
, -
, *
, которые вместе составляют корректное выражение в обратной польской нотации.
Формат вывода:
Выводится одно целое число — результат вычисления выражения.
Пример
Ввод
7 2 3 * -
Вывод
1
Ввод
10 15 - 7 *
Вывод
-35
Решение
Польский калькулятор проще всего реализовать с помощью стека (читается как стэк). К счастью, списки в python настолько гибки, что стек по сути, это когда ты добавляешь элемент в конец списка, и берешь элемент тоже из конца списка.
Считываем строку и разбиваем ее на токены (split).
Заводим пустой список stack. Будем с ним работать по правилам стека.
Пока список токенов не пустой достаем последний токен.
Если это число, то записываем его в стек. В противном случае мы имеем дело с операцией. Разбираем тип операции и в зависимости от того что это за операция достаем из стека значения.
Результат вычислений будет находиться в единственном элементе стека.
Посмотреть код
Решение
string = input()
tokens = string.split(' ')
operators = ['+', '-', '*', '/']
stack = []
while tokens != []:
value = tokens.pop(0)
if value.isdigit():
stack.append(int(value))
else:
match value:
case '+':
stack.append(stack.pop() + stack.pop())
case '-':
stack.append(stack.pop(-2) - stack.pop())
case '*':
stack.append(stack.pop() * stack.pop())
case '/':
stack.append(stack.pop(-2) / stack.pop())
print(stack[-1])
while tokens != []: равно while tokens:
Спасибо за комментарий, об этом я рассказываю в этой статье.
А тут, я предполагаю, что еще не все освоились с такой особенностью языка и поэтому показываю неправильный с точки зрения PEP8, но более понятный для людей изучавших другой язык программирования, способ.