Reverse Polish Notation Evaluation in Java

Question

I would like to hear feedback about my code both in term of improving efficiency if possible or using other data structures. Also go ahead and let me know about code styles/patterns.

/**
 * Created by mona on 5/26/16.
 */
import java.util.Arrays;
import java.util.Stack;
import java.util.HashSet;
public class EvaluateReversePolishNotation {
    //["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
    public static int evaluateReversePolishNotation(String[] tokens) throws ArithmeticException {
        Stack<Integer> stk = new Stack<>();
        HashSet<String> ops = new HashSet<>(Arrays.asList("+","-","*","/"));
        for (int i=0; i<tokens.length; i++) {
            if (!ops.contains(tokens[i])) {
                stk.push(Integer.parseInt(tokens[i]));
            }
            else {
                int secondOperand = stk.pop();
                int firstOperand = stk.pop();
                switch (tokens[i]) {
                    case "+":
                        stk.push(firstOperand+secondOperand);
                        break;
                    case "-":
                        stk.push(firstOperand-secondOperand);
                        break;
                    case "*":
                        stk.push(firstOperand*secondOperand);
                        break;
                    case "/":
                        if (secondOperand == 0) {
                            throw new ArithmeticException("Second operand can't be zero in division");
                        }
                        stk.push(firstOperand/secondOperand);
                        break;
                    default:
                        break;
                }
            }
        }
        return stk.pop();
    }

    public static void main(String[] args) {
      String[] revPolishNotations ={"2","1", "+", "3", "*"};
      System.out.println(evaluateReversePolishNotation(revPolishNotations));
    }
}

Answer 1

public class EvaluateReversePolishNotation {

As a general rule, name classes and objects as nouns. Verbs are used for methods. I personally like PostfixCalculator, but if you want these words, consider:

public class ReversePolishNotationEvaluator {

Now it's a noun.

        HashSet<String> ops = new HashSet<>(Arrays.asList("+","-","*","/"));

I would mark down for this when evaluating code.

        Set<String> ops = new HashSet<>(Arrays.asList("+", "-", "*", "/"));

Unless you are specifically using some method that only exists in that specific implementation, I would always recommend using the interface as the type.

I prefer a little whitespace in my lists.

Note that you don't actually need this.

        HashSet<String> ops = new HashSet<>(Arrays.asList("+","-","*","/"));
        for (int i=0; i<tokens.length; i++) {
            if (!ops.contains(tokens[i])) {
                stk.push(Integer.parseInt(tokens[i]));
            }
            else {
                int secondOperand = stk.pop();
                int firstOperand = stk.pop();
                switch (tokens[i]) {
                    case "+":
                        stk.push(firstOperand+secondOperand);
                        break;
                    case "-":
                        stk.push(firstOperand-secondOperand);
                        break;
                    case "*":
                        stk.push(firstOperand*secondOperand);
                        break;
                    case "/":
                        if (secondOperand == 0) {
                            throw new ArithmeticException("Second operand can't be zero in division");
                        }
                        stk.push(firstOperand/secondOperand);
                        break;
                    default:
                        break;
                }
            }
        }

It's enough to write

        for (String token : tokens) {
            stk.push(processToken(stk, token));
        }

and separately

    public static String processToken(Stack stack, String token) throws ArithmeticException {
        switch (token) {
            case "+":
                return stack.pop() + stack.pop();
            case "-":
                Integer subtrahend = stack.pop();
                return stack.pop() - subtrahend;
            case "*":
                return stack.pop() * stack.pop();
            case "/":
                Integer divisor = stack.pop();
                if (divisor == 0) {
                    throw new ArithmeticException("Divisor can't be zero");
                }

                return stack.pop() / divisor;
            default:
                return Integer.parseInt(token);
        }
    }

The advantage of this is that you only write each operator down once. So adding or removing an operator only needs to be done in one place. In the original code, you had to change in two places. This can lead to odd behavior if you make changes.

The separate method saves having to rewrite stk.push( constantly. Yes, we write return a lot, but we no longer need to break.

I would prefer the for each form or the advanced for loop to a C-style for loop anytime you don't use the index variable for anything other than indexing the collection.

You also might consider having a PostfixCalculator class with an object field of a Stack. Then you wouldn't have to pass the Stack around. Obviously the two methods would no longer be static in that case.

It's not clear to me that you gain anything by the check for division by zero. If you actually divide by zero, it will throw an ArithmeticException anyway. Why do so manually? Normally it would be because you wanted to add something to the error message or log something prior to throwing the exception. Or to keep going after handling the exception. But you don't do any of that here. So why the extra code? If there's a reason, put it in a comment so that no one undoes what you did.

It would make more sense to me to catch the exception for the stack being empty. That's likely to happen due to bad input. If you catch it, you can add additional information about the error. In particular, what token failed.

Similarly, you might want to handle the situation where the stack is not empty. If you have more than one value left on the stack after processing all the tokens, then there was a mistake somewhere.

Note that the JavaDoc for Stack says to use Deque instead.

Answer 2

Overall, I think the code works well for what it intends to solve. Some minor thing to note is with your variable naming. I had a mentor who once told me that before, programming languages only allowed at most 2 characters in them, so he said we're quite fortunate that modern programming languages allow much much longer identifiers. Take advantage of that, and make your variable names more descriptive. It only saves you a few effort typing stk instead of stack. In addition, modern IDEs are very capable of auto-completion, so typing long, descriptive identifiers aren't that much of an issue. You've already done that with your method name, which is good, so you should extend that to your other identifiers.

One other thing is to use interface when declaring Collections. Instead of declaring ops (operations) as HashSet, it should be just Set. This way, it's easier to shift to a different concrete implementation in the future.

As for the code, I think you can improve it a bit by using enum for operations. I'm not sure if this is a bit of over-engineering, but I think this will make the evaluateReversePolishNotation method a bit easier to read (or at least look at). The following is not complete, but hopefully it illustrates my point:

public enum BinaryOperator {
    PLUS("+") {
        int operate(int operand1, int operand2) {
            return operand1 + operand2;
        }
    },
    DIVIDE("/") {
        int operate(int operand1, int operand2) {
            if (operand2 != 0) {
                return operand1 / operand2;
            } else {
                throw new ArithmeticException("Cannot divide by zero.");
            }
        }
    };

    static final Map<String, BinaryOperator> MAP;

    static {
        Map<String, BinaryOperator> map = new HashMap<>();
        for (BinaryOperator operator : BinaryOperator.values()) {
            map.put(operator.operator, operator);
        }
        MAP = Collections.unmodifiableMap(map);
    }

    String operator;

    BinaryOperator(String operator) {
        this.operator = operator;
    }

    abstract int operate(int operand1, int operand2);

    static Map<String, BinaryOperator> getMap() {
        return MAP;
    }

}

With this enum in place, you can refactor the method in question to be:

public static int evaluateReversePolishNotation(String[] tokens) {
    Stack<Integer> stack = new Stack<>();
    Map<String, BinaryOperator> operationMap = BinaryOperator.getMap();
    BinaryOperator operator;
    //use foreach construct
    for (String token : tokens) {
        if (!operationMap.containsKey(token)) {
            stack.push(Integer.parseInt(token));
        }
        else {
            int secondOperand = stack.pop();
            int firstOperand = stack.pop();
            operator = operationMap.get(token);
            stack.push(operator.operate(firstOperand, secondOperand));
        }
    }
    return stack.pop();
}

Notice that in the code above, there's no declaration of ArithmeticException because it's unchecked (RuntimeException).

Answer 3

Integer arithmetic

For a "calculator", it's not intuitive that the / operator performs integer division. You should either fix that or document it clearly.

Implementation

Class names should be nouns; I recommend ReversePolishNotationEvaluator. The function name can be shortened to just evaluate().

The HashSet is a redundant complication. Any token that is not recognized as an operator could just be handled by the default case.

It is not necessary to throw ArithmeticException explicitly; the JVM will do it for you if you attempt to divide by 0. It is also not necessary to declare ArithmeticException, since it is a RuntimeException. If you decide to do so explicitly, though, I recommend that you also declare NumberFormatException, which could happen with Integer.parseInt(). (For that matter, there's also a NoSuchElementException that can occur with stack underflow, which you have not bothered to handle.)

The for loop should just be written as for (String token : tokens).

In opposition to some advice given in other answers, I recommend writing stk.push() explicitly for each operation. Reverse Polish Notation calculators should let each operator manipulate the stack directly. This allows you to implement operators like "!", "drop", and "dup", which don't necessarily pop two operands and push one result.

As stated in the JavaDoc, ArrayDeque should be preferred over java.util.Stack, even if Stack is not quite deprecated.

import java.util.*;

public class ReversePolishNotationEvaluator {
    public static int evaluate(String[] tokens) throws ArithmeticException, NumberFormatException {
        Deque<Integer> stk = new ArrayDeque<>();
        for (String token : tokens) {
            switch (token) {
              case "+":
                stk.push(stk.pop() + stk.pop());
                break;
              case "-":
                stk.push(-stk.pop() + stk.pop());
                break;
              case "*":
                stk.push(stk.pop() * stk.pop());
                break;
              case "/":  // NOTE: Integer division truncates towards 0
                int divisor = stk.pop();
                stk.push(stk.pop() / divisor);
                break;
              default:
                stk.push(Integer.parseInt(token));
            }
        }
        return stk.pop();
    }

    public static void main(String[] args) throws ArithmeticException, NumberFormatException {
        System.out.println(evaluate(args));
    }
}

Going further

If you develop this calculator further, the switch block could get unwieldy. At that point, you may wish to consider defining operators as objects.

Answer 4

The provided answers mostly deal with the current state of your code and will improve it of course. And as this solution will work so or so I will not say anything about that. I want you to focus on another subject that wasn't adressed specificly:

You did not identify the possible movable parts.

Will the number of operations increase? Will the number of operands differ from 2 in the future?

Why is this important at all?

If you do not support the movable parts then often you will have to implement your algorithms nearly from scratch again and again as it is based on assumptions that are cutoffs to only address the "next" requirement. The principle that is violated by restructuring your code everytime a new requirement occurs: Open-Closed-Principle.

You know that you have currently four operators. The movable parts begin with 2 elements. So you had 3 times to identify that the if-statement was an inappropriate structure as it will have to be extended everytime a new operator occurrs. You do not need to implement all operators known to you but you should implement a structure that represents the nature of an operator: It is independent from other operators. So every operator should get its own class.

You know that some operators need only one (faculty), some more than two operands (complex functions). It is easy to reflect this if you separate the operators into classes. You only need to specify how many elements does the operator need.