Problem F
RPN Calculator

Your goal is to write a postfix (“Reverse Polish Notation”) calculator. Unlike the probably more familiar “infix” notation, in postfix notation the numbers are given first, then the desired operation. The following example is from Wikipedia. The infix notation

can be written as

It can be evaluated by what Wikipedia calls the “left to right” algorithm as follows:

15 7 1 1 + - / 3 * 2 1 1 + + - =
15 7     2 - / 3 * 2 1 1 + + - =
15         5 / 3 * 2 1 1 + + - =
             3 3 * 2 1 1 + + - =
                 9 2 1 1 + + - =
                 9 2     2 + - =
                 9         4 - =
                             5

Your program will read and process lines of input one at a time, until it reads quit on a line by itself. Each line of input will either be an integer, or a string representing an operation. If the input is a number, your program should save it on a stack. If the input is an arithmetic operation, your program should remove the two most recently saved numbers, and replace them with the result of the operation. If before the operation, the most recently added number (i.e. the top of the stack) is $b$, and the second most recently added number is $a$, you should replace them with

The non-arithmetic operations should be implemented as follows:

Input

Each line of input will either be an integer, or a string $+, -, *, /, \verb|^|$, dup, pop, print, quit, or swap. You may assume that there will always be sufficient arguments for each operation (i.e. there is no “stack underflow”), and that no division by zero is attempted.

Output

The output should be the output from the print operations in the input (if any).

15
7
1
1
+
-
/
3
*
2
1
1
+
+
-
print
quit

5

17
3
2
*
print
dup
dup
pop
+
3
/
print
swap
-
13
+
2
^
print
quit

6
4
0

2
128
^
3
/
-2
*
print
quit

-226854911280625642308916404954512140970