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

Solution 1: 在第一个数前加+。每次遇到运算符或者最后一个字符时，根据之前的运算符对栈操作：若之前的是+，把num压入栈；若之前的是-，把- num压入栈；若之前的是*，弹出栈顶，压入栈顶*num；若之前的是/，弹出栈顶，压入栈顶/ num。并把运算符更新为当前字符的运算符。最后把栈所有元素相加。

    public int calculate(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        char sign = '+';
        int num = 0;
        Deque<Integer> stack = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c >= '0' && c <= '9') {
                num = num * 10 + c - '0';
            } 
            if (isOperator(c) || i == s.length() - 1) {
                switch(sign) {
                    case '+' :
                        stack.offerLast(num);
                        break;
                    case '-' :
                        stack.offerLast(-num);
                        break;
                    case '*' :
                        stack.offerLast(stack.pollLast() * num);
                        break;
                    case '/' :
                        stack.offerLast(stack.pollLast() / num);    
                        break;
                }
                sign = c;
                num = 0;
            }
        }
        int ans = 0;
        while (!stack.isEmpty()) {
            ans += stack.pollLast();
        }
        return ans;
    }
    private boolean isOperator(char c) {
        return c == '+' || c == '-' || c == '*' || c == '/';
    }

Solution 2: 不用栈，用prevValue记录上一个数（类似记录栈顶元素）

public int calculate(String s) {
    if (s == null) return 0;
    s = s.trim().replaceAll(" +", "");
    int length = s.length();

    int res = 0;
    long preVal = 0; // initial preVal is 0
    char sign = '+'; // initial sign is +
    int i = 0;
    while (i < length) {
        long curVal = 0;
        while (i < length && (int)s.charAt(i) <= 57 && (int)s.charAt(i) >= 48) { // int
            curVal = curVal*10 + (s.charAt(i) - '0');
            i++;
        }
        if (sign == '+') {
            res += preVal;  // update res
            preVal = curVal;
        } else if (sign == '-') {
            res += preVal;  // update res
            preVal = -curVal;
        } else if (sign == '*') {
            preVal = preVal * curVal; // not update res, combine preVal & curVal and keep loop
        } else if (sign == '/') {
            preVal = preVal / curVal; // not update res, combine preVal & curVal and keep loop
        }
        if (i < length) { // getting new sign
            sign = s.charAt(i);
            i++;
        }
    }
    res += preVal;
    return res;
}