RPN stands for Reversed Polish Notation. It is a method of calculation where the operations are placed after the terms on which to be computed. (RPN is used by Hewlett-Packard!) As the input string is read, all integers are pushed on the stack. As soon as an operation is reached, the top two integers are popped off the stack and the operation is performed on those numbers. Then the result is pushed on the stack and we begin reading the input string again.
EXAMPLE:
Given the input string: 22 32 2 4 * / 14 + -
The rpn calculator would read the integers in order, pushing each on the
stack. When the calc reaches the '*', the stack looks like:
| |
| |
<SP> +----+
| 4 |
+----+
| 2 |
+----+
| 32 |
+----+
| 22 |
+----+
| |
The calculator now pops the top 2 numbers off the stack (2 and 4) and applies the operation ( * ). The result ( 8 ) is then pushed on the stack.
| |
| |
<SP> +----+
| 8 |
+----+
| 32 |
+----+
| 22 |
+----+
| |
The next character that the calculator gets is '/'. Because this is an operation, the calculator pops the top 2 numbers from the stack, operates, then pushes the result back on the stack. 32 and 8 are replaced by 4:
| |
| |
<SP> +----+
| 4 |
+----+
| 22 |
+----+
| |
The calculator now continues reading and encounters a 14. This gets pushed on the stack. The next item is an operation, '+'. At this point, the stack is:
| |
| |
<SP> +----+
| 14 |
+----+
| 4 |
+----+
| 22 |
+----+
| |
After performing the '+' the stack becomes:
| |
| |
<SP> +----+
| 18 |
+----+
| 22 |
+----+
| |
The next item is an operation, '-', so the stack becomes:
| |
| |
<SP> +----+
| 4 |
+----+
| |
Finally, the calculator encounters a '\n' indicating that the computation is done, so the calculator outputs its answer, which will always be the top element of the stack:
<POP> "4. Thank you, come again"