Leetcode: Basic Calculator

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

You may assume that the given expression is always valid.

Some examples:

"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23

Note: Do not use the eval built-in library function.

Understand the problem:
1. If num, push into num stack.
2. If operator: 
    -- If the op stack is empty, push the operator into the stack. 
    -- If the op has higher precedence, e.g. * or /, check the top of the op stack. 
        -- If the top operator on the op stack is a "(", push and move on. 
        -- If the top operator on the op stack has lowe precedence as well, push into the stack. 
        -- If the top operator on the op stack has the same precedence, consume one operation, and then push the op into the op stack. 
    -- If the op has lower percedence, e.g. + or -, check the top of the op stack as well. 
        -- If the top of the op stack is a left parthesis, push the op and move on
        -- Else, Pop one operator and two operands from the two stacks, resp. and push the result back. 
    -- If the op is a left parthesis, push to the op stack and move on. 

    -- If the op is a right parthesis, pop and compuate until we reach a left parthesis.   

Code (Java):

class Solution {
    public int calculate(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        
        s = s.trim();
        s = s.replaceAll("[ ]+", "");
        
        Stack<Integer> numStack = new Stack<>();
        Stack<Character> opStack = new Stack<>();
        
        int ans = 0;
        
        int i = 0;
        while (i < s.length()) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                int num = 0;
                while (i < s.length() && Character.isDigit(s.charAt(i))) {
                    int digit = Character.getNumericValue(s.charAt(i));
                    num = num * 10 + digit;
                    i++;
                }
                numStack.push(num);
            } else {
                if (opStack.isEmpty() || c == '(') {
                    opStack.push(c);
                    i++;
                } else if (c == '*' || c == '/') {
                    if (opStack.peek() == '*' || opStack.peek() == '/') {
                        compute(numStack, opStack);
                    } else {
                        opStack.push(c);
                        i++;
                    }
                } else if (c == '+' || c == '-') {
                    compute(numStack, opStack);
                } else if (c == ')') {
                    while (!opStack.isEmpty() && opStack.peek() != '(') {
                        compute(numStack, opStack);
                    }
                    opStack.pop();
                    i++;
                }
            }
        }
        
        while (!opStack.isEmpty()) {
            compute(numStack, opStack);
        }
        
        return numStack.pop();
    }
    
    private void compute(Stack<Integer> numStack, Stack<Character> opStack) {
        int num2 = numStack.pop();
        int num1 = numStack.pop();
        
        char op = opStack.pop();
        
        int ans = 0;
        
        switch (op) {
            case '+': 
                ans = num1 + num2;
                break;
            case '-' :
                ans = num1 - num2;
                break;
            case '*' :
                ans = num1 * num2;
                break;
            case '/': 
                ans = num1 / num2;
                break;
        }
        
        numStack.push(ans);
    }
}

Summary:
The problem looks complicated to implement, actually could be memorized in a template way. 
If the token is a number, then push it to the num stack. 
If the token is a operator, there are 5 cases to consider:
1. If the opStack is empty
  -- push into opStack
2. If the token is + or -
  -- Check the top of the opStack. 
     -- If the top is '(', then push the token into opStack.
     -- Else (which means has higher or equal precedence), consume the stack by doing one computation. 
3. If the token is * or /
     -- If the top is '(', push the token into opStack
     -- Else if top has lower precedence ( + or -), push the token into opStack.
     -- Else if the top has equal precedence (* or /), consume the stack by doing one computation. 
4. If the token is (
    -- Push into opStack
5. If the token is )
   -- Doing computations until we see the '(' in the opStack. 


There is another corner case need to be very careful is:
If the input String has only one number, e.g. (1), 1, 1*. For OA it is still valid. So the trick to handle this edge case is in the computation method, before we pop two numbers from the numStack, we check if the size of the numStack. If less than 2, we know that this case happens. Then we only need to do is pop out the opStack until it is empty. Then the result is the only number in the numStack.