Условие задачи

Дан массив строк tokens, который представляет арифметическое выражение в обратной польской записи.

Необходимо вычислить выражение и вернуть целое число, которое представляет его значение.

Обратите внимание на следующее:

• Допустимые операторы: +, , и /.
• Каждый операнд может быть целым числом или другим выражением.
• Деление между двумя целыми числами всегда округляется в сторону нуля.
• Не будет деления на ноль.
• Ввод представляет собой допустимое арифметическое выражение в обратной польской записи.
• Ответ и все промежуточные вычисления могут быть представлены в 32-битном целом числе.

Объяснение

Для решения задачи необходимо написать программу, которая будет принимать на вход массив строк tokens и возвращать результат вычисления арифметического выражения в обратной польской записи.

Примеры

Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

Input: tokens = ["4","13","5","/","+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6

Решение

Для решения задачи мы можем использовать стек. Мы будем проходиться по каждому элементу массива tokens и, если это операнд, то мы добавим его в стек. Если же это оператор, то мы извлечем два последних операнда из стека, выполним соответствующую операцию и результат добавим обратно в стек. В конце, когда мы прошлись по всем элементам массива tokens, на вершине стека будет находиться результат вычисления всего выражения.

Пример:

Input: tokens = ["2","1","+","3","*"]

1. Добавляем 2 в стек: [2]
2. Добавляем 1 в стек: [2, 1]
3. Выполняем операцию "+" над 2 и 1, результат (3) добавляем в стек: [3]
4. Добавляем 3 в стек: [3, 3]
5. Выполняем операцию "*" над 3 и 3, результат (9) добавляем в стек: [9]
6. Конец выражения, результат на вершине стека: 9

Реализация на Python