Evaluate a postfix bill

Problem

In postfix form the operator comes after its two numbers: 2 3 4 * + means 2 + 3 × 4. Read a postfix expression with the operators +, - and * and print its value.

Input, output and limits

Input: The first line has n, the number of tokens. The next line has n tokens: integers or one of + - *.
Output: The value of the expression.
Constraints: 1 ≤ n ≤ 1000
The expression is valid
Every value fits in a long

Examples

Example

Input

5
2 3 4 * +

Output

3 × 4 = 12, then 2 + 12 = 14.

Hints

Try the problem first. Open one hint at a time.

Hint 1

A number goes on the stack. An operator pops two numbers, applies itself and pushes the result.

Hint 2

Pop the right operand first, then the left operand. The order matters for -.

Hint 3

A token is an operator only if it is exactly +, - or *; -5 is a number.

Write your Java code, run it on the examples and submit it to hidden tests.

Solve in the editor

All Java problems

Problem

Input, output and limits

Examples

Hints

More Queues, Stacks & Priority Queues problems

Problem

Input, output and limits

Examples

Hints

More Queues, Stacks & Priority Queues problems