[LeetCode] Basic Calculator II

Basic Calculator II

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid.

Some examples:

"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5

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

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

Solution: Since here we do not have parentheses, a stack is not necessary. 

One can directly make one pass to derive the result, by maintaining preMulDiv, preAddSub, preNum, and curNum.

The logic: 

Each time we see '+' or '-', we know '*' or '/' before it must have been processed. If we have unprocessed '+' or '-' before, process the old one.

Each time we see a number, if we have unprocessed '*' or '/', process it immediately. Otherwise, update preNum and curNum.

In the end, we need to check whether we need to process '+' or '-' once.
Remarks. In order to deal with the special test case "0-2147483648", I added a little more code. Did not aim to take care of all large number operations.

public class Solution {
    private boolean isOverflow(String s) {
        return s.equals("2147483648");
    }

    private int evalOp(int a, int b, char op) {
        switch (op) {
            case '+': return a + b;
            case '-': return a - b;
            case '*': return a * b;
            default: return a / b;
        }
    }
    
    public int calculate(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        Character preAddSub = null;
        Character preMulDiv = null;
        Integer preNum = null;
        Integer curNum = null;
        int i = 0;
        while (i < s.length()) {
            if (Character.isWhitespace(s.charAt(i))) {
                i++;
            } else if (Character.isDigit(s.charAt(i))) {
                int j = i + 1;
                while (
                    j < s.length() && 
                    Character.isDigit(s.charAt(j))
                ) {
                    j++;    
                }
                if (isOverflow(s.substring(i, j))) {
                    return Integer.MIN_VALUE;
                }
                int nextNum = Integer.valueOf(s.substring(i, j));
                if (preMulDiv != null) {
                    curNum = evalOp(curNum, nextNum, preMulDiv);
                    preMulDiv = null;
                } else {
                    preNum = curNum;
                    curNum = nextNum;
                }
                i = j;
            } else if (s.charAt(i) == '+' || s.charAt(i) == '-') {
                if (preAddSub != null) {
                    curNum = evalOp(preNum, curNum, preAddSub);
                } 
                preAddSub = s.charAt(i);
                i++;
            } else {
                preMulDiv = s.charAt(i);
                i++;
            }
        }
        if (preAddSub != null) {
            curNum = evalOp(preNum, curNum, preAddSub);
        } 
        return curNum;
    }
}