A Scala example: Reverse Polish Notation

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.

class RPN {
  private var stack: List[Float] = Nil
 
  def number(x: Float) =
    stack = x :: stack
   
  def result =
    stack.head
}

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:

def plus() =
  stack = stack match {
    case x :: y :: tail => (x + y) :: tail
    case tail => throw new IllegalStateException()
  }

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 minus and div the way we did, otherwise we had do define minus as op2((x, y) => y - x)):

private def op2(func : (Float, Float) => Float) : Unit = {
  stack = stack match {
    case x :: y :: tail => (func(y, x)) :: tail
    case tail => throw new IllegalStateException()
  }
}
 
def plus() = op2(_ + _)
def minus() = op2(_ - _)
def times() = op2(_ * _)
def div() = op2(_ / _)

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:

class RPN private(private val stack:List[Float]) {
  def this() = this(Nil)
 
  private def op2(func : (Float, Float) => Float) : RPN = {
    return stack match {
      case x :: y :: tail => new RPN((func(y, x)) :: tail)
      case tail => throw new IllegalStateException("Stack is empty")
    }
  }
 
  def number(x: Float) = new RPN(stack = x :: stack)
 
  def plus = op2(_ + _)
  def minus = op2(_ - _)
  def times = op2(_ * _)
  def divide = op2(_ / _)
 
  def result =
    if (!stack.isEmpty && stack.tail.isEmpty)
      stack.head
    else
      throw new IllegalStateException("Stack does not contain exactly one element")
}

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:

class RPNParser {
  private val numberRegex = """^([0-9,.]+)$""".r;
 
  private def applyRPNPart(part: String, rpn: RPN): RPN = part match {
    case numberRegex(y) => rpn.number(y.toFloat)
    case "+" => rpn.plus
    case "-" => rpn.minus
    case "*" => rpn.times
    case "/" => rpn.divide
    case x => throw new IllegalArgumentException(x+" is not valid")
  }
}

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

def calculate(expression: String): Float = {
  return calc(expression.split("""\s+""").toList, new RPN)
}
 
private def calc(parts: List[String], rpn: RPN): Float = {
  if (parts.isEmpty) {
    return rpn.result
  } else {
    try {
      return calc(parts.tail, applyRPNPart(parts.head, rpn))
    } catch {
      case e @ (_:IllegalStateException|_:IllegalArgumentException) =>
        throw new RuntimeException(e.getMessage()+
          " in: "+parts.:\("")((x, y) => x+" "+y))
    }
  }
}

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

object Main {
  private def processTerm(term: String): Unit = {
    try {
      println(new RPNParser().calculate(term))
    } catch {
      case e: RuntimeException => println(e.getMessage)
    }
  }
 
  def main(args: Array[String]): Unit = {
    var ok: Boolean = false
    do {
      val term = readLine("> ")
 
      ok = term != null && !term.isEmpty()
      if (ok)
        processTerm(term)
    } while (ok)
  }
}

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

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