OO design of Reverse Polish Notation Calculator

Question

This solution focuses on the design of classes, not the actual push and pop stack part. I will include that part of the code as well. The current code has 2 operators (plus and minus).

If we add another subclass under Token, is there a way that we don't need to check in processInput() what each operator is and perform the right calculation?

I didn't know how to answer that question. I looked into Java Reflection, but still don't know how reflection can help me in this case. Can anyone shed some light on how I can make this design better?

I want to allow people to add new operators, multiply and divide, and maybe make their own definition for special operators.

This application will take input string like "1 2 + 1 -" and output 2 because "1 2 + 1 -" is the reverse Polish notation for (1+2)-1 = 2.

import java.util.*;
public class RPNCalculator {
    public static Stack<Integer> stack;
    //assume this string has integers and legal operators +,- and deliminated by space
    // an example would be "12 2 + 1 -" 
    private static String input;
    static String operators ="+-";

    public RPNCalculator(String userInput){
        input = userInput;
        stack = new Stack<Integer>();
    }

    public void processInput(){
        StringTokenizer st = new StringTokenizer(input, " ");
        while (st.hasMoreTokens()){
            String str = st.nextToken();
            if(!operators.contains(str)){
                stack.push(Integer.parseInt(str));
            }
            else{
                if(str.equals("+")){
                    Plus obj = new Plus();
                    obj.calc();
                }
                else if(str.equals("-")){
                    Minus obj2 = new Minus();
                    obj2.calc();
                }
            }
        }
        System.out.println(stack.pop());
    }
}

public abstract class Token {
    abstract void calc();
}
public class Minus extends Token {

    @Override
    void calc() {
        int a = RPNCalculator.stack.pop();
        int b = RPNCalculator.stack.pop();
        RPNCalculator.stack.push(b-a);

    }

}

public class Plus extends Token {

    @Override
    void calc() {
        int a = RPNCalculator.stack.pop();
        int b = RPNCalculator.stack.pop();
        RPNCalculator.stack.push(a+b);
    }

}
public class RPNDriver {
       public static void main(String[] args) {
           System.out.println("starting calculator...");
           RPNCalculator rpn = new RPNCalculator("1 2 +");
           rpn.processInput();
       }
}

Answer 1

You can add more flexibility by storing a mapping from a String to a Token in a Map. After populating the map, you'll just need to look up for the token in it instead of writing a a long sequence of if-else blocks.

That is, you can define and populate it like this:

Map<String, Token> operators = new HashMap<>();
operators.add("+", new Plus());
// other operators go here

and then use it like this: operators.get(str).calc()

This way, you just need to define a new subclass of the Token and add its instance to the operators map to define a new operator.

You can make the code even more flexible by passing this map as a parameter to the processInput method to decouple reading the input from the computations (this way, a client will be able to define his own subclass of the Token and pass it to this method).

I'd also rename the Token. Operator or Operation seems more appropriate to me (because a number is also a token, so this name is more precise).

There's also no point in having static members in the RPNCalculator class. It makes it non-reusable and might create a bunch of issues in a multithreaded environment. I'd suggest to make all members non-static and encapsulate them properly (and pass a reference to an instance of this class to the constructor of the concrete Token subclasses).

You can also decouple the operators from the calculator completely by changing the signature of the calc method to public int calc(int a, int b) (it might be an issue for non-binary operators, though).

You can improve your code by handling the errors more carefully. For instance, if the number of tokens on the stack is more than one in the end of the evaluation, your code will return some value, but it should be an error ("1 2" is not a valid expression, is it?). You can check such cases and throw an appropriate exception.