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-negativeintegers and empty spaces.

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

You may assume that the given expression is always valid. All intermediate results will be in the range of[-2147483648, 2147483647].

Some examples:

"1 + 1" = 2
" 6-4 / 2 " = 4
"2*(5+5*2)/3+(6/2+8)" = 21
"(2+6* 3+5- (3*14/7+2)*5)+3"=-12

Note:Do notuse theevalbuilt-in library function.

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

        s = s.trim();
        s = s.replaceAll("\\s", "");

        int num = 0;
        char sign = '+';
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++){
            char c = s.charAt(i);

            if (Character.isDigit(c)){
                num = num * 10 + (c - '0');
            }
            else if (c == '('){
                int j = i + 1, count = 1;
                for (; j < s.length(); j++){
                    if (s.charAt(j) == '(') count++;
                    else if (s.charAt(j) == ')') count--;

                    if (count == 0) break;
                }

                num = calculate(s.substring(i + 1, j));
                i = j;
            }

            //System.out.println("i: " + i + " num: " + num);
            if (!Character.isDigit(c) || i == s.length() - 1){
                if (sign == '+'){
                    stack.push(num);
                }
                else if (sign == '-'){
                    stack.push(-num);
                }
                else if (sign == '*'){
                    stack.push(stack.pop() * num);
                }
                else if (sign == '/'){
                    stack.push(stack.pop() / num);
                }

                sign = c;
                num = 0;
            }
        }

        int ans = 0;
        while (!stack.isEmpty()){
            ans += stack.pop();
        }

        return ans;
    }
}