Stack: Infix to prefix expression

package additional_problems.stack;

/**
 * Rules for infix to prefix conversion:
 * 1. Reverse the expression
 * 2. Print operands as they arrived
 * 3. If the stack is empty or contains ')' on the top, push incoming operator onto stack
 * 4. If incoming operator is '(', pop the stack elements till ')' is found
 * 5. If incoming operator is ')', push it into stack
 * 6. If incoming operator has higher precedence than the operator at the top of the stack, push it on the stack
 * 7. If incoming operator has lower precedence than the top of the stack, pop and print the top of the stack, Then test the
 *    incoming operator with the top of the stack.
 * 8. If incoming operator has the same precedence as the top of the stack use the associativity rule
 *      i. associativity L->R (i.e *and/ or +and-) then push the incoming operator into stack
 *      ii. associativity R->L then push the incoming operator
 * 9. At the end of the stack pop and print all the operators
 * 10. Reverse the end result
 *
 */

public class P03InfixToPrefix {

    //method that returns the precedence of operators
    //the higher precedence operators would return a higher value
    public static int getPrecedence(char operator){
        if (operator=='+' || operator=='-'){
            return 1;
        } else if (operator=='*' || operator=='/'){
            return 2;
        } else if (operator=='^'){
            return 3;
        }
        return -1;
    }

    public static String reverseString(String string){
        StringBuffer reversedString= new StringBuffer("");
        for (int i = string.length()-1; i >=0; i--) {
            reversedString.append(string.charAt(i));
        }
        return reversedString.toString();
    }

    public static String infixToPostfix(String expression){
        CharStack stack= new CharStack(expression.length());
        //1. Reverse the expression
        String reversedExpression= reverseString(expression);
        StringBuffer result= new StringBuffer("");

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

            //2. Print operands as they arrived
            if ((c >= '0' && c <= '9') || (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')) {
                result.append(c);
            }

           //3. If the stack is empty or contains ')' on the top, push incoming operator onto stack
           else if(stack.peek()==')' || stack.isEmpty()){
                stack.push(c);
            }

            //4. If incoming operator is '(', pop the stack elements till ')' is found
           else if(c=='('){
                while (stack.peek()!=')'){
                    result.append(stack.pop());
                }
                stack.pop();
            }

            //5. If incoming operator is ')', push it into stack
           else if(c==')'){
                stack.push(c);
            }

            //6. If incoming operator has higher precedence than the operator at the top of the stack, push it on the stack
            else if(getPrecedence(c)>getPrecedence(stack.peek())){
                stack.push(c);
            }

            //7. If incoming operator has lower precedence than the top of the stack, pop and print the top of the stack,
            // then test the incoming operator with the top of the stack.
            else if(getPrecedence(c)<getPrecedence(stack.peek())){
                while(getPrecedence(c)<getPrecedence(stack.peek())){
                    result.append(stack.pop());
                }
                stack.push(c);
            }

            //8. If incoming operator has the same precedence as the top of the stack use the associativity rule
            //        i. associativity L->R (i.e *and/ or +and-) then push the incoming operator into stack
            //       ii. associativity R->L then push the incoming operator
            else if(getPrecedence(c)==getPrecedence(stack.peek())){
                stack.push(c);
            }

        }

        //9. At the end of the stack pop and print all the operators
        if(!stack.isEmpty()){
            while (!stack.isEmpty()){
                result.append(stack.pop());
            }
        }

        //10. Reverse the end result
        return reverseString(result.toString());
    }

    public static void main(String [] args){
        System.out.println(infixToPostfix("A*B+C/D"));
    }

}