A Scala example: Reverse Polish Notation

8 Feb

As you may already have heared, I am a big fan of Scala. I was asked to provide a few examples. I would not say that I am an expert, so I start with a really simple example.

Let’s write a really simple RPN calculator which reads a term from STDIN and prints out the result. The simple thing about RPN is that we only need a stack to calculate the result. So we start with this a class that includes the stack.

We add two Methods: number(Float) and result. The first one is used to add a new number to the stack, the second one yields the result.

To be able to calculate, we need a few more methods. Let’s start with an add function: If there are at least two elements on the stack, add the two top elements, remove them and put the result back. If there are less than two elements on the stack, this is an error. This is how our method looks:

It should be clear how the other methods could be implemented. But wait – there would be very much redundance in it. It would be nicer if the whole match-part could be excluded, only (x + y) is relevant here. So let’s extract a new function and add the other operations (Note that we swap x and y so we can define minusand div the way we did, otherwise we had do define minus as op2((x, y) => y - x)):

We can now create a new RPN object, push 3 numbers, call plus twice and read the result.

The List is immutable. We could write our code in a little more functional style by doing the same with our RPN class. Therefore we add a new constructor which takes the stack. There is no reason to make this constructor public. The operations will not return Unit but new RPN objects. This also changes the return value of op2. To handle invalid input, we throw an exception when result is called at the wrong time:

Okay. For the moment, the class is complete (we could obviously add more features like „**“ or a op1 method for „sin“, „cos“, „tan“, etc.).

The next task is to read a string and call the methods accordingly. Let’s do it bottom up. Imagine, we already have split the string up, we have a valid RPN object and we want to apply a single part of the string to the RPN object to generate a new object. This is simple:

Splitting a string is really simple. We process it recursively and do some error handling. This part is some kind of ugly. I think the calc method is just too long, I’m open to suggestions wink

Let’s add a main method and we are done:

Disclaimer: this is 100% not the finest Scala source on earth. However, I promised to show some lines of code and I did it. I’m still learning how to use the beauty of Scala, but perhaps this example is enough for you to start your own adventures in Scala smiley

You can also download the whole source.

Edit: a friend of mine wrote some german blog posts about implementing RPN in Clojure, it’s worth reading, I think wink

4 Replies to “A Scala example: Reverse Polish Notation

  1. Many thanks!
    I got the code examples running after changing the signature of the main method into
    def main(args: Array[String]) {
    Greetings, Rainer

    • At least with scala 2.9 both codes should compile to the same bytecode. Ich get the same output for both variants:

      $ scala -version
      Scala code runner version 2.9.0.1 — Copyright 2002-2011, LAMP/EPFL

      $ scalap Main
      object Main extends java.lang.Object with scala.ScalaObject {
      def this() = { /* compiled code */ }
      def main(args : scala.Array[scala.Predef.String]) : scala.Unit = { /* compiled
      code */ }
      }

      $ javap Main
      Compiled from „test.scala“
      public final class Main extends java.lang.Object{
      public static final void main(java.lang.String[]);
      }

      def x() { /* … */}
      should be just be the short form for
      def x(): Unit = { /* … */ }

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.