/**
 * Infix to RPN translator.
 * @author Jeff Raab
 */
public class InfixToRPNSolution implements IInfixToRPN {

    /** Stack used to hold operators in translation. */
    private IStack operators = StacksAndQueuesFactory.createStack();

    /** Constructs a new translator. */
    public InfixToRPNSolution() {}
    
    /** 
     * Returns the RPN representation of the 
     * given infix notation expression.
     * @param anInfix expression in infix to translate
     */
    public String translate(String anInfix) {
        if (anInfix.length() == 0) {
            return "";
        }
    
        String postfix = "";
    
        char[] chars = anInfix.toCharArray();
        
        char c;
        boolean firstDigit = true;
        for (int i = 0; i < chars.length; i++) {
            c = chars[i];
        
            if (Character.isDigit(c)) {
                if (firstDigit) {
                    postfix += ",";
                    firstDigit = false;
                }

                postfix += c;
                
                continue;
            }
            
            if (isOperator(c)) {
                while (!operators.isEmpty() && 
                       higherOrEqualPrecedence(
                            ((Character)operators.top()).charValue(), c))
                {
                    postfix += "," + operators.pop();
                }
                
                operators.push(new Character(c));
            }
            
            else if (c == '(') {
                operators.push(new Character(c));
            }
            
            else if (c == ')') {
                char op = ((Character)operators.pop()).charValue();

                while (op != '(') {
                    postfix += "," + op;
                    
                    op = ((Character)operators.pop()).charValue();
                }
            }
            
            firstDigit = true;
        }
        
        while (!operators.isEmpty()) {
            postfix += "," + operators.pop();
        }
        
        return postfix.substring(1);
    }

    /** Returns whether or not the given char is an operator. */
    private boolean isOperator(char c) {
        switch (c) {
            case '+':   case '-':
            case '*':   case '/':
                return true;
            default:
                return false;
        }
    }
    
    /** 
     * Returns whether or not the first char represents an operator
     * of higher or equal precedence to the second char.
     */
    private boolean higherOrEqualPrecedence(char c1, char c2) {
        int p1 = 0, p2 = 0;
        
        switch (c1) {
            case '+': case '-':
                p1 = 1;
                break;
            case '*': case '/':
                p1 = 2;
        } 

        switch (c2) {
            case '+': case '-':
                p2 = 1;
                break;
            case '*': case '/':
                p2 = 2;
        }
        
        return p1 >= p2;
    }
}