18
votes
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.
JavaScript, ES6:
(
...
I might be overusing the destructuring operator just a tiny bit)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:
"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!
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.
Of course, the actual motivation of this was just to do RPN starting from the end of the string.
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:
First up!
Our braindead parser:
Here, we use Lua's inbuilt regex to split apart a string based on any whitespace.
There are some caveats.
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).
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.
And of course, implementing integer division is also nice and simple:
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.
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.
And linking in our functions is dead simple too, as we have first class functions, and UTF-8 strings.
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.
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.
Basic Racket with no fancy
eval
ormacro
nonsense or error handling!A C++17 version - with constexpr compile time support. Slightly hacky fixed size stack to allow compile time generation. Expects completely valid input.
Here's my own, once again in PHP:
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.