Reverse Polish Notation calculator with unit tests

Question

I had an interview with a global company yesterday. They had given me a programming assignment. I shared my screen and I must have finished the task in 1.5 hours.

Task was programming Reverse Polish Notation calculator in Java. I had developed as I shared my code below. I was rejected by not being stick to KISS and DRY principles. How should I improve my code according to these principles?

Calculator.java

package com.luxoft;

import java.util.Stack;



import com.luxoft.model.Element;
import com.luxoft.model.Number;

public class Calculator {

    private Stack<Element> operationStack = new Stack<>();

    public Integer add(String elements) {
        return null;
    }

    public Integer calculate( String elements ) throws Exception {
        operationStack.clear();
        String[] elementArray = elements.split(" ");
        for( int i=0; i<elementArray.length; i++ ) {
            String element = elementArray[i];
            Element operationElement = ElementExtractor.extract(element);
            operationElement.process(operationStack);   
        }

        System.out.println( "operationStack.size():"+operationStack.size() );

        if( operationStack.size() != 1 ) {
            throw new Exception("not calculated");
        }

        return ((Number)operationStack.pop()).getValue();
    }

}

ElementExtractor.java

package com.luxoft;

import java.util.HashMap;
import java.util.Map;

import com.luxoft.model.DivideOperator;
import com.luxoft.model.Element;
import com.luxoft.model.MinusOperator;
import com.luxoft.model.MultiplyOperator;
import com.luxoft.model.Number;
import com.luxoft.model.PlusOperator;

public class ElementExtractor {

    private static Map<String,Element> map = new HashMap<String,Element>();

    static {
        map.put("+", new PlusOperator());
        map.put("-", new MinusOperator());
        map.put("*", new MultiplyOperator());
        map.put("/", new DivideOperator());
    }

    public static Element extract(String element) {
        try {
            Integer i = Integer.parseInt(element);
            return new Number(i);
        }catch (NumberFormatException e) {
            return map.get(element);
        }
    }

}

Other Classes

package com.luxoft.model;

import java.util.Stack;

public abstract class Element {

    public abstract Stack<Element> process( Stack<Element> stack );

}


public class Number extends Element{

    private Integer value;

    public Number(Integer value) {
        this.value = value;
    }

    public Stack<Element> process( Stack<Element> stack ){
        stack.push( this );
        return stack;
    }

    public Integer getValue() {
        return value;
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + ((value == null) ? 0 : value.hashCode());
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Number other = (Number) obj;
        if (value == null) {
            if (other.value != null)
                return false;
        } else if (!value.equals(other.value))
            return false;
        return true;
    }



}



public class PlusOperator extends Element{

    public PlusOperator() {
    }

    @Override
    public Stack<Element> process(Stack<Element> stack) {
        Number secondElement = (Number)stack.pop();
        Number firstElement = (Number)stack.pop();
        stack.push(new Number( firstElement.getValue() + secondElement.getValue() ) );
        return stack;
    }
}

public class MinusOperator extends Element{

    public MinusOperator() {
    }

    @Override
    public Stack<Element> process(Stack<Element> stack) {
        Number secondElement = (Number)stack.pop();
        Number firstElement = (Number)stack.pop();
        stack.push(new Number( firstElement.getValue() - secondElement.getValue() ) );
        return stack;
    }

}


public class MultiplyOperator extends Element{

    public MultiplyOperator() {
    }

    @Override
    public Stack<Element> process(Stack<Element> stack) {
        Number secondElement = (Number)stack.pop();
        Number firstElement = (Number)stack.pop();
        stack.push(new Number( firstElement.getValue() * secondElement.getValue() ) );
        return stack;
    }
}


public class DivideOperator extends Element{

    public DivideOperator() {
    }

    @Override
    public Stack<Element> process(Stack<Element> stack) {
        Number secondElement = (Number)stack.pop();
        Number firstElement = (Number)stack.pop();
        stack.push(new Number( firstElement.getValue() / secondElement.getValue() ) );
        return stack;
    }

}

And Unit Tests

package com.luxoft;

import static org.junit.Assert.assertEquals;

import org.junit.Test;

public class CalculatorTest {

    @Test
    public void shouldCalculateCorrectWhenAdded() throws Exception {
        Calculator calculator = new Calculator();
        assertEquals(calculator.calculate("8 7 +"), Integer.valueOf(15) );
    }

    @Test
    public void shouldCalculateCorrectWhenAddedMultipleValues() throws Exception {
        Calculator calculator = new Calculator();
        assertEquals(calculator.calculate("99 11 + 8 7 + +"), Integer.valueOf(125) );
    }

    @Test
    public void shouldCalculateCorrectWhenMultiplied() throws Exception{
        Calculator calculator = new Calculator();
        assertEquals(calculator.calculate("4 7 *"), Integer.valueOf(28));
    }

    @Test
    public void shouldCalculateCorrectWhenMultipliedMultipleValues() throws Exception{
        Calculator calculator = new Calculator();
        assertEquals(calculator.calculate("4 7 * 5 2 * *"), Integer.valueOf(280));
    }

    @Test
    public void shouldCalculateCorrectWhenSubtracted() throws Exception {
        Calculator calculator = new Calculator();
        assertEquals( calculator.calculate("8 3 -") , Integer.valueOf(5));
    }

    @Test
    public void shouldCalculateCorrectWhenSubtractedMultipleValues() throws Exception {
        Calculator calculator = new Calculator();
        assertEquals( calculator.calculate("33 3 - 10 6 - -") , Integer.valueOf(26));
    }

    @Test
    public void shouldCalculateCorrectWhenDivided() throws Exception {
        Calculator calculator = new Calculator();
        assertEquals( calculator.calculate( "36 9 / " ) , Integer.valueOf(4));
    }

    @Test
    public void shouldCalculateCorrectWhenDividedMultipleValues() throws Exception {
        Calculator calculator = new Calculator();
        assertEquals( calculator.calculate( "90 3 / 30 5 / /" ) , Integer.valueOf(5));
    }

    @Test
    public void shouldCalculateCorrectWhenAnyOperation() throws Exception{
        Calculator calculator = new Calculator();
        assertEquals( calculator.calculate( "15 7 1 1 + - / 3 * 2 1 1 + + -" ) , Integer.valueOf(5));
    }

    @Test
    public void shouldCalculateCorrectWhenAnyExample() throws Exception{
        Calculator calculator = new Calculator();
        assertEquals( calculator.calculate( "2" ) , Integer.valueOf(2));
        assertEquals( calculator.calculate( "3 4 +" ) , Integer.valueOf(7));
        assertEquals( calculator.calculate( "12 4 / 1 -" ) , Integer.valueOf(2));
        assertEquals( calculator.calculate( "12 4 1 - /" ) , Integer.valueOf(4));
        assertEquals( calculator.calculate( "15 7 1 1 + - / 3 * 2 1 1 + + -" ) , Integer.valueOf(5));

    }
}

Answer 1

Your naming is inconsistent and confusing. What is an "Element"? Why does operationStack contain Elements rather than Operations, as its name would suggest? Why is elementArray an array of Strings rather than of Elements, as its name would suggest? Why is Number an Element, and why does its .getValue() method return an Integer? You should stick to standard terminology: the input consists of tokens, which are interpreted as operations that manipulate a stack of numbers. Furthermore, you should avoid picking class names that conflict with the standard Java library — specifically, com.luxoft.model.Number shadows java.lang.Number. If you think about it, your Number class is really a kind of operation: a "push some number onto the stack" operation.

The .process(Stack<Element> stack) method returns a Stack<Element>, which implies that it returns a new stack object rather than mutating the existing one. If all of the operations always mutate the existing stack, then you should follow the convention and return void instead.

Avoid using java.util.Stack. The documentation recommends using java.util.ArrayDeque instead.

Your Calculator.add(String elements) is dead code.

No-arg public constructors are implicit; you don't have to define constructors that contain no code.

Since Java 9, you can write

Map.of("+", new PlusOperator(),
       "-", new MinusOperator(),
       …);

Since your Element class is an abstract class with a single unimplemented method, you can make a @FunctionalInterface, which would greatly reduce the amount of boilerplate in each concrete class.

Suggested solution

import java.util.Deque;

@FunctionalInterface
public interface Operation {
    void apply(Deque<Number> stack);
}

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Map;

public class Calculator {
    private static final Map<String, Operation> SYMBOLS = Map.of(
        "+", stack -> {
            stack.push(stack.pop().doubleValue() + stack.pop().doubleValue());
        },
        "-", stack -> {
            Number subtrahend = stack.pop();
            stack.push(stack.pop().doubleValue() - subtrahend.doubleValue());
        },
        "*", stack -> {
            stack.push(stack.pop().doubleValue() * stack.pop().doubleValue());
        },
        "/", stack -> {
            Number divisor = stack.pop();
            stack.push(stack.pop().doubleValue() / divisor.doubleValue());
        }
    );

    public static Operation operationFor(String token) {
        Operation op = SYMBOLS.get(token);
        if (op != null) {
            return op;
        } else {
            return (stack -> stack.push(Double.parseDouble(token)));
        }
    }

    private Deque<Number> stack = new ArrayDeque<>();

    public void process(String... tokens) {
        for (String token : tokens) {
            operationFor(token).apply(stack);
        }
    }

    public Number calculate(String input) {
        this.stack.clear();
        this.process(input.split(" "));
        if (this.stack.size() != 1) {
            throw …
        }
        return this.stack.pop();
    }
}

Answer 2

So, I'm late to the party, but I'm going to say I think your approach is a lot more complicated it has to be. Solving RPN is a stack and a loop. Unless I was explicitly being asked to show extensible code, I don't think I'd even use an operation type. It's hard to tell because we weren't there to ask questions - 1.5 hours seems like a really long time for that problem.

If you do decide to go with an Operation, you don't necessarily need a separate class file for each instance. You could have an interface and anonymous functions that implement it, or perhaps an enum of operations.

I felt like playing around, so I took a stab at this. Without an Operation, I wound up with this code.

public final class Calculator {

    public static void main(final String[] argv) {
        final Calculator calculator = new Calculator();
        System.out.println(calculator.calculate("8 7 +")); //15
        System.out.println(calculator.calculate("99 11 + 8 7 + +")); //125
        System.out.println(calculator.calculate("4 7 *")); //28
        System.out.println(calculator.calculate("4 7 * 5 2 * *")); //280
        System.out.println(calculator.calculate("8 3 -")); //5
        System.out.println(calculator.calculate("33 3 - 10 6 - -")); //26
        System.out.println(calculator.calculate("36 9 / ")); //4
        System.out.println(calculator.calculate("90 3 / 30 5 / /")); //5
        System.out.println(calculator.calculate("15 7 1 1 + - / 3 * 2 1 1 + + -")); //5

    }

    private int calculate(final String input) {
        final Deque<Integer> stack = new LinkedList<>();
        final String[] values = input.split(" ");
        for (final String value : values) {
            final Integer intValue = this.parseInt(value);
            if (intValue == null) {
                this.operate(value, stack);
            } else {
                stack.push(intValue);
            }
        }
        return stack.pop();
    }

    private Integer parseInt(final String value) {
        try {
            return Integer.parseInt(value);
        } catch (final NumberFormatException e) {
            return null;
        }
    }

    private void operate(final String operator, final Deque<Integer> stack) {
        switch (operator) {
        case "+" :
            stack.push(stack.pop() + stack.pop());
            break;
        case "-" :
            final int subtrahend = stack.pop();
            stack.push(stack.pop() - subtrahend);
            break;
        case "*" :
            stack.push(stack.pop() * stack.pop());
            break;
        case "/" :
            final int denominator = stack.pop();
            stack.push(stack.pop() / denominator);
            break;
        default :
            throw new IllegalStateException("Unknown operator " + operator);
        }
    }

}

With an operation class, my take would be:

import java.util.Collections;
import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

public final class Calculator {

    private static final Map<String, Operation> OPERATIONS = buildMap();

    public static void main(final String[] argv) {
        final Calculator calculator = new Calculator();
        System.out.println(calculator.calculate("8 7 +")); //15
        System.out.println(calculator.calculate("99 11 + 8 7 + +")); //125
        System.out.println(calculator.calculate("4 7 *")); //28
        System.out.println(calculator.calculate("4 7 * 5 2 * *")); //280
        System.out.println(calculator.calculate("8 3 -")); //5
        System.out.println(calculator.calculate("33 3 - 10 6 - -")); //26
        System.out.println(calculator.calculate("36 9 / ")); //4
        System.out.println(calculator.calculate("90 3 / 30 5 / /")); //5
        System.out.println(calculator.calculate("15 7 1 1 + - / 3 * 2 1 1 + + -")); //5

    }

    private int calculate(final String input) {
        final Deque<Integer> stack = new LinkedList<>();
        final String[] values = input.split(" ");
        for (final String value : values) {
            final Integer intValue = this.parseInt(value);
            if (intValue == null) {
                OPERATIONS.get(value).operate(stack);
            } else {
                stack.push(intValue);
            }
        }
        return stack.pop();
    }

    private Integer parseInt(final String value) {
        try {
            return Integer.parseInt(value);
        } catch (final NumberFormatException e) {
            return null;
        }
    }


    private interface Operation {

        void operate(final Deque<Integer> stack);
    }

    private static Map<String, Operation> buildMap() {
        final Map<String, Operation> map = new HashMap<>();
        map.put("+", stack -> stack.push(stack.pop() + stack.pop()));
        map.put("-", stack -> {
            final int subtrahend = stack.pop();
            stack.push(stack.pop() - subtrahend);
        });
        map.put("*", stack -> stack.push(stack.pop() * stack.pop()));
        map.put("/", stack -> {
            final int denominator = stack.pop();
            stack.push(stack.pop() / denominator);
        });
        return Collections.unmodifiableMap(map);
    }

Answer 3

1. Problem model
In my opinion this problem should rarely use more than three classes. I actually only need two: Operation and value. In each string are only the mathematical operations and the values. This would have cut down your code in half, I assume.

2. Design
I really hope you came prepared and you brought some paper. A Polnish notation calculator can be calculated with stacks. But if I was under some time pressure and if I had the three restrictions Java, KISS and DRY, I would have come up with something like this:

The Component should have been an abstract class, but that information is redundant. This is an example of the Composite Pattern, which is one of the Big Four Design Patterns. Another change in your code could have been the implementation of the Singleton pattern or using static methods. But in my opinion that would not have lowered the complexity of your code.
In this model I do not care, how much memory it takes. I just implement the getValue and call the getValue of Operation and Value, to get the answer of the root Component.
It is also an AST (abstract syntax tree, Reference) This design is taught on a regular basis in University nowadays over multiple courses. It is faster than the stack/array implementation. The faster speed comes with worse memory usage than an in-place stack calculation.

3. Implementation
I hope there is no discussion, that this is really simple to implement. I would have reused this: String[] elementArray = elements.split(" ");

Some pseudo-Code

int start;
static int end; // for whole code;
start = 0;
end = elementArray.length - 1;
if (end == start) return elementArray[start].toString();
/* else */
if (isNumber (elementArray[end])) throw new Exception;

Operation root = new Operation(elementArray, end);
root.getValue(); // is the result

public Operation constructor looks something like this
value = elementArray[end];
if (isValue(elementArray[--end])) {//goes backward
    operand2 = new Value(elementArray[end]); //does something
    if(isValue(elementArray[--end]) //next: goes backward
        operand1 = new Value(elementArray[end]); //does something
        //the end, both are values
    else {
        // new starting point for next Operation
        operand1 = new Operation(elementArray, end);
    }
} else {
    // new starting point for next Operation
    operand2 = new Operation(elementArray, end);
    if(isValue(elementArray[--end])
        operand1 = new Value(elementArray[end]);
    else {
        operand1 = new Operation(elementArray, end);
    }
} //all in all four cases

getValue() always returns a double.

• an Operation decides which mathematical operation is done. It uses the getValue on the Operands and with those numbers it executes the operation.

• a Value returns on call of getValue the String as double (or stores the number as double)

  4. Testing

The unit tests are great.
Again with pen and paper, two examples would suffice.
Change one of them to this 15 0 1 1 + - / 3 * and this equals -22.5
If one calculate function is able to get the correct answer, this case would be done.
Then there is the no-division-with-zero-problem. If that case is handled well, everything is proven to work.

5. Even more improvement
Again, pen and paper: In the design phase, turn the reverse Polnish notation into a Polnish notation. Someone taught me that, and it can be proven by example. That would lead you to search in stackoverflow or codereview for some duplicates over here, here or here. Or you design it with my classes, or your stack and you do not have to think reverse. That makes it easier to solve it.
Anyway, I wish you better luck next time. If I had to give improvement hints, the design phase and the reflection of your code is very important. The tests could have shown your expertise with the mathematical field.