e-olymp
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.

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