What does Reverse Polish Notation (RPN) mean?
Reverse Polish notation (RPN) is a method for conveying mathematical expressions without the use of separators such as brackets and parentheses. In this notation, the operators follow their operands, hence removing the need for brackets to define evaluation priority. The operation is read from left to right but execution is done every time an operator is reached, and always using the last two numbers as the operands. This notation is suited for computers and calculators since there are fewer characters to track and fewer operations to execute.
Reverse Polish notation is also known as postfix notation.
Techopedia explains Reverse Polish Notation (RPN)
Reverse Polish notation was proposed by Burks, Warren and Wright in 1954 and so named because it was simply the reverse of Polish notation (prefix notation), invented by the Polish logician Jan Lukasiewicz, which puts the operator before the operands. In the 1960s, it was then independently reinvented by E.W. Dijkstra and F.L. Bauer for reducing the number of times computer memory is accessed and increasing performance. It made use of the computer’s stack to store its operands before executing the operator.
RPN leads to faster calculations for a couple of reasons. One is that there is less information to store. Therefore, instead of needing to store nine characters for the expression ((5 – 3) * 2), computers using RPN only need to store five characters with the expression 5 3 – 2 *. And because there are fewer characters to process, execution becomes faster.
So in a computer using RPN, the evaluation of the expression 5 1 – 3 * is as follows:
- Push 5 into the stack. This is the first value.
- Push 1 into the stack. This is the second value and is on the position above the 5.
- Apply the subtraction operation by taking two operands from the stack (1 and 5). The top value (1) is subtracted from the value below it (5), and the result (4) is stored back to the stack. 4 is now the only value in the stack and is in the bottom.
- Push 3 into the stack. This value is in the position above 4 in the stack.
- Apply the multiplication operation by taking the last two numbers off the stack and multiplying them. The result is then placed back into the stack. After this operation, the stack now only contains the number 12.