Рассмотрим стек, который поддерживает выполнение двух типов действий:
- Добавить заданное число в стек.
- Извлечь два числа из стека, произвести над ними арифметическую операцию (сложение или умножение) и добавить результат этой арифметической операции в стек.
Вам задана строка, описывающая последовательность действий над стеком. i-ый символ строки соответствует i-ому действию, которое надо выполнить:
- Если i-й символ является цифрой, то нужно добавить в стек число, соответствующее этой цифре.
- Если i-й символ «+» или «*», то нужно выполнить арифметическую операцию, соответствующую этому символу.
Изначально стек пуст. Выведите число, которое окажется на вершине стека после выполнения всех заданных действий.
Выходные данные
Выведите единственное число — верхний элемент стека после выполнения заданных операций.
Примечание
В первом примере действия над стеком эквивалентны вычислению выражения (1+2)*3+6*6.
Во втором примере используется только добавление чисел в стек, и ответом будет последнее добавленное число.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
12+3*66*+
|
45
|
|
2
|
149
|
9
|