# RPN Calculator (using Scala, python and Java)

1. Description

One of the earliest Programming Praxis challenges is called RPN Calculator . Our task is to write a RPN module capable of evaluating simple RPN expressions and return the right result . The exact requirment:

Implement an RPN calculator that takes an expression like `19 2.14 + 4.5 2 4.3 / - *` which is usually expressed as `(19 + 2.14) * (4.5 - 2 / 4.3)` and responds with 85.2974. The program should read expressions from standard input and print the top of the stack to standard output when a newline is encountered. The program should retain the state of the operand stack between expressions.

Programming Praxis

The natural algorithm to resolve this exercise is stack-based :

 The first step is to tokenize the expression .If the expression is “19 2.14 + 4.5 2 4.3 / – *” after the tokenization the resulting structure will be an array of operands and operators, for example an array of Strings {“19”, “2.14”, “+”, “4.5”, “2”, “4.3”, “/”, “-“, “*”} . At the second step we iterate over the array of tokens .If the token: Is an operand (number, variable) – we push in onto the stack . Is an operator (we apriopri know the operator takes N arguments), we pop N values from the stack, we evaluate the operator with those values as input parameters, we push the result back onto the stack . If the RPN expression is valid, after we apply the previous steps, the stack would contain only one value, which is the result of the calculation .

2. Implementation

I will implement the solutions for this challenge using three different languages: Scala, python and Java .

2.1 Scala Solution

And if we compile and run the above code:

And now some short explanations:

RPNCalc is called a singleton object . I believe this is the official Scala “work-around” for defining static utilities functions . Anyways, pretty elegant for an work-around (being ironic) .
ops is HashMaplike data-structure that maps a given string (in our case operators “+”, “-“, “*”, “/”) with an associated function literal . Thus we can use the map’s elements just like “normal” functions, for example: ops(“+”)(1, 3) evaluates to 4 .You may wonder what’s with the : ((_:Double) + (_:Double)) syntax . This is a concise way of saying ((a:Double, b:Double) => a + b), so the ops can anytime be rewritten as:

evalTokens(tokens: Array[String]) works exactly as described in the algorithm presentation, the only notable thing about it, is that it uses the mutable version of a Stack data structure .
And in the main function:

Is the same as saying:

in Java (read line by line from standard input) .

2.2 Python Solution

At a first glimpse the python implementation looks very similar to the Scala implementation . Still there are some subtle differences, as python doesn’t have all the functional characteristics, and the programming style is a little different .

2.3 Java Solution

This solution is probably the most verbose, as Java has the more strict and primitive syntax, when compared to its counterparts .

In this particular case I wanted to imitate the previous solutions: have a map (dictionary) with operators and the corresponding anonymous functions . Unfortunately Java doesn’t have support for such constructs (lambda functions, clojures, etc.), so I had to somehow find a work-around .

The first Java solution:

Ok, but having an inner interface + some anonymous classes is a little overkill for our particular case . Maybe a more natural approach for Java would be to use functions instead:

Conclusions:

Every language has its strength and weaknesses . Python is easy to learn, to read, to write and more important is fun . Java is verbose, but fast, and Scala, Scala is something new .

If you have any suggestions don’t hesitate to comment .

You may find interesting the following article: Shunting Yard Algorithm (how to convert infix expressions to Reverse Polish Notation).