Напиши программу для вычисления значения арифметического выражения записанного с помощью обратной польской записи. Обратная польская запись - это форма записи математических и…
Напиши программу для вычисления значения арифметического выражения записанного с помощью обратной польской записи. Обратная польская запись - это форма записи математических и логических выражений, в которой операнды расположены перед знаками операций. Например, запись арифметического выражения выражения в обратной польской нотации 1 2 + 4 * 3 + соответствует арифметическому выражению (1 + 2) * 4 + 3. Вычисление выражения в обратной польской записи основано на использовании стека, при этом можно сформулировать следующий алгоритм: 1. запускаем цикл по всем символам: 2. если символ это число - оно помещается в стек. 3. если символ это знак операции, то со стека снимается два числа и соответствующая операция выполняется над этими числами. Результат операции помещается в стек. 4. после завершения цикла в стеке остался один элемент - результат арифметического выражения. Входные данные: Строка, содержащая числа и арифметические операции (+, -, *, / - деление нацело) разделенные одним пробелом. Выходные данные: Одной целое число - результат арифметического выражения. Пример ввода: 7 2 3 * - Пример вывода: 1
Для решения данной задачи потребуется написать программу, которая будет вычислять значение арифметического выражения, записанного в обратной польской записи. По вашему описанию, алгоритм решения следующий:
- Создаем стек, где будем хранить числа.
- Проходим по каждому символу во входной строке:
- Если символ является числом, помещаем его в стек.
- Если символ - знак операции, извлекаем два числа из стека, выполняем операцию и помещаем результат обратно в стек.
- После обработки всей строки в стеке должно остаться только одно число, которое и будет результатом вычисления выражения.
Напишем программу на Python, реализующую данное решение:
def eval_reverse_polish(input_str):
stack = []
operators = {'+': lambda x, y: x + y,
'-': lambda x, y: x - y,
'*': lambda x, y: x * y,
'/': lambda x, y: x // y} # используем целочисленное деление
for token in input_str.split():
if token.isdigit():
stack.append(int(token))
elif token in operators:
b = stack.pop()
a = stack.pop()
stack.append(operators[token](a, b))
return stack[0]
input_str = '7 2 3 * -'
result = eval_reverse_polish(input_str)
print(result) # Результат вычисления выражения
Таким образом, вы получите результат выполнения арифметического выражения в обратной польской записи из примера ввода: 1.
