## Reverse Polish NotationProblem #181 |

*Thanks to user FolieWasHere for suggesting this problem!*

Most of us get used to using **infix** math notation while writing arithmetic expressions, like this:

```
2 * 4 + 9 / 3
```

Meanwhile in programming the concept of **postfix** notation is often exploited. This form (often called also
Reverse Polish Notation) was used in many programmable
calculators and in some languages (e.g. `Forth`

) to simplify processing. Moreover one of the popular ways of
parsing and executing of infix notation is via conversion to postfix one.

Some languages (like `LISP`

) also use **prefix** notation which gives similar advantages.

Let us see few examples. Operation on two values is simply written after them:

```
2 4 * multiply 2 by 4
9 3 / divide 9 by 3
8 3 + sum 8 and 3
```

More complex expression:

```
5 2 3 * + 5 + 2 * 3
5 2 + 3 * (5 + 2) * 3
```

You see, Polish notation does not need brackets (parentheses) since the order of operation is always determined.

Simple way to evaluate expression in RPN is by using stack and the following algorithm:

- loop through all tokens of the expression;
- if the next token is a value, it is pushed onto stack;
- if it is operation, then a pair of values are popped from stack, operation is done on them and result is pushed back;
- after the whole expression is processed, stack contains a single value which is the result of evaluation.

It is also easy to extend these rules for using unary operations - for them only one value should be popped from the stack instead of two. So for example formula for root of quadratic equation:

```
(sqrt(b * b - 4 * a * c) - b) / (2 * a)
```

Could be written as:

```
b b * 4 a * c * - sqrt b - 2 a * /
```

You are given a long expression in postfix notation, which contains integer values and operations:

`add`

and`sub`

for`+`

and`-`

;`mul`

,`div`

and`mod`

for`*`

,`/`

and remainder;`sqrt`

for taking square root.

You are to calculate the result.

**Input data** contains the expression, which may consist of few hundreds tokens.

**Answer** should contain single integer value - the result.

Example:

```
input data:
70 11 mul 5 div 219 add 28 26 6 sub 6 sub div mul 448 7 mul sqrt add
answer:
802
```

You need to login to get test data and submit solution.