Arithmetic Expression Calculator

I wrote the following code using TDD (Test-Driven Development). I made a significant effort to start with simple tests and simple implementations and to proceed with the design as I felt was appropriate to add each additional piece of functionality. I also paid attention to the number of methods per class and line count for each method. In particular, I tried very hard to make each method no longer than 6 lines of code (not including braces and blank lines). As duplicate logic was introduced and methods became too long or stopped making sense in a given context, the code was broken up and extracted to new methods and classes: This process of constantly massaging the code is called refactoring.

Approximate Development Time: 4-6 hours 

package com.vladimirlevin.calc;

import junit.framework.TestCase;

public class TestCalculator extends TestCase {
    public void testAdd() {
        Calculator calc = new Calculator();
        String result = calc.eval("1 + 1");
        assertEquals("2", result);
    }

    public void testAddWithNoWhitespace() {
        Calculator calc = new Calculator();
        String result = calc.eval("1+1");
        assertEquals("2", result);
    }

    public void testSubtract() {
        Calculator calc = new Calculator();
        String result = calc.eval("5 - 2");
        assertEquals("3", result);
    }

    public void testMultiply() {
        Calculator calc = new Calculator();
        String result = calc.eval("16 * 2");
        assertEquals("32", result);
    }

    public void testDivide() {
        Calculator calc = new Calculator();
        String result = calc.eval("9 / 3");
        assertEquals("3", result);
    }

    public void testSimpleExpression() {
        Calculator calc = new Calculator();
        String result = calc.eval("9 + 3 - 7");
        assertEquals("5", result);
    }

    public void testOperatorPrecedence() {
        Calculator calc = new Calculator();
        String result = calc.eval("12 + 4 * 9");
        assertEquals("48", result);
    }

    public void testOperatorPrecedenceLongerExpression() {
        Calculator calc = new Calculator();
        String result = calc.eval("12 + 4 * 10 - 6 + 14 / 2");
        assertEquals("53", result);
    }

    public void testParentheses() {
        Calculator calc = new Calculator();
        String result = calc.eval("(10 + 2) / 6");
        assertEquals("2", result);
    }

    public void testParenthesesLongerExpression() {
        Calculator calc = new Calculator();
        String result = calc.eval("((10+2) * 2)/(6-1)");
        assertEquals("4", result);
    }

    public void testParenthesesAroundExpression() {
        Calculator calc = new Calculator();
        String result = calc.eval("(100 + 100)");
        assertEquals("200", result);
    }
}



package com.vladimirlevin.calc;

public class Calculator {
    public String eval(String expr) {
        return new ComplexExpression(expr).eval();
    }
}




package com.vladimirlevin.calc;

import java.util.List;
import java.util.LinkedList;
import java.util.StringTokenizer;

abstract class  Expression {
   protected List tokens = new LinkedList();

    public Expression(String expr) {
        String delimiters = " ()\n\r\t" + Operator.operators();
        StringTokenizer tokenizer = new StringTokenizer(expr, delimiters, true);

        while (tokenizer.hasMoreTokens()) {
            String token = tokenizer.nextToken();
            if (!isWhitespace(token))
                tokens.add(token);
        }
    }

    public Expression(List tokens) {
        this.tokens = tokens;
    }

    public abstract String eval();

    protected void replace(int startIndex, int endIndex, String newValue) {
        tokens.add(startIndex, newValue);

        int itemsToRemove = endIndex - startIndex;
        for (int i=0; i<itemsToRemove; i++)
            tokens.remove(startIndex+1);
    }

    private boolean isWhitespace(String token) {
        return token.equals(" ") || token.equals("\n") || token.equals("\t");
    }
}




package com.vladimirlevin.calc;

import java.util.List;

class SimpleExpression extends Expression {
    public SimpleExpression(String expr) {
        super(expr);
    }

    public SimpleExpression(List tokens) {
        super(tokens);
    }

    public String eval() {
        for (int i=0; i<Operator.operatorsByPrecence.length; i++)
            evaluateOperationsByPriority(Operator.operatorsByPrecence[i]);

        return (String) tokens.get(0);
    }

    private void evaluateOperationsByPriority(List operators) {
        for (int j=0; j<tokens.size(); j++) {
            String token = (String) tokens.get(j);
            if (operators.contains(token)) {
                String value = new Operator(token).calc(
                        (String) tokens.get(j-1), (String) tokens.get(j+1));
                replace(j-1, j+2, value);
                j--;
            }
        }
    }
}




package com.vladimirlevin.calc;

import java.util.List;
import java.util.LinkedList;

class ComplexExpression extends Expression {
    public ComplexExpression(String expr) {
        super(expr);
    }

    public ComplexExpression(List tokens) {
        super(tokens);
    }

    public String eval() {
        while (tokens.size() > 1)
            evaluateInnermostExpression();

        return (String) tokens.get(0);
    }

    private void evaluateInnermostExpression() {
        LinkedList found = new LinkedList();
        int [] delims = findInnermostExpression(found);
        SimpleExpression innermostExpression = new SimpleExpression(found);
        replace(delims[0], delims[1], innermostExpression.eval());
    }

    private int[] findInnermostExpression(List found) {
        int innerLeftParen = 0;
        for (int i=0; i<tokens.size(); i++) {
            if (tokens.get(i).equals("("))
                innerLeftParen = i;

            if (tokens.get(i).equals(")")) {
                found.addAll(tokens.subList(innerLeftParen+1, i));
                return new int[] {innerLeftParen, i+1};
            }
        }

        found.addAll(tokens);
        return new int[] { 0, tokens.size() };
    }
}




package com.vladimirlevin.calc;

import java.util.ArrayList;

class Operator {
    private static final ArrayList highPriorityOperators = new ArrayList();
    private static final ArrayList lowPriorityOperators = new ArrayList();

    public static final ArrayList[] operatorsByPrecence = { highPriorityOperators,
                                                            lowPriorityOperators };
    static {
        highPriorityOperators.add("*");
        highPriorityOperators.add("/");

        lowPriorityOperators.add("+");
        lowPriorityOperators.add("-");
    }

    private String operator;

    public Operator(String operator) {
        this.operator = operator;
    }

    public static String operators() {
        StringBuffer tokens = new StringBuffer();
        for (int i=0; i<operatorsByPrecence.length; i++)
            for (int j=0; j<operatorsByPrecence[i].size(); j++)
                tokens.append(operatorsByPrecence[i].get(j));
        return tokens.toString();
    }

    public String calc (String leftVal, String rightVal) {
        int leftValue = Integer.parseInt(leftVal);
        int rightValue = Integer.parseInt(rightVal);

        if (operator.equals("+"))
            leftValue += rightValue;
        else if (operator.equals("-"))
            leftValue -= rightValue;
        else if (operator.equals("*"))
            leftValue *= rightValue;
        else if (operator.equals("/"))
            leftValue /= rightValue;

        return String.valueOf(leftValue);
    }
}