224. Basic Calculator.md

Solution1

class Solution {
    public int calculate(String s) {
        if (s == null) {
            return 0;
        }
        Stack<Integer> stack = new Stack<>();
        int res = 0;
        int sign = 1;
        int number = 0;
        for (int i = 0; i < s.length(); i++) {
            Character c = s.charAt(i);
            if (c >= '0' && c <= '9') {
                number = 10 * number + (c - '0');
            }
            else if (c == '+') {
                res += sign * number;
                number = 0;
                sign = 1;
            }
            else if (c == '-') {
                res += sign * number;
                number = 0;
                sign = -1;
            }
            else if (c == '(') {
                stack.push(res);
                stack.push(sign);
                number = 0;
                sign = 1;
                res = 0;
            }
            else if (c == ')') {
                res += sign * number;
                res *= stack.pop();
                res += stack.pop();
                sign = 1;
                number = 0;
            }
        }
        if (number != 0) {
            res += sign * number;
        }
        return res;
    }
}

note

• The idea is to use a stack to store the sign & number and iterate through the string and evaluate accordingly in terms of the sign.
• When it sees number, we update the number for future use (here, be careful the number might not be single digit, so we do number * 10 + (c - 'a')).
• When it sees '+' or '-', we will evaluate previous value and set number to 0 and sign accordingly.
• When it sees '(', it means we need to store our previous result and sign temporarily and start evaluating expression in this new parenthesis when we will push value first into stack and then sign (it's important that we push sign first so we can use it later right after we finish evaluating the expression in this new parenthesis).
• When it meets ')', we will first wrap up the calculation inside this parenthesis by res += sign * number and then pop out the sign and result before this parenthesis and update our value.
• After the loop, check if number is 0. If not, we do a final calculation.

Solution2 (initial solution/brute force/slow)

class Solution {
    public int calculate(String s) {
        Stack<Integer> stack = new Stack<>();
        s = s.trim();
        int sign = 1;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                int cnt = -1;
                int start = i;
                while (cnt != 0) {
                    i++;
                    if (s.charAt(i) == '(') {
                        cnt--;
                    }
                    if (s.charAt(i) == ')') {
                        cnt++;
                    }
                }
                stack.push(sign * calculate(s.substring(start + 1, i + 1)));
            }
            else if (Character.isDigit(s.charAt(i))) {
                int num = 0;
                while (i < s.length() && Character.isDigit(s.charAt(i))) {
                    num = num * 10 + s.charAt(i) - '0';
                    i++;
                }
                i--;
                stack.push(sign * num);
            }
            else if (c == '+' || c == '-') {
                
                sign = c == '+' ? 1 : -1;
                System.out.println(sign);
            }
        }
        int ret = 0;
        while (!stack.empty()) {
            ret += stack.pop();
        }
        return ret;
    }
}