224. Basic Calculator

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

You may assume that the given expression is always valid.

Some examples:

"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23

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

Solution:

Use a stack to keep track of parentheses.

Go through the string and check each character c:

1. If c is a digit, we go forward and find the next non-digit one. Therefore we get a number and use the current sign to update the current result inside the current parentheses.

2. If c is a sign, we update the sign.

3. If c is left parenthesis, we push the current result and sign into the stack.

4. If c is right parenthesis, we pop out the sign and result and add with the current result.

5. We do not need to handle other characters.



Code:

public class Solution {
    public int calculate(String s) {
        int result = 0;
        int sign = 1;
        int len = s.length();
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < len; i++) {
            char c = s.charAt(i);
            if (c >= '0' && c <= '9') {
                int num = c - '0';
                while (i + 1 < len && s.charAt(i + 1) >= '0' && s.charAt(i + 1) <= '9') {
                    num = num * 10 + s.charAt(i + 1) - '0';
                    i++;
                }
                result += num * sign;
            }
            else if (c == '+' || c == '-') {
                sign = c == '+' ? 1 : -1;
            }
            else if (c == '(') {
                stack.push(result);
                stack.push(sign);
                result = 0;
                sign = 1;
            }
            else if (c == ')') {
                result = stack.pop() * result + stack.pop();
            }
        }
        return result;
    }
}