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

This article is part of the series Java Tutorial Through Katas.

Fizz Buzz (Easy) – Java 7
Berlin Clock (Easy) – Java 7 and 8
Tennis Game (Easy) – Java 7
Reverse Polish Notation (Medium) – Java 7 and 8

The article assumes that the reader already has experience with Java 7, that he is familiar with the basic usage of JUnit tests with Hamcrest matchers and that he knows how to run them from his favorite IDE (ours is IntelliJ IDEA).

Tests that prove that the solution is correct are displayed below. Recommended way to solve this kata is to use test-driven development approach (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.

Since many of the new features added to Java 8 were inspired by Scala and other functional programming languages, short comparison of Java 7 (or earlier), Java 8 and Scala solutions is provided at the end of the article.

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.

[TESTS]

public class ReversePolishNotationTest {

    @Test
    public void calcSignShouldReturnStackWithTwoElementsPoppedAndOneElementPushed() {
        Stack<Double> numbers = new Stack<>();
        IntStream.rangeClosed(1, 5).forEach(number -> numbers.add((double) number));
        Stack<Double> actual = calcSign(numbers, (num1, num2) -> num2 / num1);
        assertThat(actual.size(), is(equalTo(4)));
    }

    @Test
    public void calcSignShouldUseOperationParameterToCalculatePushedValue() {
        Stack<Double> numbers = new Stack<>();
        numbers.push((double) 15);
        numbers.push((double) 3);
        Stack<Double> actual = calcSign(numbers, (num1, num2) -> num2 / num1);
        assertThat(actual.pop(), is(5.0));
    }

    @Test
    public void calcShouldBeAbleToCalculateSingleDigitNumbers() {
        assertThat(calc("1 2 +"), is(equalTo(3.0)));
    }

    @Test
    public void calcShouldBeAbleToCalculateMultiDigitNumbers() {
        assertThat(calc("12 3 /"), is(equalTo(4.0)));
    }

    @Test
    public void calcShouldBeAbleToHandleNegativeNumbers() {
        assertThat(calc("-12 3 /"), is(equalTo(-4.0)));
    }

    @Test
    public void calShouldBeAbleToHandleDecimalNumbers() {
        assertThat(calc("-12.9 3 /"), is(equalTo(-4.3)));
    }

    @Test
    public void calShouldBeAbleToHandleMoreComplexNotations() {
        assertThat(calc("1 2 + 4 * 5 + 3 -"), is(equalTo(14.0)));
    }

}

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

[ONE POSSIBLE SOLUTION]

public class ReversePolishNotation {

    public static Double calc(String input) {
        Stack<Double> numbers = new Stack<>();
        Arrays.asList(input.split(" ")).stream().forEach(number -> {
            switch(number) {
                case "+":
                    calcSign(numbers, (n1, n2) -> n2 + n1);
                    break;
                case "-":
                    calcSign(numbers, (n1, n2) -> n2 - n1);
                    break;
                case "*":
                    calcSign(numbers, (n1, n2) -> n2 * n1);
                    break;
                case "/":
                    calcSign(numbers, (n1, n2) -> n2 / n1);
                    break;
                default:
                    numbers.push(Double.parseDouble(number));
            }
        });
        return numbers.pop();
    }

    protected static Stack<Double> calcSign(Stack<Double> numbers, BiFunction<Double, Double, Double> operation) {
        numbers.push(operation.apply(numbers.pop(), numbers.pop()));
        return numbers;
    }

}

Java 8 solution code can be found in the ReversePolishNotation.java.
Java 7 (old earlier) equivalent can be found in the ReversePolishNotationSeven.java.
Scala solution can be found in the Scala Tutorial Through Katas: Reverse Polish Notation (Medium) post.

First difference between Java 8 and 7 can be found in tests themselves. New IntStream class with range methods together with forEach provides a bit cleaner way to generate a range of numbers.

[JAVA 7]

for (int number = 1; number <= 5; number++) {
    numbers.add((double) number);
}

[JAVA 8]

IntStream.rangeClosed(1, 5).forEach(number -> numbers.add((double) number));

In the implementation code, we’re using function as calc method argument. BiFunction represents a function that accepts two arguments and produces a result. Java 7 solution uses the enum Sign instead. Using function resulted in more open and cleaner code.

Method is declared as:

[JAVA 8]

    protected static Stack<Double> calcSign(Stack<Double> numbers, BiFunction<Double, Double, Double> operation) {
        numbers.push(operation.apply(numbers.pop(), numbers.pop()));
        return numbers;
    }

To call the method with multiply operation:
[JAVA 8]

calcSign(numbers, (n1, n2) -> n2 * n1);

Java 7 solution used much more code to describe similar functionality using enum:

[JAVA 7]

    public enum Sign {

        ADD("+") {
            public double apply(double num1, double num2) {
                return num2 + num1;
            }
        },
        REMOVE("-") {
            public double apply(double num1, double num2) {
                return num2 - num1;
            }
        },
...

In this case Scala seems to be working in almost the same way as Java 8. The only difference is in few shortcuts that can be taken. For example, equivalent to Java 8 calcSign call is:

[SCALA]

...
calcSign(numbers, _ * _)
...

Another difference is Scala’s preference for immutability that can be seen in the foldLeft method.

[SCALA]

...
input.split(" ").foldLeft(List[Double]())((out, in) => {
...

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

Test-Driven Java Development

Test-Driven Java Development book wrote by Alex Garcia and me has been published by Packt Publishing. It was a long, demanding, but very rewarding journey that resulted in a very comprehensive hands-on material for all Java developers interested in learning or improving their TDD skills.

If you liked this article I am sure that you’ll find this book very useful. It contains extensive tutorials, guidelines and exercises for all Java developers eager to learn how to successfully apply TDD practices.

You can download a sample or purchase your own copy directly from Packt or Amazon.