Competitions

# Implementation: Data Structures

# 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.

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