Return to Blog

Building a command line RPN calculator

By John Lekberg on May 22, 2020.


This week's post is about building a command line reverse Polish notation (RPN) calculator. You will learn:

Reverse Polish notation means operators follow their operands. E.g.

(3 + 4) * 5

would be written as

3 4 + 5 *

Script source code

rpncalc

#!/usr/bin/env python3

import decimal
import re

from decimal import Decimal as D


class RPNCalc:
    """A reverse polish notation (RPN) calculator.

    Manages a stack of numbers.
    Numbers are decimal.Decimal objects.

    Supports the following operations:

    | op   | input     | output |
    |------|-----------|--------|
    | +    | x y +     | x+y    |
    | -    | x y -     | x-y    |
    | *    | x y *     | x*y    |
    | /    | x y /     | x/y    |
    | **   | x y **    | x**y   |
    | drop | x drop    |        |
    | swap | x y swap  | y x    |
    | dup  | x dup     | x x    |
    | over | x y over  | x y x  |
    | rot  | x y z rot | y z x  |
    | nand | x y nand  | !(x&y) |
    | <=   | x y <=    | (x<=y) |

    """

    def __init__(self):
        """Initialize the stack and supported operations."""

        self._stack = []

        def op(arity, f):
            """Turn a function like (lambda x, y: x + y)
            into an operation that pops and pushes self._stack.
            """

            def stack_f():
                if len(self._stack) < arity:
                    raise IndexError(
                        "Stack too small for operation"
                    )
                args = [
                    self._stack.pop() for _ in range(arity)
                ]
                results = f(*reversed(args))
                self._stack.extend(results)

            return stack_f

        self._operations = {
            # Arithmetic
            "+": op(2, lambda x, y: [x + y]),
            "-": op(2, lambda x, y: [x - y]),
            "*": op(2, lambda x, y: [x * y]),
            "/": op(2, lambda x, y: [x / y]),
            "**": op(2, lambda x, y: [x ** y]),
            # Stack Manipulation
            "drop": op(1, lambda x: []),
            "swap": op(2, lambda x, y: [y, x]),
            "dup": op(1, lambda x: [x, x]),
            "over": op(2, lambda x, y: [x, y, x]),
            "rot": op(3, lambda x, y, z: [y, z, x]),
            # Boolean Logic
            "nand": op(2, lambda x, y: [D(not (x and y))]),
            # Inequality
            "<=": op(2, lambda x, y: [D(x <= y)]),
        }

    @property
    def stack(self):
        """Return a read-only version of the current
        stack."""
        return tuple(self._stack)

    def execute(self, command):
        """Execute an RPN command.

        Tokens are split on whitespace.
        """
        for token in command.split():
            try:
                token = D(token)
                self._stack.append(token)
            except decimal.InvalidOperation:
                if token in self._operations:
                    self._operations[token]()
                else:
                    raise ValueError(
                        f"{token!r} not recognized as operation or number."
                    )


class RPNInterpreter:
    """Adds support for comments and macros on top of an
    RPNCalc.

    Comments are stripped from "#" to the end of the line.

    Macro statements look like

    macro NAME EXPANSION

    E.g.

    macro sqrt 0.5 **

    SHOW statement shows the stack.

    Also lower-cases the input, so "drop" can be written as
    "DROP" or "Drop", etc.
    """

    def __init__(self):
        """Initialize the underlying RPNCalc and the macro
        table."""
        self._calculator = RPNCalc()
        self._macros = {}

    def execute(self, line):
        """Execute a line by removing comments, then

        - Processing macro-statements, OR
        - Processing show-statements, OR
        - Expanding all macros (exhaustively) and executing
          the resulting line in the underlying RPNCalc.
          Then return the top of the stack, or None if the
          stack is empty.
        """
        line = line.lower()
        line = re.sub(r"#.*$", "", line)
        match_macro = re.match(
            r"macro\s+(?P<name>\S+)\s*(?P<expansion>.*)$",
            line,
        )
        if match_macro:
            self._macros[match_macro["name"]] = match_macro[
                "expansion"
            ]
        elif line.strip() == "show":
            return [
                float(x) for x in self._calculator.stack
            ]
        else:
            maybe_macro = lambda x: self._macros.get(x, x)
            exhausted = False
            while not exhausted:
                old_line = line
                line = re.sub(
                    "\S+", lambda m: maybe_macro(m[0]), line
                )
                exhausted = old_line == line
            self._calculator.execute(line)
            try:
                return self._calculator.stack[-1]
            except IndexError:
                return


if __name__ == "__main__":
    import argparse

    parser = argparse.ArgumentParser()
    parser.add_argument(
        "scripts",
        nargs="*",
        help="execute these files before the REPL",
    )
    args = parser.parse_args()

    interpreter = RPNInterpreter()

    for script in args.scripts:
        with open(script) as file:
            for line in file:
                try:
                    result = interpreter.execute(line)
                except Exception as e:
                    print(f"ERROR in {script}, {e.args[0]}")

    import readline

    while True:
        try:
            line = input("    ")
        except EOFError:
            break
        try:
            result = interpreter.execute(line)
        except Exception as e:
            print("ERROR", e.args[0])
        else:
            if result is not None:
                print(result)

    print()
$ ./rpncalc --help
usage: rpncalc [-h] [scripts [scripts ...]]

positional arguments:
  scripts     execute these files before the REPL

optional arguments:
  -h, --help  show this help message and exit

Using my calculator

$ ./rpncalc

I can use rpncalc to calculate the square root of 2:

2 .5 **
1.414213562373095048801688724

I can also calculate the distance from the point (3, 4) to the point (0, 0):

3 2 ** 4 2 ** + .5 **
5.000000000000000000000000000

I think it's hard to read 2 ** for squaring and .5 ** for square roots, so I create macros for squaring and square rooting:

macro  ^2  2 **
macro  sqrt  .5 **
3 ^2 4 ^2 + sqrt
5.000000000000000000000000000

I think this would be easier to read if I could group some of the terms, so I like to have an "empty" macro that I just use for readability:

3 ^2 , 4 ^2 , + sqrt
5.000000000000000000000000000

Even though the macro system is simple, because this calculator uses a concatenative programming language I can create more advanced macros, such as unit conversions.

If I know that a 1 inch is 2.54 centimeters, then how many centimeters are in 6 feet 4 inches?

macro  cm
macro  in  2.54 * cm
macro  ft  12 * in
macro  ->cm  1 cm /
6 ft 4 in + ->cm
193.04

Building a "standard library" for my calculator

I have a few macros that I like to consistently use. I have incorporated these into a standard library, a file named stdlib.

stdlib

# rpncalc Standard Library

macro ,

# Boolean.
macro  not  dup nand
macro  and  nand not
macro  or   not swap not nand
macro  nor  or not

# Equality and inequality.
macro  >   <= not
macro  <   swap >
macro  >=  swap <=
macro  =   over over <= rot rot >= and
macro  !=  = not

# Multiplexing.
# a b s mux => like JavaScript "s ? b : a".
macro  mux  0 != rot over not * rot rot * +

What are these macros?

Here's an example of using stdlib to explore the golden ratio, φ:

$ ./rpncalc stdlib
macro  abs  dup 0 > -1 1 rot mux *
macro  ~  - abs 1e-8 <
0 0 ~
1
0.0000000000001 0 ~
1
macro  sqrt  .5 **
macro  phi  5 sqrt 1 + 2 /
phi
1.618033988749894848204586834
macro  ^2  2 **
phi ^2
2.618033988749894848204586833
phi ^2 , phi 1 + , ~
1

Building a library for calculating body mass index (BMI)

Body mass index (BMI) is a measurement used to broadly classify a person's weight (given their height) into categories like "underweight", "normal weight", and "overweight".

I created a library, bmi, that allows me to make BMI calculations:

bmi

# rpncalc Body Mass Index (BMI) Library
#
# You MUST also load rpncalc stdlib.

# Units - Weight

macro  kg
macro  lb  0.453592 * kg
macro  st  6.35 * kg

macro  ->kg  1 kg /

# Units - Height

macro  m
macro  cm  100 / m
macro  ft  0.3048 * m
macro  in  12 / ft

macro  ->m  1 m /

# BMI Formula
#
# height weight bmi
#
# E.g.
#
# 5 ft 7 in + , 175 lb , bmi

macro  bmi  ->kg swap ->m , 2 ** /

# BMI Classifications
#
# bmi *
#
# E.g.
#
# 33.3 obese

macro  _range  rot dup rot < rot rot <= and

macro  underweight    18.5 <
macro  normal-weight  18.5 25 _range
macro  overweight     25   30 _range
macro  obese          30 >=

# Classify BMI using a number:
# 1 - underweight
# 2 - normal-weight
# 3 - overweight
# 4 - obese
#
# E.g.
#
# 22.5 classify-bmi

macro  classify-bmi  _c1
macro  _c1  dup underweight   swap _c2 swap 1 swap mux
macro  _c2  dup normal-weight swap _c3 swap 2 swap mux
macro  _c3  dup overweight    swap _c4 swap 3 swap mux
macro  _c4  dup obese         swap _c5 swap 4 swap mux
macro  _c5  drop -1

I'll use this to look at the BMI of several people:

$ ./rpncalc stdlib bmi
macro  bmi_1  5 ft 8 in + , 250 lb , bmi
bmi_1
38.01194886126796475046237290
    classify-bmi
4
bmi_1 obese
1
macro  bmi_2  161 cm , 14 st 5 lb + , bmi
    bmi_2
35.17146715018710697889741908
classify-bmi
4
bmi_2 underweight
0
bmi_2 obese
1
macro bmi_3  6 ft 3 in + , 156 lb , bmi
bmi_3
19.49844710356087378841424350
classify-bmi
2
bmi_3 underweight
0
bmi_3 overweight
0
bmi_3 normal-weight
1

How the script works

The RPNCalc class manages the stack, and the RPNInterpreter class manages the macros.

I use Decimal objects for numbers because they have more accuracy than floating point numbers.

I represent the stack as a list and use list methods to push and pop from the stack.

The stack manipulation operations, like dup, are taken from the Forth programming language.

I tokenize strings using str.split, which does a simple split on whitespace. If I wanted to allow tokens containing whitespace, I might use the shlex module.

Macros are also implemented using simple text substitution. Because reverse Polish notation (RPN) lends itself to being a concatenative language, even simple text replacement macros can be used to construct advanced functions, like classifying BMI.

I use the built-in function input to get user input. I also import the readline module, to allow for more elaborate line editing and history features. (See the readline module for details.)

In conclusion...

In this week's post you learned how to create a reverse Polish notation (RPN) calculator that supports macros. You also learned how to construct more advanced macros that converted between different units of measurement and calculated medical measurements, like body mass index (BMI).

My challenge to you:

Create macros for units of space and time (e.g. meters and seconds) and use them to convert speed values (e.g. convert 150 miles/hour to meters/second).

If you enjoyed this week's post, share it with your friends and stay tuned for next week's post. See you then!