Programming Challenge: Reverse Polish Notation Calculator

JavaScript, ES6:
(...I might be overusing the destructuring operator just a tiny bit)

// just used for printing each evaluation step to console, not necessary for the solution
const withLogging = func => (...args) => {
  console.log(...args.slice(0, 2));
  return func(...args);
};

const operators = {
  '+': (x, y) => x + y,
  '-': (x, y) => x - y,
  '/': (x, y) => x / y,
  x: (x, y) => x * y,
  '*': (x, y) => x * y
};

const rpnReducer = (values, item) =>
  operators[item]
    ? [...values.slice(0, -2), operators[item](...values.slice(-2))]
    : [...values, +item];

// pass `true` as second argument to see all the evaluation steps :D
const rpnEvaluate = (rpnExpression, logSteps = false) =>
  rpnExpression
    .split(' ')
    .reduce(logSteps ? withLogging(rpnReducer) : rpnReducer, [])[0];

rpnEvaluate('15 7 1 1 + - / 3 * 2 1 1 + + -', true);

Pop open your browser dev tools and paste the whole thing in to try it out. 😎

As I find these sorts of challenges most interesting when trying to come up with a solution that does not take the obvious approach, here is my first attempt (in Python). Amongst other features:

• It flexibly chooses between ints, floats, and complex numbers (if entered as, eg, "2 3.2j +").
• It does not use a stack (note, because of how python lists work, this has horrible time complexity).
• It should pass any test with valid inputs, but
• with invalid inputs, it allows arbitrary code execution (for example, input of "3 4 +bool(open('amaliciouslyplacedfile','w').write('thisisbad'))+")

def rpneval(s):
    s=s.split(' ')
    i=0
    while i<len(s):
        try:
            complex(s[i])
            i+=1
        except:
            s[i-2]=eval(('{}'*3).format(s[i-2],s[i],s[i-1]))
            del(s[i-1]); del(s[i-1])
            i-=1
    return s[-1]

With apologies for giving two completely different answers, here is another version, with an entirely different approach. Here, I parse the token list backward, using recursive function calls. Rather than returning a number, I return a list.

• For valid RPN strings, defined as strings where, processed normally, every operator acts on two numbers, npr returns the correct answer. However, it only does as many operations as it needs to do in order to find that answer. Any operators that weren't used in the final answer aren't applied (eg, "1 1 + 2 3 *" will only apply one multiplication operation).
• For incomplete RPN strings, defined as strings where, processed normally, every operator does not have two numbers to operate on, npr does as many operations as necessary to find, if possible, a number as the last item (like an RPN calculator that has ignored any errors and cleared the stack whenever an error took place), while returning a reduced, incomplete RPN token list. The reduced list contains operations and numbers that are equivalent, however, to the input string.
• Why is this interesting? Because substrings of valid RPN strings are, in general, either valid or incomplete RPN strings. Thus, for a string A, if it is split into a list of arbitrary substrings S_i, then npr(A) = npr( concatenation of every npr(S_i)). So, for example:

npr('15 7 1 1 + - / 3 * 2 1 1 + + -') == npr(npr('15 7 1 1 + -') + npr('/ 3 * 2 1 1 + + -'))

Of course, the actual motivation of this was just to do RPN starting from the end of the string.

applyop =  {'+': lambda x, y: x + y, '-': lambda x, y: x - y, 
            '*': lambda x, y: x * y, '/': lambda x, y: x / y}
isop = lambda x: x in applyop.keys()
def npr(l):
    if isinstance(l, str):
        l = l.split(' ')
    if not isop(l[-1]):
        return l
    if len(l) < 2:
        return l
    if isop(l[-2]):
        l = npr(l[:-1])+l[-1:]
    if len(l) < 3:
        return l
    if isop(l[-3]):
        l = npr(l[:-2])+l[-2:]
    if not (isop(l[-2]) or isop(l[-3])):
        return l[:-3] + [applyop[l[-1]](float(l[-3]),float(l[-2]))]
    return l

When it comes to these challenges, I try to push myself, by reaching for something I'm not entirely familiar with, or by making it as performant as I can, or codegolf to get the least bytes, etc.

Unfortunately, almost all of those answered by an RPN on D's main website, and is a fantastic piece of code.

I'm not more creative than that blend of mixins, static loops, and Ds robust IO.

So, the only real choice I have left... Is completeness.

Parsing an RPN is braindead simple - split by whitespace, evaluate left to right, if not an operator, push ot the stack. By being clever you can do other things, and increase your performance... But I'm not interested in that this time around.

So, the goal is:

• A stack for storing numbers and results
• + an addition operator
• - a minus operator
• * a multiplication operator
• / a divide operator
• i/ integer division operator
• √ a square root operator
• ^ an exponent operator
• % a modulus operator
• ][ a clamp operator
• .. a rounding operator

First up!

Our braindead parser:

local parser = function(data)
  -- File handling can happen elsewhere. We just want the data.
  assert(type(data) == "string")
  -- Here it comes, the whole thing:
  return string.gmatch(example, "%S+")
end

Here, we use Lua's inbuilt regex to split apart a string based on any whitespace.

There are some caveats.

• Lua can only return a few thousand values. It's note infinitely scaleable.
• This just gives us string token, without attempting to do any types

We'll leave the parser for now, but I do plan to come back to it.

Instead, let's build our operators, and assume we've worked out parser and made a stack (implemented as a simple table).

local add = function(stack)
  local a = table.remove(stack) or 0
  local b = table.remove(stack) or 0
  stack[#stack + 1] = a + b
end

By using Lua's ability to do comparisons wherever you feel like, we can add some data protection here.

table.remove is also a helpful little thing. It returns the last value in a table, removing it, or returns nil.

So, now we can whack out a few functions.

I'll gloss over most.

But! We do need to worry about our pesky little division operator.

Because, well, division by zero should return an infinite number, positive or negative. Lua, being little more than C in ways of the stdlib, doesn't know what the hell an infinite value is. And I don't really feel like adding a type, which is actually quite a pain in the butt.

Instead, let's opt for an older way computers used to handle division by zero, not with a crash error, or with an infinite value, or a NotANumber, but with a zero. Negative zero, to be more precise.

It's unusual, and users need to be aware of it, but it does have a history in the world of computer science.

local divide = function(stack)
  local a = table.remove(stack) or 0
  local b = table.remove(stack) or 0
  if b == 0 then
    stack[#stack + 1] = -0
  else
    stack[#stack + 1] = a / b
  end
end

And of course, implementing integer division is also nice and simple:

local divide_int = function(stack)
  divide(stack)
  stack[#stack + 1] = math.ceil(table.remove(stack))
end

The only other interesting operator will probably be clamp.

Clamping is something that often turns up in video programming. You take three numbers, sort them smallest to largest, and take the middle one and discard the rest.

It's actually quite useful, and interesting for us because it takes three arguments, instead of two, demonstrating flexibility.

local clamp = function(stack)
  local t = {table.remove(stack), table.remove(stack), table.remove(stack)}
  if #t == 3 then
    table.sort(t)
    stack[#stack + 1] = t[2]
  elseif #t == 2 then
    if t[1] > t[2] then
      stack[#stack + 1] = t[1]
    else
      stack[#stack + 1] = t[2]
    end
  else
    stack[#stack + 1] = t[1] or 0
  end
end

So... What was simple, when accounting for edge cases, looks nuts.

At it's core, when three args can be pulled off the stack, it sorts them and returns the middle.

However, if only two can, then it returns the larger of the two.

If one can, it returns that one.

Finally, if none can, then it returns zero.

Technically, clamp requires three and shouldn't be so flexible, but it's nice in a calculator if it doesn't explode every time you try and do something. Which also let's you come up with some stupid little tricks here and there.

Note: We probably need to define how our intended .. or rounding function works. We'll use math.ceil, so it rounds up.

Let's get back to the parser.

We basically need to do two things, turn strings that might be numbers into numbers, and link symbol representations with our functions.

First, numbers are easy.

local parser = function(data)
  -- File handling can happen elsewhere. We just want the data.
  assert(type(data) == "string")
  local t = {}
  for atom in string.gmatch(example, "%S+") do
    if tonumber(atom) then
      t[#t +1] = tonumber(atom)
    else
      -- TODO: Link in our functions.
    end
  end
end

And linking in our functions is dead simple too, as we have first class functions, and UTF-8 strings.

local parser = function(data)
  -- File handling can happen elsewhere. We just want the data.
  assert(type(data) == "string")
  local t = {}
  for atom in string.gmatch(example, "%S+") do
    if tonumber(atom) then
      t[#t + 1] = tonumber(atom)
    elseif atom == '+' then
      t[#t + 1] = add
    elseif atom == '-' then
      t[#t + 1] = minus
    elseif atom == '*' then
      t[#t + 1] = multiply
    elseif atom == '/' then
      t[#t + 1] = divide
    elseif atom == 'i/' then
      t[#t + 1] = divide_int
    elseif atom == '√' then
      t[#t + 1] = square_root
    elseif atom == '^' then
      t[#t + 1] = exponent
    elseif atom == '%' then
      t[#t + 1] = mod
    elseif atom == '][' then
      t[#t + 1] = clamp
    elseif atom == '..' then
      t[#t + 1] = round
    end
  end
  t = reverse(t)
  return t
end

Note: Technically, we could have used the symbol names when defining the functions. But the syntax gets a bit more cluttered.

So, we have all our functions that play with our stack, safely. Unless something erratic happens, the calculator won't crash. And if it does crash, you probably have worse things on your hands.

To make the calculator work, all we have left is an evalulator, and then cli bindings (which I won't go into).

The evaluator takes the parse tree, (array really... it's a stack), and goes through it.

local eval = function(tbl)
  local stack = {}
  while #tbl > 0 do
    local x = table.remove(tbl)
    -- Use the operator if it was
    if type(x) == "function" then
      x(stack)
    -- Ignore x if it was a nil for some weird reason
    elseif x then
      stack[#stack + 1] = x
    end
  end
  if #stack > 0 then
    print(stack[#stack])
  end
end

We end our evaluator with a little print statement of the top of the stack, so that the calculator feels useful.

I've glossed over a few things, and not really expanded it, because it tends to be simple, but you can find my complete implementation here.

Some test cases:

import unittest

from rpn import evaluate


class RpnTests(unittest.TestCase):
    def test_rpn(self):
        test_cases = [
            ('1', 1),
            ('2 2 +', 4),
            ('3 3 *', 9),
            ('5 4 -', 1),
            ('6 3 /', 2),
            ('2 2 + 2 *', 8),
            ('3 3 3 * +', 12),
            # https://en.wikipedia.org/wiki/Reverse_Polish_notation#Example
            ('15 7 1 1 + - / 3 * 2 1 1 + + -', 5),
        ]
        for input, expected in test_cases:
            actual = evaluate(input)
            self.assertEquals(expected, actual, input)

And a simple implementation, elegant and devoid of any pretense of error checking:

operations = {
    '+': lambda x, y: x + y,
    '-': lambda x, y: x - y,
    '*': lambda x, y: x * y,
    '/': lambda x, y: x / y,
}

def evaluate(expression):
    stack = []

    for operand in expression.split(' '):
        try:
            operation = operations[operand]
            y, x = stack.pop(), stack.pop()
            value = operation(x, y)
        except KeyError:
            value = int(operand)

        stack.append(value)

    return value

Basic Racket with no fancy eval or macro nonsense or error handling!

#lang racket

(define operators `((,"+" . ,+)
                   (,"-" . ,-)
                   (,"*" . ,*)
                   (,"/" . ,/)))

;; String -> Number
(define (evaluate expression)
  (first
   (for/fold [(result null)]
             ([token (string-split expression)])
     (define operator (assoc token operators))
     (if operator
         (cons ((cdr operator) (second result) (first result))
               (drop result 2))
         (cons (string->number token) result)))))

(module+ test
  (require rackunit)
  (check-eq? (evaluate "1") 1)
  (check-eq? (evaluate "2 2 +") 4)
  (check-eq? (evaluate "3 3 *") 9)
  (check-eq? (evaluate "5 4 -") 1)
  (check-eq? (evaluate "6 3 /") 2)
  (check-eq? (evaluate "2 2 + 2 *") 8)
  (check-eq? (evaluate "3 3 3 * +") 12)
  ; https://en.wikipedia.org/wiki/Reverse_Polish_notation#Example
  (check-eq? (evaluate "15 7 1 1 + - / 3 * 2 1 1 + + -") 5)
  )

A C++17 version - with constexpr compile time support. Slightly hacky fixed size stack to allow compile time generation. Expects completely valid input.

#include <string_view>
#include <cstdio.h>

//from_chars isn't constexpr for standard reasons
constexpr void from_chars_local(const char *s, const char *t, int &x) {
	x = 0;
	while (s != t) {
		x = x * 10 + *s - '0';
		s++;
	}
}

constexpr int eval_rpn(const std::string_view &s) {
	int stack[128] = {};
	int sind = 0;

	std::string_view::size_type i = 0, j = 0;
	
	while (i != s.size()) {
		switch (s[i]) {
		case '+':
			stack[sind - 2] = stack[sind - 2] + stack[sind - 1]; sind -= 1;
			break;
		case '-':
			stack[sind - 2] = stack[sind - 2] - stack[sind - 1]; sind -= 1;
			break;
		case '*':
			stack[sind - 2] = stack[sind - 2] * stack[sind - 1]; sind -= 1;
			break;
		case '/':
			stack[sind - 2] = stack[sind - 2] / stack[sind - 1]; sind -= 1;
			break;
		case ' ':
			break; // can't i+=2 in constexpr
		default:
			j = s.find_first_of(' ', i);
			from_chars_local(&s[i], &s[j], stack[sind++]);
		}

		i = i>j ? i + 1 : j + 1;
	}

	return stack[0];
}

int main()
{
        static_assert(eval_rpn("15 7 1 1 + - / 3 * 2 1 1 + + -") == 5)
}

I've been looking for a job lately, so I've been trying to do more programming challenges to keep my skills sharpish. Thanks for posting these, they've been a great help!

Anyways, I went for Java this time. It accepts + - * / as operators, and expects tokens to be separated by spaces.
It always surprises me at the things you can't do in Java without some complicated setup, like reading in lines from the console or pushing / popping elements to/from an array.

import java.util.Scanner;
import java.util.Stack;
import java.util.EmptyStackException;
import java.util.Arrays;

public class RPNCalculator {
  public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    System.out.println("Enter RPN String. Valid operators are + - * /");
    String[] rpn = scan.nextLine().trim().split(" ");
    System.out.println("You entered: " + Arrays.toString(rpn));

    scan.close();

    Stack<Float> operatorStack = new Stack<Float>();
    int count = 0;

    for (String token : rpn ) {
      if(token.matches("[0-9\\.]+")) {
        operatorStack.push(new Float(token));
        count++;
      }
      else if (token.matches("[\\+\\-\\*\\/]")) {
        try {
          Float operand_2 = operatorStack.pop();
          Float operand_1 = operatorStack.pop();
          count -= 2;
          if(count < 0) {
            System.out.println("The RPN string is invalid. Please verify you have entered valid Reverse Polish Notation.");
            break;
          }
          count++;

          switch (token) {
            case "+": operatorStack.push(operand_1 + operand_2);
                      break;
            case "-": operatorStack.push(operand_1 - operand_2);
                      break;
            case "*": operatorStack.push(operand_1 * operand_2);
                      break;
            case "/": operatorStack.push(operand_1 / operand_2);
            default:  break;
          }
        }
        catch(EmptyStackException e) {
          System.out.println("The RPN string is invalid. Please verify you have entered valid Reverse Polish Notation.");
          System.exit(1);
        }
      }
    }
    try {
      Float result = operatorStack.pop();
      if (count == 1)
        System.out.println(result);
      else
        System.out.println("Please verify that you have entered a valid RPN string.");
    }
    catch(EmptyStackException e) {
      System.out.println("Please verify that you have entered a valid RPN string.");
    }
  }
}

import re
from typing import List, Union


operators = {
    "+": lambda x, y: x + y,
    "-": lambda x, y: x - y,
    "/": lambda x, y: x / y,
    "*": lambda x, y: x * y
}


def is_float(token: str) -> bool:
    try:
        float(token)
        return True
    except:
        return False


def tokenize(expr: str) -> List[str]:
    return re.findall(r"(\d(?:\.\d+)?|[+\-/*])", expr)


def cast_tokens(tokens: List[str]) -> List[Union[float, str]]:
    return [
        float(token) if is_float(token) else token
        for token in tokens
    ]

def calculate(expr: str) -> float:
    stack = []
    tokens = cast_tokens(tokenize(expr))

    for token in tokens:
        if isinstance(token, float):
            stack.append(token)
        else:
            x = stack.pop()
            y = stack.pop()
            result = operators[token](x, y)
            stack.append(result)

    if len(stack) > 1:
        raise ValueError("Invalid expression.")

    return stack[0]


def main():
    while True:
        expr = input("Enter a RPN expression: ")
        print("= {}".format(calculate(expr)))


if __name__ == "__main__":
    main()