Evaluate Reverse Polish Notation (Обратная польская запись)
Описание: Вычислите значение арифметического выражения в обратной польской записи. Допустимые операторы: +, -, *, /. Деление целочисленное с отбрасыванием дробной части.
Пример 1:
Вход: tokens = ["2","1","+","3","*"]
Выход: 9
Объяснение: (2 + 1) * 3 = 9
Пример 2:
Вход: tokens = ["4","13","5","/","+"]
Выход: 6
Объяснение: 4 + (13 / 5) = 4 + 2 = 6
Ограничения:
1 <= tokens.length <= 10⁴
Деление на ноль не встречается
Рекомендуемая временная и пространственная сложность
O(n) по времени и O(n) по памяти.
Подсказка 1
В постфиксной записи операнды идут перед оператором. Какая структура позволяет забрать два последних значения?
Подсказка 2
Стек: число — кладём, оператор — снимаем два верхних и кладём результат.
Подсказка 3
Порядок важен: первым снимается правый операнд. Для вычитания и деления это критично.