package leetcode;

import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * https://leetcode.com/problems/basic-calculator-ii/
 */
public class Problem227 {
    public int calculate(String s) {
        Map<Character, Integer> precendenceMap = new HashMap<>();
        precendenceMap.put('/', 2);
        precendenceMap.put('*', 2);
        precendenceMap.put('-', 1);
        precendenceMap.put('+', 1);
        String str = s.replaceAll("\\s+", "");
        Stack<Long> operands = new Stack<>();
        Stack<Character> operators = new Stack<>();
        String num = "";
        for (char c : str.toCharArray()) {
            if (Character.isDigit(c)) {
                num += c;
            } else if (c == '+' || c == '-' || c == '*' || c == '/') {
                if (!num.isEmpty()) {
                    operands.add(Long.parseLong(num));
                    num = "";
                }
                if (!operators.isEmpty()) {
                    int peekPrecedence = precendenceMap.get(operators.peek());
                    int predence = precendenceMap.get(c);
                    if (peekPrecedence >= predence) {
                        evaluate(operands, operators);
                    }
                }
                if (c == '+' || c == '-') {
                    while (!operators.isEmpty()) {
                        evaluate(operands, operators);
                    }
                }
                operators.add(c);
            }
        }
        if (!num.isEmpty()) {
            operands.add(Long.parseLong(num));
            num = "";
        }
        if (!operators.isEmpty()) {
            evaluate(operands, operators);
        }
        // evaluate from left to right
        Collections.reverse(operands);
        Collections.reverse(operators);
        while (!operators.isEmpty()) {
            evaluateLeftToRight(operands, operators);
        }
        return (int) operands.pop().longValue();
    }
    
    private void evaluate(Stack<Long> operands, Stack<Character> operators) {
        char op = operators.pop();
        long a = operands.pop();
        long b = operands.pop();
        long val = evaluate(b, a, op);
        operands.add(val);
    }
    
    private void evaluateLeftToRight(Stack<Long> operands, Stack<Character> operators) {
        char op = operators.pop();
        long a = operands.pop();
        long b = operands.pop();
        long val = evaluate(a, b, op);
        operands.add(val);
    }
    
    private long evaluate(long a, long b, char op) {
        if (op == '+') {
            return a + b;
        } else if (op == '-') {
            return a - b;
        } else if (op == '*') {
            return a * b;
        } else { // op == /
            return a / b;
        }
    }
    
    public static void main(String[] args) {
        Problem227 prob = new Problem227();
        System.out.println(prob.calculate("3+2*2")); // 7
        System.out.println(prob.calculate(" 3/2 ")); // 1
        System.out.println(prob.calculate(" 3+5 / 2 ")); // 5
        System.out.println(prob.calculate("1*4+5+2-3/6*8")); // 11
        System.out.println(prob.calculate("0-2147483648")); // -2147483648
        System.out.println(prob.calculate("530+194/2/2*3/25*2/5*6/5*8-22/2*2*4+24*11+120/6/2/2*13*62")); // 4752
        System.out.println(prob.calculate("1-1+1")); // 1
        System.out.println(prob.calculate("14/3*2")); // 8
        System.out.println(prob.calculate("1*2-3/4+5*6-7*8+9/10")); // -24
        System.out.println(prob.calculate("282-1*2*13-30-2*2*2/2-95/5*2+55+804+3024")); // 4067
        System.out.println(prob.calculate("1-95/5*2+3")); // -34
    }
}

@@ -2815,892 +2815,6 @@
   %7D%0A
-    %0A    public static void main(String%5B%5D args) %7B%0A        Problem227 prob = new Problem227();%0A        System.out.println(prob.calculate(%223+2*2%22)); // 7%0A        System.out.println(prob.calculate(%22 3/2 %22)); // 1%0A        System.out.println(prob.calculate(%22 3+5 / 2 %22)); // 5%0A        System.out.println(prob.calculate(%221*4+5+2-3/6*8%22)); // 11%0A        System.out.println(prob.calculate(%220-2147483648%22)); // -2147483648%0A        System.out.println(prob.calculate(%22530+194/2/2*3/25*2/5*6/5*8-22/2*2*4+24*11+120/6/2/2*13*62%22)); // 4752%0A        System.out.println(prob.calculate(%221-1+1%22)); // 1%0A        System.out.println(prob.calculate(%2214/3*2%22)); // 8%0A        System.out.println(prob.calculate(%221*2-3/4+5*6-7*8+9/10%22)); // -24%0A        System.out.println(prob.calculate(%22282-1*2*13-30-2*2*2/2-95/5*2+55+804+3024%22)); // 4067%0A        System.out.println(prob.calculate(%221-95/5*2+3%22)); // -34%0A    %7D%0A
 %7D%0A

Update problem 227 solution