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));
}
}
loadDefaultBinaryOperators()
maybe with astatic
block; So thatRPNIntegerCalculator()
will work once created. \$\endgroup\$