# RPN: Postfix Notation

August 6, 2018

“Please Excuse My Dear Aunt Sally”

Learning order of operations in grade school yielded the acronym for “Parentheses, Exponents, Multiplication, Division, Addition, and Subtraction”: PEMDAS. The idea is to provide a mnemonic to aid in getting the order of operations correct. Alternatively, if you’re like me, you’ll liberally apply parentheses. ¯\_(ツ)_/¯

At university, a friend introduced me to Reverse Polish Notation (RPN). Using RPN removes the concept of order of operations & subsequently the need for parentheses. Here’s the rundown:

## The Basics

Expressions consist of operands (digits e.g. `2`

) & operators (symbols e.g. `+`

). The “typical” notation, as in: `1 + 2 = 3`

is referred to as Infix notation, where operators go between operands.

### Prefix

Polish Notation (AKA Prefix Notation) alters this by having operators precede operands like so: `+ 1 2`

. An alternative way of thinking about this notation is each operator is a function that takes a fixed number of arguments (operands). Using this thought process, we could write the expression as `+(1, 2)`

. With a fixed number of operands for each operator, parentheses become optional.

### Reverse!

By reversing Polish Notation we get our RPN (AKA Postfix Notation) with the operators following operands like so: `1 2 +`

. RPN uses the simple stack paradigm by pushing operands onto the stack and popping them off when an operator is encountered.

Knowing this, it’s not difficult to write a basic function to evaluate an RPN expression. Here’s one in JavaScript:

```
function rpn (input) {
let ops = input.split(/\s+/),
stack = [],
op
// Remove values one at a time from left to right
while (op = ops.shift()) {
// Check if numeric (operand)
if (op == +op) {
stack.push(op)
// If not, it must be an operator
} else {
let num2 = stack.pop(),
num1 = stack.pop(),
result = eval(num1 + op + num2)
stack.push(result)
}
}
return stack.pop()
}
```

Which you could use like so:

```
const expr = '5 3 -'
rpn(expr) // 2
```

## Using RPN

Hewlett-Packard (HP) is historically rooted in RPN: the HP-35, the first *pocket* scientific calculator, exclusively used RPN. Currently, you can purchase the HP-50g — a graphing calculator — that has the option to use RPN or Algebraic mode. I’ve been personally using the HP-50g^{1} for the past 2 ½ years and it’s been a solid experience. Programming is straightforward & there are plenty of libraries available for download.

On my Android device, RealCalc is my go-to. Similar to the HP-50g, RealCalc also supports Algebraic mode.

In a CLI, `dc`

is great option. Similar to `bc`

, `dc`

supports RPN — fully allowing viewing & manipulation of the stack.

Before the HP I used a TI-83 Plus. For me personally, I feel more productive with the HP vs. the TI. As with most things, however, YMMV.↩

Posted on August 6, 2018 #math