/**

/**
 * Created by 1000132937 on 3/22/2018.
 */

import java.util.ArrayList;
import java.util.Stack;

public class ToRPN {

    public static ArrayList<String> convertInfix(String[] exprTokens){
        ArrayList<String> infix = new ArrayList<String>();
        Stack<String> operatorStack = new Stack<String>();

        for(String op : exprTokens){
            op = op.trim();
            //if its an operand , simply append to output
            if(!isOperator(op)){
                infix.add(op);
            } else{
                // if it is operator
                //if its a left parenthesis then push it to stack
                if(op.equals("(")){
                    operatorStack.push("(");
                } else if(op.equals(")")){
                    //other wise if it is a right parenthesis then pop the stack untill we see a matching left parenthesis
                    while(!operatorStack.isEmpty() && !operatorStack.peek().equals("(")){
                        infix.add(operatorStack.pop());
                    }

                    //if we do not have a matching left parethesis then it's a malformed expression
                    if(operatorStack.isEmpty() || !operatorStack.peek().equals("(")){
                        return null;
                    }
                    //otherwise we found a matching left. Just pop it out
                    else{
                        operatorStack.pop();
                    }
                } else{
                    //otherwise its an operator
                    //keep poping out element from stack and append in output as long as we see a higher precedence operator
                    //in the top of stack
                    while(
                            !operatorStack.isEmpty()
                                    && (
                                    (isLeftAssociative(op) && getPrecedence(op) <= getPrecedence(operatorStack.peek()))
                                            || (!isLeftAssociative(op) && getPrecedence(op) < getPrecedence(operatorStack.peek()))
                            )
                            ){
                        infix.add(operatorStack.pop());
                    }
                    //ow add the operator
                    operatorStack.push(op);
                }
            }
        }

        //if there are left over element sin stack then append them in the output
        while(!operatorStack.isEmpty()){
            infix.add(operatorStack.pop());
        }

        return infix;
    }

    private static int getPrecedence(String op){
        if(op.equals("+") || op.equals("-")){
            return 2;
        }
        if(op.equals("*") || op.equals("/")){
            return 3;
        }
        if(op.equals("^")){
            return 4;
        }

        return 0;
    }

    private static boolean isLeftAssociative(String op){
        if(op.equals("+") || op.equals("-") || op.equals("*") || op.equals("/")){
            return true;
        }
        if(op.equals("^")){
            return false;
        }

        return false;
    }

    private static boolean isOperator(String op){
        return op.matches("[-+*/^()]");
    }
}