Reverse Polish notation

This article is a stub. Help us out by expanding it.

Reverse Polish Notation (RPN) is a notation to enter expressions in which the operators follow their operands. For example, the expression will be entered in RPN as "1 2 +".

Evaluation, or What RPN means

The concept of a stack is important in evaluating RPN. For example, the expression "1 2 + 3 - 8 9 * 7 2 - 5 4 + + + +" is evaluated as follows:

• You see the number 1 and push it into the stack. The stack is now (from bottom to top): 1.
• See 2 and push it into stack. The stack is now: 1 2.
• See +. You add the top 2 numbers in the stack, 1 and 2. Note: the order matters. In this case it is 1+2=3, and we push 3 into the stack. The stack is now: 3.
• See 3. Push 3 into the stack. We have in the stack 3 3.
• See -. 3-3=0, pop out 3 and 3 and push 0 into stack. The stack is now: 0.
• See 8. Push 8 in: 0 8
• 9: push 9 in: 0 8 9
• \(*\): pop out 8 and 9, multiply, and push 27 in.
• 7: push 7 in. 0 27 7
• 2: push 2 in. 0 27 7 2.
• -: subtract, pop the original numbers and push in the result. 0 27 5
• 5 4 + --- at the end of doing those we have 0 27 5 9.
• +: 0 27 14
• +: 0 41
• +: 41.

The only number left in the stack is our answer, 41.

Importance

RPN is important because with RPN you do not have to use any parenthesis, so experienced people typing RPN on a calculator may be faster than typing in the "normal" expression; speed is important on contests like TMSCA in Texas.

~Johnxyz1