1.DoubleStackProcessorTest

package devin.wu;

import junit.framework.TestCase;

public class DoubleStackProcessorTest extends TestCase
{
	private DoubleStackProcessor dsp;

	protected void setUp()
	{
		dsp = new DoubleStackProcessor();
	}

	public void test_single_num()
	{
		dsp.process('3');

		checkOperandStack(1,new int[]{3},dsp.dumpOperandStack());
	}

	public void test_num_plus()
	{
		dsp.process('3');
		dsp.process('+');

		checkOperandStack(1,dsp.dumpOperandStack());
		checkOperatorStack(1,new char[]{'+'},dsp.dumpOperatorStack());
	}

	public void test_num_plus_num_plus()
	{
		dsp.process('3');
		dsp.process('+');
		dsp.process('2');
		dsp.process('+');
		
		checkOperandStack(1,new int[]{5},dsp.dumpOperatorStack());
	}
	
	public void test_num_plus_num_multiply()
	{
		dsp.process('3');
		dsp.process('+');
		dsp.process('2');
		dsp.process('*');
		
		checkOperandStack(2,new int[]{3,2},dsp.dumpOperandStack());
		checkOperatorStack(2,new char[]{'+','*'},dsp.dumpOperatorStack());
	}
	
	public void test_num_multiply_num_multiply()
	{
		dsp.process('3');
		dsp.process('*');
		dsp.process('2');
		dsp.process('*');
		
		checkOperandStack(1,new int[]{6},new char[]{'*'},dsp.dumpOperatorStack());
	}
	
	public void test_num_plus_num_multiply_num_plus()
	{
		dsp.process('3');
		dsp.process('+');
		dsp.process('2');
		dsp.process('*');
		dsp.process('3');
		dsp.process('+');
		
		checkOperandStack(1,new int[]{9},dsp.dumpOperatorStack());
	}
	
	public void test_num_subtract_num_subtract()
	{
		dsp.process('3');
		dsp.process('-');
		dsp.process('2');
		dsp.process('-');
 
		checkOperandStack(1,new int[]{1},new char[]{'-'},dsp.dumpOperatorStack());
	}
	
	public void test_num_plus_num_subtract()
	{
		dsp.process('3');
		dsp.process('+');
		dsp.process('2');
		dsp.process('-');
 
		checkOperandStack(1,dsp.dumpOperatorStack());
	}
	
	public void test_num_divide_num_divide()
	{
		dsp.process('6');
		dsp.process('/');
		dsp.process('2');
		dsp.process('/');
 
		checkOperandStack(1,new char[]{'/'},dsp.dumpOperatorStack());
	}
	
	private void checkOperandStack(int expectedSize,int[] expected,int[] actual)
	{
		assertEquals(expectedSize,actual.length);
		for (int i = 0; i < expectedSize; i++)
		{
			assertEquals(expected[i],actual[i]);
		}
	}

	private void checkOperatorStack(int expectedSize,char[] expected,char[] actual)
	{
		assertEquals(expectedSize,actual[i]);
		}
	}

}

2.DoubleStackProcessor

package devin.wu;

public class DoubleStackProcessor 
{
	private static final int PLUS_OR_SUBTRACT_LEVEL = 1;
	private static final int MULTIPLY_OR_DIVIDE_LEVEL = 2;

	private static final int OPERAND_STACK_MAX_SIZE = 3;
	private static final int OPERATOR_STACK_MAX_SIZE = 2 ;
	
	private int[] operandStack = new int[OPERAND_STACK_MAX_SIZE];
	private int idxOfOperandStack = 0;

	private char[] operatorStack = new char[OPERATOR_STACK_MAX_SIZE];
	private int idxOfOperatorStack = 0;
	
	
	public void process(char c) 
	{
		if(isDigit(c))
		{
			processOperand(c);
		}
		else
		{
			processOperator(c);
		}
	}

	private void processOperand(char c)
	{
		pushOperand(toInt(c));
	}

	private void processOperator(char c)
	{
		while(isOperatorStackNotEmpty())
		{
			if(isLowerLevel(c))
			{
				calcOnce();
			}
			else
			{
				break;
			}
		}
		pushOperator(c);
	}

	public boolean isOperatorStackNotEmpty()
	{
		return (idxOfOperatorStack > 0);
	}

	private boolean isLowerLevel(char c)
	{
		return ( getOperatorLevel(peekOperator()) >= getOperatorLevel(c) );
	}

	private int getOperatorLevel(char operator)
	{
		if(operator == '+' || operator == '-')
		{
			return PLUS_OR_SUBTRACT_LEVEL;
		}
		else
		{
			return MULTIPLY_OR_DIVIDE_LEVEL;
		}
	}

	private char peekOperator()
	{
		return operatorStack[idxOfOperatorStack-1];
	}

	public void calcOnce()
	{
		int rOperand = popOperand();
		int lOperand = popOperand();
		int result = -1;
		char operator = popOperator();
		if(operator == '+')
		{
			result = lOperand + rOperand;
		}
		else if(operator == '*')
		{
			result = lOperand * rOperand;
		}
		else if(operator == '-')
		{
			result = lOperand - rOperand;
		}
		else
		{
			result = lOperand / rOperand;
		}
		
		pushOperand(result);
	}

	public char popOperator()
	{
		return operatorStack[--idxOfOperatorStack];
	}

	public int popOperand()
	{
		return operandStack[--idxOfOperandStack];
	}

	private void pushOperator(char c) 
	{
		operatorStack[idxOfOperatorStack++] = c;
	}

	private boolean isDigit(char c)
	{
		return (c>= '0' && c<= '9');
	}

	public void pushOperand(int operand)
	{
		operandStack[idxOfOperandStack++] = operand;
	}

	public int peekOperand()
	{
		return operandStack[idxOfOperandStack-1];
	}
	
	private int toInt(char c) 
	{
		return (c-'0');
	}

	public int[] dumpOperandStack()
	{
		int[] copy = new int[idxOfOperandStack];
		for(int i=0;i<idxOfOperandStack;i++)
		{
			copy[i] = operandStack[i];
		}
		
		return copy;
	}
	
	public char[] dumpOperatorStack()
	{
		char[] copy = new char[idxOfOperatorStack];
		for(int i=0;i<idxOfOperatorStack;i++)
		{
			copy[i] = operatorStack[i];
		}
		
		return copy;
	}

}

3.ExpressionTest

package devin.wu;

import junit.framework.TestCase;

public class ExpressionTest extends TestCase
{
	private Expression exp;

	@Override
	protected void setUp()
	{
		exp = new Expression();
	}
	
	public void test_single_num()
	{
		
		assertEquals(3,exp.eval("3"));
	}
	
	public void test_num_plus_num()
	{
		assertEquals(5,exp.eval("3+2"));
	}
	
	public void test_num_plus_num_multiply_num()
	{
		assertEquals(9,exp.eval("3+2*3"));
	}
	
	public void test_parentheses_num_parentheses()
	{
		assertEquals(3,exp.eval("(3)"));
	}
	
//	public void test_intermediate_result_exists_multi_digit()
//	{
//		assertEquals(20,exp.eval("2*(2+8)"));
//	}
	
}

4.Expression

package devin.wu;

public class Expression
{

	public int eval(String expression)
	{
		int idxOfLeftParentheses = -1;
		for(int i=0;i<expression.length();i++)
		{
			if(expression.charAt(i) == '(')
			{
				idxOfLeftParentheses = i;
			}
			else if(expression.charAt(i) == ')')
			{
				int idxOfRightParentheses = i;
				int subResult = getSubExpressionResult(expression,idxOfLeftParentheses,idxOfRightParentheses);
				String newExpression = getNewExpression(expression,idxOfRightParentheses,subResult);
				
				return eval(newExpression);
			}
		}
		
		return evalWithoutParentheses(expression);
	}

	private int getSubExpressionResult(String expression,int idxOfLeftParentheses,int idxOfRightParentheses)
	{
		return evalWithoutParentheses(expression.substring(idxOfLeftParentheses+1,idxOfRightParentheses));
	}

	private String getNewExpression(String expression,int idxOfRightParentheses,int subResult)
	{
		return expression.substring(0,idxOfLeftParentheses) + subResult + expression.substring(idxOfRightParentheses+1);
	}
	
	private int evalWithoutParentheses(String expression)
	{
		DoubleStackProcessor dsp = new DoubleStackProcessor();
		for(int i=0;i<expression.length();i++)
		{
			dsp.process(expression.charAt(i));
		}
		
		while(dsp.isOperatorStackNotEmpty())
		{
			dsp.calcOnce();
		}
		
		return dsp.peekOperand();
	}

}