calculator

import java.util.*;

import static java.lang.Double.NaN;
import static java.lang.Double.valueOf;
import static java.lang.Math.incrementExact;
import static java.lang.Math.pow;


/*
 *   A calculator for rather simple arithmetic expressions
 *
 *   This is not the program, it's a class declaration (with methods) in it's
 *   own file (which must be named Calculator.java)
 *
 *   NOTE:
 *   - No negative numbers implemented
 */
public class Calculator {

    // Here are the only allowed instance variables!
    // Error messages (more on static later)
    final static String MISSING_OPERAND = "Missing or bad operand";
    final static String DIV_BY_ZERO = "Division with 0";
    final static String MISSING_OPERATOR = "Missing operator or parenthesis";
    final static String OP_NOT_FOUND = "Operator not found";

    // Definition of operators
    final static String OPERATORS = "+-*/^";

    // Method used in REPL
    double eval(String expr) {
        if (expr.length() == 0) {
            return NaN;
        }
        List<String> tokens = tokenize(expr);
        List<String> postfix = infix2Postfix(tokens);
        return evalPostfix(postfix);
    }

    // ------  Evaluate RPN expression -------------------

    double evalPostfix(List<String> postfix) {
        Deque<String> stack = new ArrayDeque<String>();
        List<String> results = new ArrayList<String>();
        double a,b;
        // If there's just one value, it gets returned.
        if (postfix.size() == 1){
            return valueOf(postfix.get(0));
        }
        for (int i = 0; i < postfix.size() ; i++) {
            // If the current index isn't an operator,
            // it gets added to the queue.
            if(!isOperator(postfix.get(i))){
                stack.push(postfix.get(i));
            }
            // If it is an operator, then it calculates
            // all the numbers before in the queue using the
            // current operator.
            else{
                a = Double.valueOf(stack.pop());
                b = Double.valueOf(stack.pop());
                stack.push(applyOperator(postfix.get(i), a, b)+"");
            }
        }
        return Double.valueOf(stack.pop());
    }

    // Checks if the current String contains an operator.
    boolean isOperator(String s){
        String[] operators = {"+","-", "*", "/", "^", "(", ")"};
        for (String operator : operators) {
            if (operator.contains(s)) {
                return true;
            }
        }
        return false;
    }

    double applyOperator(String op, double d1, double d2) {
        switch (op) {
            case "+":
                return d1 + d2;
            case "-":
                return d2 - d1;
            case "*":
                return d1 * d2;
            case "/":
                if (d1 == 0) {
                    throw new IllegalArgumentException(DIV_BY_ZERO);
                }
                return d2 / d1;
            case "^":
                return pow(d2, d1);
        }
        throw new RuntimeException(OP_NOT_FOUND);
    }

    // ------- Infix 2 Postfix ------------------------

    List<String> infix2Postfix(List<String> infix) {
        List<String> postFix = new ArrayList<String>();
        Deque<String> que = new ArrayDeque<String>();
        boolean latestBracket = false;
        for (String s : infix) {

            // Checks if the current index is an operator
            // , if it isnt an operator, it adds it to
            // postFix.
            if (isOperator(s)) {

                // Checks if the latest operator added to queue is
                // an opening bracket
                if (!que.isEmpty() && !que.peek().contains("(")) {
                    latestBracket = false;
                } else if (!que.isEmpty()) {
                    latestBracket = true;
                }

                // Code for brackets.
                // If the latest operator was an opening bracket and
                // the current operator isnt a bracket, it will be
                // added to the queue.
                if (latestBracket && !s.contains("(") && !s.contains(")")) {
                    que.push(s);
                    latestBracket = false;
                }
                // If the current operator is a open bracket
                // it will be added to the queue.
                else if (s.contains("(")) {
                    que.push(s);
                    latestBracket = true;
                }
                // If the current operator is a closing bracket
                // all operators will be popped until a closing
                // bracket is the next in que. It will be popped
                // but not put anywhere. The for loop the breaks.
                else if (s.contains(")")) {
                    int stackSize = que.size();
                    for (int k = 0; k < stackSize; k++) {
                        if (!que.peek().contains("(")) {
                            postFix.add(que.pop());
                        } else {
                            que.pop();
                            break;
                        }
                    }
                }
                // Code for non-bracket operators.
                else {
                    // If the queue is empty the new operator will simply be
                    // put in the queue.
                    if (que.isEmpty()) {
                        que.push(s);
                    }
                    // If the top of the queue has higher precedence than the
                    // current operator to be added, then it will be popped
                    // and the new operator will be added. However if there are
                    // more than one operator with higher precedence
                    // all of those will be popped as well.
                    else if (getPrecedence(que.peek()) > getPrecedence(s)) {
                        postFix.add(que.pop());
                        while (true) {
                            if (!que.isEmpty() && getPrecedence(que.peek()) > getPrecedence(s)) {
                                postFix.add(que.pop());
                            } else break;
                        }
                        que.push(s);
                    }
                    // If both the top of the queue and the operator to be added has the
                    // same precedence, then the code checks the associativity. If the
                    // new operator has left association then the old operator will
                    // be popped. In both cases the new one gets pushed in to the queue.
                    else if (getPrecedence(que.peek()) == getPrecedence(s)) {
                        if (getAssociativity(s) == Assoc.LEFT) {
                            postFix.add(que.pop());
                        }
                        que.push(s);
                    }
                    // If the new operator has higher precedence then it gets pushed to
                    // the top of the queue.
                    else if (getPrecedence(que.peek()) < getPrecedence(s)) {
                        que.push(s);
                    }

                }
            } else postFix.add(s);
        }
        // If there are any operators left in queue they will be added
        // to the end of the postFix list.
        while(!que.isEmpty()){
            postFix.add(que.pop());
        }
        System.out.println(postFix.toString());
        return postFix;
    }

    int getPrecedence(String op) {
        if ("+-".contains(op)) {
            return 2;
        } else if ("*/".contains(op)) {
            return 3;
        } else if ("^".contains(op)) {
            return 4;
        } else {
            throw new RuntimeException(OP_NOT_FOUND);
        }
    }

    Assoc getAssociativity(String op) {
        if ("+-*/".contains(op)) {
            return Assoc.LEFT;
        } else if ("^".contains(op)) {
            return Assoc.RIGHT;
        } else {
            throw new RuntimeException(OP_NOT_FOUND);
        }
    }

    enum Assoc {
        LEFT,
        RIGHT
    }

    // ---------- Tokenize -----------------------

    // List String (not char) because numbers (with many chars)
    // Using a StringTokenizer on the String we can split
    // up the String and still keep the delimiters. Using simple
    // regex we tell it where to split. We then add it to the list
    // that then gets returned.
    List<String> tokenize(String expr) {
       // TODO
        List<String> tokens = new ArrayList<String>();
        StringTokenizer test = new StringTokenizer(expr,"[\\+\\-*/\\^ ()]+", true );
        while(test.hasMoreTokens()){
            tokens.add(test.nextToken());
        }
        // If the list has any empty indexes, they get removed.
        for (int i = 0; i < tokens.size(); i++) {
            if (tokens.get(i).contains(" ")){
                tokens.remove(i);
                i = 0;
            }
        }
        return tokens;
    }
}