Home Archives Search About

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-50g1 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.


  1. 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  


← Newer post  •  Older post →