import java.util.StringTokenizer;

/**
 * IRPNEvaluator solution that uses a stack and a queue
 * to process the tokens of the expression
 * @author Jeff Raab
 */
public class RPNEvaluatorSolution implements IRPNEvaluator {

    /** Queue used to hold parsed tokens. */
    protected IQueue tokens = StacksAndQueuesFactory.createQueue();
    
    /** Stack used to hold operands during evaluation. */
    protected IStack operands = StacksAndQueuesFactory.createStack();
    
    /** Creates a new RPN evaluator. */
    public RPNEvaluatorSolution() {}
    
    /** 
     * Returns the result of evaluating the given RPN expression.
     * @param anExpression expression to evaluate
     */
    public int evaluate(String anExpression) {
        if (anExpression.length() == 0) {
            return 0;
        }
    
        parseExpression(anExpression);
        
        Object token;
        while (!tokens.isEmpty()) {
            token = tokens.dequeue();
            
            if (token instanceof Integer) {
                operands.push(token);
            }
            else {
                IOperator op = (IOperator)token;

                Integer left, right;
                try {
                    right = (Integer)operands.pop();
                    left = (Integer)operands.pop();
                }
                catch (Exception ex) {
                    throw new RuntimeException(
                        "Expression incorrect: " + anExpression);
                }                    

                operands.push(op.apply(left, right));
            }
        }
        
        if (operands.size() != 1) {
            throw new RuntimeException("Expression incorrect:" + anExpression);
        }
        
        Integer result = (Integer)operands.pop();
        return result.intValue();
    }
    
    /** Parses the given expression. */
    private void parseExpression(String anExpression) {
        StringTokenizer t = new StringTokenizer(anExpression, ",", false);
        
        String token;
        while (t.hasMoreTokens()) {
            token = t.nextToken();
            
            if (token.equals("+")) {
                tokens.enqueue(createAdd());
            }
            else if (token.equals("-")) {
                tokens.enqueue(createSubtract());
            }
            else if (token.equals("*")) {
                tokens.enqueue(createMultiply());
            }
            else if (token.equals("/")) {
                tokens.enqueue(createDivide());
            }
            else {
                tokens.enqueue(parseNumber(token));
            }
        }
    }
    
    /** Parses the given number. */
    private Integer parseNumber(String aNumber) {
        int num = 0;

        char c;
        for (int i = 0; i < aNumber.length(); i++) {
            c = aNumber.charAt(i);

            if (c < '0' || c > '9') {
                throw new RuntimeException("Number expected: " + aNumber);
            }
            
            num = num * 10 + (aNumber.charAt(i) - '0');
        }
        
        return new Integer(num);
    }
    
    /** Creates an addition operator. */
    private IOperator createAdd() {
        return new IOperator() {
            public Integer apply(Integer left, Integer right) {
                return new Integer(left.intValue() + right.intValue());
            }
        };
    }

    /** Creates a subtraction operator. */
    private IOperator createSubtract() {
        return new IOperator() {
            public Integer apply(Integer left, Integer right) {
                return new Integer(left.intValue() - right.intValue());
            }
        };
    }

    /** Creates a multiplication operator. */
    private IOperator createMultiply() {
        return new IOperator() {
            public Integer apply(Integer left, Integer right) {
                return new Integer(left.intValue() * right.intValue());
            }
        };
    }

    /** Creates a division operator. */
    private IOperator createDivide() {
        return new IOperator() {
            public Integer apply(Integer left, Integer right) {
                return new Integer(left.intValue() / right.intValue());
            }
        };
    }
}