Scala Tutorial Through Katas: Reverse Polish Notation (Medium)

A programming kata is an exercise which helps a programmer hone his skills through practice and repetition.

This article is part of the series “Scala Tutorial Through Katas”. Articles are divided into easy, medium and hard. Beginners should start with easy ones and move towards more complicated once they feel more comfortable programming in Scala.

For the complete list of Scala katas and solutions please visit the index page

The article assumes that the reader is familiar with the basic usage of ScalaTest asserts and knows how to run them from his favorite Scala IDE (ours is IntelliJ IDEA with the Scala plugin).

Tests that prove that the solution is correct are displayed below. Recommended way to solve this kata is to write the implementation for the first test, confirm that it passes and move to the next. Once all of the tests pass, the kata can be considered solved.

One possible solution is provided below the tests. Try to solve the kata by yourself first.

Reverse Polish Notation

In reverse Polish notation the operators follow their operands; for instance, to add 3 and 4, one would write “3 4 +” rather than “3 + 4″. If there are multiple operations, the operator is given immediately after its second operand; so the expression written “3 – 4 + 5″ in conventional notation would be written “3 4 – 5 +” in RPN: 4 is first subtracted from 3, then 5 added to it. An advantage of RPN is that it obviates the need for parentheses that are required by infix. While “3 – 4 * 5″ can also be written “3 – (4 * 5)”, that means something quite different from “(3 – 4) * 5″. In postfix, the former could be written “3 4 5 * -“, which unambiguously means “3 (4 5 *) -” which reduces to “3 20 -“; the latter could be written “3 4 – 5 *” (or 5 3 4 – *, if keeping similar formatting), which unambiguously means “(3 4 -) 5 *”.

More info can be found in the Wikipedia.

The goal of this kata is to create a program that performs calculations using reverse Polish notation.

Following unit tests were used in a TDD fashion while developing the solution.

[UNIT TESTS]

class ReversePolishNotationTest extends FlatSpec with Matchers {

  "calculateFunction" should "return stack with 2 elements popped and one element pushed" in {
    calcSign(List[Double](1, 2, 3, 4, 5), _ / _) should have size 4
  }

  it should "be use function parameter to calculate value that is pushed" in {
    calcSign(List[Double](1, 2, 3, 15, 3), _ / _).last should equal(5)
  }

  "calculate" should "be able to calculate single digit numbers" in {
    "1 2 +".calc should equal(3)
  }

  it should "be able to calculate multi digit numbers" in {
    "12 3 /".calc should equal(4)
  }

  it should "be able to handle negative numbers" in {
    "-12 3 /".calc should equal(-4)
  }

  it should "be able to handle decimal numbers" in {
    "-12.9 3 /".calc should equal(-4.3)
  }

  it should "be able to calculate more complex notations" in {
    "1 2 + 4 * 5 + 3 -".calc should equal(14)
  }

}

Test code can be found in the GitHub ReversePolishNotationTest.scala.

[ONE POSSIBLE SOLUTION]

object ReversePolishNotation {

  implicit class Calculator(input: String) {

    def calc: Double = {
      input.split(" ").foldLeft(List[Double]())((out, in) => {
        in match {
          case "+" => calcSign(out, _ + _)
          case "-" => calcSign(out, _ - _)
          case "*" => calcSign(out, _ * _)
          case "/" => calcSign(out, _ / _)
          case _ => out :+ in.toDouble
        }
      }).head
    }

  }

  private[solutions] def calcSign(nums: List[Double], operation:(Double, Double) => Double) = {
    nums.dropRight(2) :+ operation(nums.dropRight(1).last, nums.last)
  }

}

The solution code can be found in ReversePolishNotation.scala solution.

What was your solution? Post it as a comment so that we can compare different ways to solve this kata.

About these ads

2 thoughts on “Scala Tutorial Through Katas: Reverse Polish Notation (Medium)

  1. I ended up doing it almost exactly the same way, but two differences: first, my “stack” grows the other way so that I can take advantage of pattern matching. Second, I don’t have a separate “calcSign” method.

    def calc: Double = {
    s.split(” “).foldLeft(ListDouble) {
    case (x :: y :: rest, “+”) => y + x :: rest
    case (x :: y :: rest, “*”) => y * x :: rest
    case (x :: y :: rest, “-“) => y – x :: rest
    case (x :: y :: rest, “/”) => y / x :: rest
    case (list, num) => num.toDouble :: list
    }.head
    }

  2. Pingback: JAVA 8教程:逆波兰表示法 - java - Barnett‘s Blog

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s