Problem Solving: Reverse Polish Notation
Reverse Polish notation (otherwise known as post-fix, RPN for short) is a way of representing mathematical equations. The notation is used because the format that the equation is in is easier for machines to interpret rather than the notation we are used to, infix notation, where the operator is in between the numbers. The equation can be complex or simple. RPN doesnt require brackets as the equations are layed out in such a format that it isn't required for machines to understand.
The name RPN is named after Jan Łukasiewicz, a Polish logician who invented Polish notation (prefix notation) some time in the 1920s.
Reverse Polish Notation[edit | edit source]
Reverse polish notation should be ordered like this:
<FirstNumber> <SecondNumber> <Operation>
Rather than the normal convention(infix) of:
<FirstNumber> <Operation> <SecondNumber>
Examples[edit | edit source]
Examples of equivalent equations[edit | edit source]
| PostFix | Infix | Answer |
|---|---|---|
| 3 4 + | 3 + 4 | 7 |
| 3 5 6 + * | (5 + 6) * 3 | 33 |
| 2 4 / 5 6 - * | (2/4)*(5-6) | -0.5 |
| 2 3 ↑ | 2³ | 8 |
Implementation as a Stack[edit | edit source]
YouTube Video Example[edit | edit source]
A video example can be seen here from Computerphile on Youtube: https://www.youtube.com/watch?v=7ha78yWRDlE [1]
Practice Questions[edit | edit source]
|
Exercise: Infix to RPN Conversion Convert x + y into RPN. Answer: x y + Convert (x + y)*z into RPN. Answer: x y + z * Convert 3 / (5 + y * x) into RPN. Answer: 3 5 y x * + / |
|
Exercise: RPN to Infix Conversion Convert x y * into infix. Answer: x * y Convert 5 y + z x 3 - * / into infix. Answer: (5 + y) / (z * (x - 3)) |
References[edit | edit source]
- ↑ Video link to Computerphile a Youtube channel: https://www.youtube.com/channel/UC9-y-6csu5WGm29I7JiwpnA