HP calculators, slide rules, and Forth all have something in common: reverse polish notation or RPN. Admittedly, slide rules don’t really have RPN, but you work problems on them the same way you do with an RPN calculator. For whatever reason, RPN didn’t really succeed in the general marketplace, and you might wonder why it was ever a thing. The biggest reason is that RPN is very easy to implement compared to working through proper algebraic, or infix, notation. In addition, in the early years of computers and calculators, you didn’t have much to work with, and people were used to using slide rules, so having something that didn’t take a lot of code that matched how users worked anyway was a win-win.
What is RPN?
If you haven’t encountered RPN before, it is an easy way to express math without ambiguity. For example, what’s 5 + 3 * 6? It’s 23 and not 48. By order of operations you know that you have to multiply before you add, even if you wrote down the multiplication second. You have to read through the whole equation before you can get started with math, and if you want to force the other result, you’ll need parentheses.
With RPN, there is no ambiguity depending on secret rules or parentheses, nor is there any reason to remember things unnecessarily. For instance, to calculate our example you have to read all the way through once to figure out that you have to multiply first, then you need to remember that is pending and add the 5. With RPN, you go left to right, and every time you see an operator, you act on it and move on. With RPN, you would write 3 6 * 5 +.
While HP calculators were the most common place to encounter RPN, it wasn’t the only place. Frieden calculators had it, too. Some early computers and calculators supported it but didn’t name it. Some Soviet-era calculators used it, too, including the famous Elektronika B3-34, which was featured in a science fiction story in a Soviet magazine aimed at young people in 1985. The story set problems that had to be worked on the calculator.
How to Do Algebraic
It is illustrative to see how complex it is to do algebraic expressions the “normal” way. The usual method is to use two stacks and a precedence table. The steps are:
1. Grab a token
2. If the token is a number, push it on the value stack.
3. If the token is an operator, check to see if it is lower in precedence than the top of the operator stack (e.g., this is a plus sign, and the top of the stack is for multiplication). If so, do the indicated operation from the top of the stack, update the value stack, and then repeat this step.
4. Once the current operator is higher in precedence than the top of the operator stack, push it on the operator stack.
5. Repeat all steps until you are done, and then work through whatever is left on the stack.
Usually, you have a low precedence start marker and a high precedence end marker that are fake tokens. Open parenthesis is also high precedence. After that, you have the operators in their usual order. So consider (5+2) + 6*3. If you add the start and end markers (I’ll use []), you get [(5+2)+6*3].
After processing the first plus sign, the operator stack will contain: [(+, and the value stack will have 5 (and, soon, 5 2). The close parenthesis will cause 5+2 to calculate and remove the opening match. So then the value stack will have 7, and the operator stack will be empty.
When you read the end marker, the value stack will be 7 6 3, and the operator stack will be [+ *. Since the end marker is higher than everything else, step 3 will cause it first to compute 6*3, leaving the stacks to contain 7 18 and [+. Another pass through step 3 leaves 25 and [ which matches the ], and the operation is complete.
While this isn’t that hard, it does take two stacks and a table. The stacks can be arbitrarily long, although in practice, that isn’t necessary. But it still seems like a lot of work.
Python RPN
Processing RPN, on the other hand, is easy. If you see a number, push it on the value stack. If you see an operator, pop off enough stuff from the stack, do the operation, and put the result back on the stack. In Python, this is very simple (see the entire code on this gist):
# parse an RPN string and execute it
def parse(self,s):
tokens=s.split()
for token in tokens:
try:
num=float(token)
rpn.push(num)
except ValueError:
if token=="x" or token=="X": # exchange top of stack
exchange()
elif token=="?": # dump stack
self.dump()
elif token=="+":
rpn.add()
elif token=='-':
rpn.sub()
elif token=="*":
rpn.mul()
elif token=="/":
rpn.div()
elif token[0]=="!":
self.vars[token[1:]]=self.peek() # store tos in var
elif token[0]=="@":
self.push(self.vars[token[1:]]) # push var to tos
else:
raise Exception("Unknown operator or number:" + token)
This handles the four basic math functions and a few special operators to exchange the two top stack elements or display the stack. It can also store named variables (!somevar) and use them again later (@somevar). Prefer C? There is a simple version in the gist, also.
Why Not?
If you need to represent math in a program, you might consider RPN. It is fast to write and easy on resources. Of course, you can just as easily make the infix algorithm spit out RPN code instead of doing the work itself, but there isn’t much benefit to that unless you are writing a compiler. Going the other way is possible, too, but a little harder.
Then again, if you don’t mind having a lot more power and you are using Python, you might think about using eval() for infix notation. However, since it can execute anything Python, that’s not the right answer for all programs, especially not those that process user input. Not to mention, that’s notoriously hard to do in compiled languages like C.
Some pretty beefy computer/calculators used RPN. Or, you can homebrew one.
In Praise of RPN (with Python or C)
Source: Manila Flash Report
0 Comments