Stack: Infix to Postfix Expression

package additional_problems.stack;

/**
 * Rules for infix to postfix conversion:
 * 1. print operands as they arrived
 * 2. If the stack is empty or contains a left parenthesis on the top, push incoming operator onto stack
 * 3. If incoming operator is '(', push it into stack
 * 4. If incoming operator is ')', pop the stack elements till left parenthesis is found
 * 5. If incoming operator has higher precedence than the operator at the top of the stack, push it on the stack
 * 6. 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.
 * 7. 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 pop and print top of the stack and then push the incoming operator
 *      ii. associativity R->L then push the incoming operator
 * 8. At the end of the stack pop and print all the operators
 *
 *
 * Created by aarushi on 6/7/21.
 */
public class P02InfixToPostfix {

    //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;
    }

    //method that converts infix to postfix expression
    public static void infixToPostfix(String string){
        CharStack stack= new CharStack(string.length());
        for(int i=0; i<string.length(); i++) {
            char c = string.charAt(i);

            //1. print operands as they arrived
            if ((c >= '0' && c <= '9') || (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')) {
                System.out.print(c);
            }

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

            //4. If incoming operator is ')', pop the stack elements till left parenthesis is found
            else if (c == ')') {
                while (stack.peek() != '(') {
                    System.out.print(stack.pop());
                }
                stack.pop();
            }

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

            //6. 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.
            //7. If incoming operator has the same precedence as the top of the stack use the associativity rule
            else if(getPrecedence(stack.peek())>getPrecedence(c) || getPrecedence(stack.peek())==getPrecedence(c)){
                while(getPrecedence(stack.peek())>getPrecedence(c) || getPrecedence(stack.peek())==getPrecedence(c)){
                    System.out.print(stack.pop());
                }
                stack.push(c);
            }
        }

        //8. At the end of the stack pop and print all the operators
        if(!stack.isEmpty()){
            while (!stack.isEmpty()){
                System.out.print(stack.pop());
            }
        }
    }

    public static void main(String [] args){
        infixToPostfix("a+b*(c^d-e)^(f+g*h)-i");
    }
}