Competitions

# Reverse Polish notation

Reverse Polish notation (RPN) is a mathematical notation in which every operator follows all of its operands. It is also known as postfix notation and does not need any parentheses as long as each operator has a fixed number of operands.

For example:

• the expression 2 + 4 in RPN is represented like 2 4 +
• the expression 2 * 4 + 8 in RPN is represented like 2 4 * 8 +
• the expression 2 * (4 + 8) in RPN is represented like 2 4 8 + *

Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operators are +, -, *, /. Operator / is an integer division (14 / 3 = 4). Each operand may be an integer or another expression.

#### Input

One line contains expression written in Reverse Polish notation. The length of expression is no more than 100 symbols.

#### Output

Print the value of expression given in Reverse Polish notation.

Time limit 1 second
Memory limit 128 MiB
Input example #1
2 4 * 8 +

Output example #1
16

Input example #2
2 4 8 + *
Output example #2
24

Input example #3
3 2 * 11 -

Output example #3
-5

Input example #5
2 5 * 4 + 3 2 * 1 + /
Output example #5
2