package leetcode;

import java.util.Collections;
import java.util.Stack;

/**
 * https://leetcode.com/problems/basic-calculator-ii/
 */
public class Problem227 {
    public int calculate(String s) {
        String expr = s.replaceAll("\\s", "");
        Stack<Character> operators = new Stack<>();
        Stack<Long> operands = new Stack<>();
        String num = "";
        for (int i = 0; i < expr.length(); i++) {
            char c = expr.charAt(i);
            if (Character.isDigit(c)) {
                num += c;
            } else { // the operator
                operands.add(Long.valueOf(num));
                if (!operators.isEmpty()) {
                    char op = operators.peek();
                    if (op == '*' || op == '/') {
                        long a = operands.pop();
                        long b = operands.pop();
                        op = operators.pop();
                        operands.add(evaluate(b, a, op));
                    }
                }
                operators.add(c);
                num = "";
            }
        }
        if (!num.isEmpty()) {
            operands.add(Long.valueOf(num));
        }
        if (!operators.isEmpty()) {
            char op = operators.peek();
            if (op == '*' || op == '/') {
                long a = operands.pop();
                long b = operands.pop();
                op = operators.pop();
                operands.add(evaluate(b, a, op));
            }
        }
        // Evaluate from left to right.
        Collections.reverse(operands);
        Collections.reverse(operators);
        while (!operators.isEmpty()) {
            long a = operands.pop();
            long b = operands.pop();
            char op = operators.pop();
            operands.add(evaluate(a, b, op));
        }
        return operands.pop().intValue();
    }

    private static long evaluate(long a, long b, char op) {
        if (op == '*') {
            return a * b;
        }
        if (op == '/') {
            return a / b;
        }
        if (op == '+') {
            return a + b;
        }
        return a - b; // op == '-'
    }
}

@@ -33,43 +33,18 @@
 til.
-Collections;%0Aimport java.util.Stack
+ArrayDeque
 ;%0A%0A/
@@ -222,21 +222,26 @@
         
-Stack
+ArrayDeque
 %3CCharact
@@ -252,37 +252,42 @@
 operators = new 
-Stack
+ArrayDeque
 %3C%3E();%0A        St
@@ -284,21 +284,26 @@
         
-Stack
+ArrayDeque
 %3CLong%3E o
@@ -320,13 +320,18 @@
 new 
-Stack
+ArrayDeque
 %3C%3E()
@@ -567,32 +567,36 @@
     operands.add
+Last
 (Long.valueOf(nu
@@ -680,32 +680,36 @@
 = operators.peek
+Last
 ();%0A            
@@ -780,35 +780,42 @@
 ng a = operands.
-pop
+removeLast
 ();%0A            
@@ -836,35 +836,42 @@
 ng b = operands.
-pop
+removeLast
 ();%0A            
@@ -889,35 +889,42 @@
  op = operators.
-pop
+removeLast
 ();%0A            
@@ -939,32 +939,36 @@
     operands.add
+Last
 (evaluate(b, a, 
@@ -1042,16 +1042,20 @@
 tors.add
+Last
 (c);%0A   
@@ -1155,16 +1155,20 @@
 ands.add
+Last
 (Long.va
@@ -1262,16 +1262,20 @@
 ors.peek
+Last
 ();%0A    
@@ -1338,35 +1338,42 @@
 ng a = operands.
-pop
+removeLast
 ();%0A            
@@ -1386,35 +1386,42 @@
 ng b = operands.
-pop
+removeLast
 ();%0A            
@@ -1431,35 +1431,42 @@
  op = operators.
-pop
+removeLast
 ();%0A            
@@ -1473,32 +1473,36 @@
     operands.add
+Last
 (evaluate(b, a, 
@@ -1575,87 +1575,8 @@
 ht.%0A
-        Collections.reverse(operands);%0A        Collections.reverse(operators);%0A
     
@@ -1632,35 +1632,43 @@
 ng a = operands.
-pop
+removeFirst
 ();%0A            
@@ -1685,19 +1685,27 @@
 perands.
-pop
+removeFirst
 ();%0A    
@@ -1732,19 +1732,27 @@
 erators.
-pop
+removeFirst
 ();%0A    
@@ -1771,16 +1771,21 @@
 ands.add
+First
 (evaluat
@@ -1836,11 +1836,18 @@
 nds.
-pop
+removeLast
 ().i

Update problem 227