Java OO Design - Reverse Polish Notation Calculator

Question

The following is my implementation of Reverse Polish Notation. I should have mentioned that this is for a coding question, which asked for unary, binary, ternary, etc. operations that also allows user-defined operators.

Would it make more sense to use Factory Pattern to replace the code inside the for loop of RPNIntegerCalculator's parse(String s) function? Any improvements or better OO design suggestions are welcome!

The Token interface defines behavior of all numbers/operators:

public interface Token<T> {
    void process(Deque<T> stack);
}

The Operand class implements Token interface and will push the number into the stack:

public class Operand<T> implements Token<T> {
    private final T val;

    public Operand(T val) {
        this.val = val;
    }

    @Override
    public void process(Deque<T> stack) {
        stack.push(val);
    }
}

The Operator class implements Token interface and will calculate the result:

public abstract class Operator<T> implements Token<T> {
    private final int numOfOperand;

    protected Operator(int numOfOperand) {
        this.numOfOperand = numOfOperand;
    }

    @Override
    public void process(Deque<T> stack) {
        if(stack == null) {
            throw new IllegalArgumentException("Stack is empty");
        }
        if(stack.size() < numOfOperand) {
            throw new IllegalArgumentException("There is not enough elements to calculate");
        }

        List<T> valList = new ArrayList<>(numOfOperand);
        for(int i = 0; i < numOfOperand; i++) {
            valList.add(0, stack.pop());
        }
        stack.push(calc(valList));
    }

    public abstract T calc(List<T> vals);
}

I have also created four classes that perform addition, subtraction, multiplication, and division on Integer (Showing Division class here):

public class DivideInteger extends Operator<Integer> {
    public DivideInteger(int numOfOperand) {
        super(numOfOperand);
    }

    @Override
    public Integer calc(List<Integer> vals) {
        double total = vals.get(0);
        for (int i = 1; i < vals.size(); i++) {
            total /= vals.get(i);
        }

        if (total > Integer.MAX_VALUE) {
            throw new ArithmeticException("Integer value overflow");
        }
        if (total < Integer.MIN_VALUE) {
            throw new ArithmeticException("Integer value underflow");
        }
        return (int) total;
    }
}

The RPNCalculator Interface defines calculator behavior:

public interface RPNCalculator<T> {
    default T evaluate(String expression) {
        return evaluate(parse(expression));
    }

    default T evaluate(List<Token<T>> tokens) {
        Deque<T> stack = new LinkedList<>();
        for (Token<T> t : tokens) {
            t.process(stack);
        }

        if (stack.size() != 1) {
            throw new IllegalArgumentException("Invalid Reverse Polish Notation Provided");
        }
        return stack.poll();
    }

    List<Token<T>> parse(String expression);
}

I have also implemented a Integer Calculator. The HashMap holds operator mapping and allows other user to add custom defined operations (The main function shows how to use this calculator):

public class RPNIntegerCalculator implements RPNCalculator<Integer> {
    private static final Map<String, Operator<Integer>> OPERATOR_MAP = new HashMap<>();

    public void addOperator(String symbol, Operator<Integer> operator) {
        OPERATOR_MAP.put(symbol, operator);
    }

    public void loadDefaultBinaryOperators() {
        OPERATOR_MAP.put("+", new AddInteger(2));
        OPERATOR_MAP.put("-", new SubtractInteger(2));
        OPERATOR_MAP.put("*", new MultiplyInteger(2));
        OPERATOR_MAP.put("/", new DivideInteger(2));
    }

    @Override
    public List<Token<Integer>> parse(String expression) {
        if(expression == null || expression.length() == 0) {
            throw new IllegalArgumentException("Invalid Reverse Polish Expression");
        }

        String[] tokens = expression.split(" ");
        List<Token<Integer>> tokenList = new ArrayList<>();
        for(String token : tokens) {
            if(OPERATOR_MAP.containsKey(token)) {
                tokenList.add(OPERATOR_MAP.get(token));
            } else {
                try {
                    tokenList.add(new Operand<>(Integer.decode(token)));
                } catch (NumberFormatException e) {
                    throw new IllegalArgumentException("Invalid Reverse Polish Token Found: " +
                            token, e);
                }
            }
        }

        return tokenList;
    }

    public static void main(String...args) {
        String rpn = "2 1 ? 3 *";
        RPNIntegerCalculator calculator = new RPNIntegerCalculator();
        calculator.loadDefaultBinaryOperators();
        System.out.println(calculator.evaluate(rpn));
    }
}

Answer 1

Overall this looks pretty good. But I can't shake the feeling that you probably over designed it a bit.

An interesting principle here is YAGNI by Martin Fowler. It stands for "you aren't gonna need it" and is tightly couple with the idea of refactoring a lot.

The first question I ask myself when looking at your code is: "Are there mathmatical operators that take more than 2 numbers?".

I couldn't quickly think of any that I would really want my basic calculator to have. So let's start by assuming we only need to work with BinaryOperators and refactor it in the future if we actually do want to add more advanced operators.

So let's simplify the Operator class and rename it to make it clear we only handle binary operators for now:

public abstract class BinaryOperator<T> implements Token<T> {

    @Override
    public void process(Deque<T> stack) {
        if(stack == null) {
            throw new IllegalArgumentException("Stack is empty");
        }
        if(stack.size() < numOfOperand) {
            throw new IllegalArgumentException("There is not enough elements to calculate");
        }

        T secondNumber = stack.pop();
        T firstNumber = stack.pop();
        stack.push(calc(firstNumber, secondNumber));
    }

    protected abstract T calc(T a, T b);
}

This means that we also have to simplify the implementing operators ofcourse:

public class DivideInteger extends BinaryOperator<Integer> {
    @Override
    protected Integer calc(Integer a, Integer b) {
        double total = a/b;

        if (total > Integer.MAX_VALUE) {
            throw new ArithmeticException("Integer value overflow");
        }
        if (total < Integer.MIN_VALUE) {
            throw new ArithmeticException("Integer value underflow");
        }
        return (int) total;
    }
}

---

The same principle also applies to the token parsing. I would expect that the tokens our program will be able to handle are all hard coded anyway. So like @gervais.b already suggested in a comment we shouldn't force the extra step of "loading the default operators". Instead we can just as well hard code it in the first place.

Another thing I would do here is not even store an instance for reuse in the first place. Since an instance of those operators is really small and the modern JVM's are good at creating and cleaning up small one time use instances we might as well create a new one each time.

So my initial idea is to replace the whole hashmap for tokens with a simple "parseToken(String token)" method.

public class RPNIntegerCalculator implements RPNCalculator<Integer> {
         @Override
    public List<Token<Integer>> parse(String expression) {
        if(expression == null || expression.length() == 0) {
            throw new IllegalArgumentException("Invalid Reverse Polish Expression");
        }

        String[] tokens = expression.split(" ");
        List<Token<Integer>> tokenList = new ArrayList<>();
        for(String token : tokens) {
            tokenList.add(parseToken(token));
        }
        return tokenList;
    }

    protected Token<Integer> parseToken(String token){
        switch(token) {
            case "+" :
                return new AddInteger();
            case "-" :
                return new SubtractInteger();
            case "*" :
                return new MultiplyInteger();
            case "/" :
                return new DivideInteger();
            default :
                try {
                    return new Operand<>(Integer.decode(token));
                } catch (NumberFormatException e) {
                    throw new IllegalArgumentException("Invalid Reverse Polish Token Found: " + token, e);
                }
        }           
    }
}

But we can actually go one step further. The entire parse method now looks like it could just as well be put in the superclass. Since there's no Integer specific functionality being used other than the parseToken method. Let's also make it a proper abstract class since it's doing most of the work and only delegates the specific token parsing to the subclasses.

public abstract class RPNCalculator<T> {
    public T evaluate(String expression) {
        if(expression == null || expression.length() == 0) {
            throw new IllegalArgumentException("Invalid Reverse Polish Expression");
        }

        String[] tokens = expression.split(" ");
        Deque<T> stack = new LinkedList<>();
        for (String token : tokens) {
            parseToken(token).process(stack);
        }

        if (stack.size() != 1) {
            throw new IllegalArgumentException("Invalid Reverse Polish Notation Provided");
        }
        return stack.poll();
    }

    protected abstract Token<T> parseToken(String token);
}

Ok, so I may have changed a bit more than you would expect from what I mentioned right before. The most notable thing is that I immediatly process a token as soon as it's parsed from the string. Given that it's a post-fix representation we know that we have all the needed information already in the stack to handle a token. So to me it looked like the most logical to do just that.

Notice that we no longer need to create a list with all the tokens. This works really well with my earlier point about creating an instance of an operator, using it and then immediatly throwing it away.

---

Now to answer your question

Would it make more sense to use Factory Pattern to replace the code inside the for loop of RPNIntegerCalculator's parse(String s) function?

I guess I have to say yes because that's basically what I did here.

The calculator implementations acts as a factory to transform a string into the correct tokens. (And than also calls the evaluation function on those tokens while parsing the string).

---

EDIT: adding non-binary operators to this solution.

Let's for example add the ++ operator that adds all the numbers currently on the stack.

1 2 1 3 ++ = 7

We first create a new class for the operator:

public class AddAllInteger implements Token<Integer> {

    @Override
    public void process(Deque<Integer> stack) {
                long result = 0;
        while(!stack.isEmpty()){
            result += stack.pop();
        }
        stack.add((int) result);
    }
}

And then we add it to the parse method so it can actually be used as well:

protected Token<Integer> parseToken(String token){
    switch(token) {
        case "+" :
            return new AddInteger();
        case "-" :
            return new SubtractInteger();
        case "*" :
            return new MultiplyInteger();
        case "/" :
            return new DivideInteger();
        case "++":
            return new AddAllInteger();
        default :
            try {
                return new Operand<>(Integer.decode(token));
            } catch (NumberFormatException e) {
                throw new IllegalArgumentException("Invalid Reverse Polish Token Found: " + token, e);
            }
    }           
}