RPN: Postfix Notation

Published 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¹ 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.

I love hearing from readers so please feel free to reach out.

Reply via email • Subscribe via RSS or email

Last modified July 9, 2024  #math