Reverse Polish Notation

Problem #181

Tags: arithmetic classical practical data-structures

Who solved this?

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.

Processing of RPN

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

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 * /

Your Goal

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

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.