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.

Solution1：Stack

思路： 提取并随着遍历数字nums[i], 同时记录每次数字前的符号，如果是operator是+或-，直接保存到stack中，即push(operator * nums[i]),
如果是*或/，从stack中pop出一个数，进行乘除运算后，push至stack中。
遍历数字后，结果都保存在了stack中，以只含加减的多项和元素的形式保存，所以再对此stack中元素进行遍历累加，得到最后计算结果。
例： " 3+5 / 2 " = 5
如 遇+3，stack存入+3; 遇+5, stack存入+5, 遇/2, pop出5，计算得到 5/2 = 2,此结果2 push到stack,
此时stack中 +3, +2，累加得到结果5

Time Complexity: O(N) Space Complexity: O(n)

Solution Code：

public class Solution {
    public int calculate(String s) {
        int len = s.length();
        if (s == null || len == 0) return 0;

        Stack<Integer> stack = new Stack<Integer>();
        int num = 0;
        char operator = '+';
        for (int i = 0; i < len; i++) {
            if (Character.isDigit(s.charAt(i))) {
                num = num * 10 + s.charAt(i) - '0';
            }
            if ((!Character.isDigit(s.charAt(i)) && ' ' != s.charAt(i)) || i == len - 1) {
                if (operator == '-') stack.push(-num);
                if (operator == '+') stack.push(num);
                if (operator == '*') stack.push(stack.pop() * num);
                if (operator == '/') stack.push(stack.pop() / num);
                operator = s.charAt(i);
                num = 0;
            }
        }

        // calculate the result from sum of elements in stack
        int re = 0;
        for (int i : stack) {
            re += i;
        }
        return re;
    }
}