[Java] Evaluate reverse polish notation using a stack

Reverse polish notation, aka the WTF! way of writing arithmetical expressions, presents an interesting exercise on stacks.

The goal is to write a program to evaluate RPN expressions eg: 3 4 + would return 7.

The input can be passed in many ways, good candidates are arrays and lists, a stack directly or a string, although in this case, you would need a separator character to understand when does a number start and end.

The idea here is to process the input sequence from left to right without creating the stack beforehand. If we encounter a number (operand), we push it onto the stack and when we encounter an operator, we pop two items from the stack, then apply the operator in the (gotcha!) REVERSE order because the stack is LIFO and this matters for the asymmetrical operations such as - and /

An interesting note, dividing by 0 a double will NOT throw an exception, we must test if we got infinite as result!

For the implementation I use a String array as input and a Double stack to allow decimal results. Only the four basic operations (sum, subtraction, multiplication, division) are supported, but the code can easily be expanded to support more and even unary operations (pop one item instead of two).

As last note: why can't we do this in constant space while parsing the string itself? Because of situations such as: 3 - (4 x 5) which translates to 3 4 5 x -

Therefore we cannot expect an operator to always follow two operands.. So: String as input = bad.

The current implementation therefore uses O(N) space and time. But you can check here for an implementation that uses O(N) time and O(1) space!

You can check the implementation on my Gist along with some test cases in RPNJTests.

You can find here the code to convert an expression to reverse polish notation.