# Programming Challenge: Reverse Polish Notation Calculator

It's been nearly a week, so it's time for another programming challenge!

This time, let's create a calculator that accepts reverse Polish notation (RPN), also known as postfix notation.

For a bit of background, RPN is where you take your two operands in an expression and place the operator after them. For example, the expression `3 + 5` would be written as `3 5 +`. A more complicated expression like `(5 - 3) x 8` would be written as `5 3 - 8 x`, or `8 5 3 - x`.

All your program has to do is accept a valid RPN string and apply the operations in the correct order to produce the expected result.

1. jzimbel
(edited )
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 =...

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, []);

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

2. 
cge
(edited )
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:...

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]
``````
1. Emerald_Knight
"Does not use a stack" could be debatable if we want to consider the list of tokens a pre-loaded stack that you're operating on. But that's just being pedantic. Interesting solution! Disgusting...

"Does not use a stack" could be debatable if we want to consider the list of tokens a pre-loaded stack that you're operating on. But that's just being pedantic.

Interesting solution! Disgusting with your arbitrary code execution and exception-oriented functionality, but interesting!

3. cge
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....

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
``````
4. s4b3r6
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....

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
• - 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!

``````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
elseif #t == 2 then
if t > t then
stack[#stack + 1] = t
else
stack[#stack + 1] = t
end
else
stack[#stack + 1] = t 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
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.

5. spit-evil-olive-tips
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),...

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
``````
6. bhrgunatha
Basic Racket with no fancy eval or macro nonsense or error handling! #lang racket (define operators `((,"+" . ,+) (,"-" . ,-) (,"*" . ,*) (,"/" . ,/))) ;; String -> Number (define (evaluate...

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)
)
``````
7. cmh
(edited )
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>...

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 = {};
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;
}

int main()
{
static_assert(eval_rpn("15 7 1 1 + - / 3 * 2 1 1 + + -") == 5)
}
``````
8. Emerald_Knight
(edited )
Here's my own, once again in PHP: <?php class ReversePolishNotationCalculator { public function __construct() { // Empty. } private function validateExpression(\$expression) { \$tokens = explode('...

Here's my own, once again in PHP:

``````<?php
class ReversePolishNotationCalculator {
public function __construct() {
// Empty.
}

private function validateExpression(\$expression) {
\$tokens = explode(' ', \$expression);

\$numbers = 0;
\$operators = 0;
foreach(\$tokens as \$token) {
if(preg_match('/^\d+(\.\d+)?\$/', \$token)) {
\$numbers++;
} else if(preg_match('/^[\+\-\/x]\$/', \$token)) {
\$operators++;
} else {
return false;
}

if(\$operators >= \$numbers) {
return false;
}
}

return \$operators == (\$numbers - 1);
}

private function evaluate(&\$tokens) {
\$operator = array_shift(\$tokens);
if(preg_match('/^\d+(\.\d+)?\$/', \$operator)) {
return doubleval(\$operator);
}

\$left_result = \$this->evaluate(\$tokens);
\$right_result = \$this->evaluate(\$tokens);

switch(\$operator) {
case '+':
return \$right_result + \$left_result;
case '-':
return \$right_result - \$left_result;
case '/':
return \$right_result / \$left_result;
case 'x':
return \$right_result * \$left_result;
default:
throw new Exception('Operator "' . \$operator . '" not recognized.');
}
}

public function calculate(\$expression) {
assert(\$this->validateExpression(\$expression), new Exception('Invalid RPN expression.'));

\$tokens = array_reverse(explode(' ', \$expression));
return \$this->evaluate(\$tokens);
}
}

\$calculator = new ReversePolishNotationCalculator();

\$tests = array(
'5 3 +' => 8,
'5 3 -' => 2,
'15 3 /' => 5,
'15 3 x' => 45,
'5 3 - 8 x' => 16,
'8 5 3 - x' => 16,
'1 1 + 2 + 3 1 1 + 7 - 15 / x -' => 5
);

foreach(\$tests as \$expression=>\$expected) {
\$actual = \$calculator->calculate(\$expression);
assert(\$actual == \$expected, new Exception("Expression '\$expression': expected '\$expected' but got '\$actual' instead."));
}

echo 'All tests passed!';
?>
``````
9. Flashynuff
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...

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.");
}
}
}
``````
10. teaearlgraycold
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:...
``````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

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

if __name__ == "__main__":
main()
``````