Scala: A Reverse Polish Notation (RPN) calculator written with foldLeft

Chapter 10 of the book, Learn You a Haskell for Great Good!, is titled, Functionally Solving Problems. In that chapter, the author describes a “Reverse Polish Notation” (RPN) calculator. If you ever used an old Hewlett-Packard (HP) calculator, you might know what that is. (At least that’s where I first learned about RPN.)

You don’t have to read it all yet, but some of that discussion is shown in this image:

The equation to solve

In short, the author shares this RPN equation:

"10 4 3 + 2 * -"

and then describes (a) how we should generically think about solving this problem, and then (b) how we should specifically solve this problem by writing an RPN Calculator in Haskell.

A Scala RPN Calculator

I’ll skip over that discussion, because you can find it online at that URL. Instead, I’ll jump right in and show one possible solution to this problem with this Scala RPN Calculator code:

package rpncalculator

object SolveRPN extends App {

    // the desired equation
    val equation = "10 4 3 + 2 * -"
    
    // print the solution
    println(solveRPN(equation))

    def solveRPN(eqn: String): Double = {
        val items = eqn.split(" ")
        val accumulator = List[Double]()
        items.foldLeft(accumulator)(foldingFunction).head
    }
   
    def foldingFunction (stack: List[Double], a: String): List[Double] = stack match {
        case List() => a.toDouble :: stack   // Nil, if you prefer
        case List(_) => a.toDouble :: stack
        case x::y::ys => a match {
            case "*" => x * y :: ys
            case "+" => x + y :: ys
            case "-" => y - x :: ys
            case "/" => y / x :: ys
            case s: String => s.toDouble :: stack
        }
    }

}

Discussion

As you can see from that code, I define the equation as a String, like this:

val equation = "10 4 3 + 2 * -"

Then I call the solveRPN method to get the solution as a Double value, which I print like this:

println(solveRPN(equation))

I tested my code against most of the equations shared in the Haskell book, including these:

val equation = "10 4 3 + 2 * -"
val equation = "2 3.5 +"
val equation = "10 2 ^"
val equation = "10 10 10 10 sum 4 /"

The last two equations are solved by adding these cases to the code shown above:

case "^" => Math.pow(y, x) :: ys
case "sum" => List(x + y + ys.sum)

The solveRPN method

Some people will say the solveRPN method is a little verbose, but I wrote it as is for clarity. I could have written it like this as well:

def solveRPN(eqn: String): Double = eqn.split(" ").foldLeft(List[Double]())(foldingFunction).head

That code also works, but whether it’s readable is subject to debate (depending on your experience with Scala, functional programming, the foldLeft method, your brain, and other factors).

The foldingFunction

The foldingFunction can be written in a variety of different ways; I’ve just shown one possible solution here which seems clean and also seems to follow the approach of the Haskell solution.

My solution first handles the case of an empty List, and then the case of a List with one item, and then handles the case of multiple List elements by looking at the value of a, where a may be a number or an operator.

Note that I could have written List() in the match/case expression as Nil instead. You can use whichever one seems to be more clear to you.

That’s all I’m going to write about this RPN problem and solution today. The “Learn You a Haskell” author covers this problem in detail, so I encourage you to read his discussion and solution.

Bonus: A little more about the Scala foldLeft method

If you haven’t used Scala’s foldLeft method before, I’ve updated this article to provide a discussion of how it works, in the context of this example. (If you already understand foldLeft, feel free to skip this part.)

The foldLeft method, found on Scala sequences, is a fun little method. Its signature looks like this:

def foldLeft[B](z: B)(f:(B, A) => B): B

What that signature means is that foldLeft is a method that takes two parameter lists, this one:

(z: B)

and this one:

(f:(B, A) => B)

The signature also infers that foldLeft works with two generic types, A and B, which I’ll discuss more in a few moments.

As the Scaladoc states, foldLeft “Applies a binary operator to a start value and all elements of this list, going left to right.”

The first parameter list

Looking back at my solution above, my first parameter list was named accumulator, and had this type:

List[Double]()

So for my solution, the generic parameter B is the type List[Double].

One note here: I don't think of this being an accumulator as much as I think of it as (a) setting the desired type, and (b) giving foldLeft a starting value. I've just seen "accumulator" as a common name in Haskell books, so I used that name here. It could be called something like startingList, emptyList, or anything else that makes sense to you.

The second parameter list

Again looking back at my solution, my second parameter list contains the method named foldingFunction. If you look at its signature, you’ll see that it matches the signature required by foldLeft’s second parameter list. Specifically, foldLeft’s second signature must look like this:

(f:(B, A) => B)

and my foldingFunction’s signature is this:

def foldingFunction (stack: List[Double], a: String): List[Double]

So again you see that the generic parameter B is the type List[Double], and now we see the generic parameter A is of type String. As a quick summary of this parameter list, this method takes two parameters, one of type B, the second of type A, and returns a result of type B.

More on the generic parameters A and B

When you think about this, you know that the generic type A must be a String, because that’s the type of our original list. Going back to my code, my original list was named items, and it had a type of List[String]:

val items = eqn.split(" ")

So the generic type A is easy to reason about; it’s the type contained by your list.

The generic type B is whatever you need for your solution. For this problem I needed for B to have the type List[Double] to implement the algorithm described in the Learn You a Haskell book.

Summary

In summary, if you were interested in seeing how to solve that RPN calculator problem with foldleft in Scala, or just wanted to see a foldleft example, I hope this article has been helpful.