224. Basic Calculator

Hard

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 .

Example 1:

Input: "1 + 1"
Output: 2

Example 2:

Input: " 2-1 + 2 "
Output: 3

Example 3:

Input: "(1+(4+5+2)-3)+(6+8)"
Output: 23

Solution:
Digit: when scan one digit, we can start one new number. when number is over, add this number to sum. Because this number must have sign and previous result.
+: assign 1 to sign for next number.
-:  assign -1 to sign for next numer.
(: push the previous result before this parenthesis and the sign for the result of this parenthesis into stack. set sum to 0, just calculate the new result with the parethesis.
):pop up two numbers from stack. the first is the sign before parenthesis, the second is the temporary result before the pair of parenthesis. we add them into the sum.

class Solution {
    public int calculate(String s) {
        Stack<Integer> stack = new Stack<Integer>();
        int sum = 0;
        int number = 0;
        int sign = 1;
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if(Character.isDigit(c)){
                number = 0;
                while(Character.isDigit(c)){
                    number = number * 10 + c - '0';
                    i++;
                    if(i >= s.length()) break;
                    c = s.charAt(i);
                }
                sum += sign * number;
                i--; 
            }else if(c == '+'){
                sign = 1;
            }else if(c == '-'){           
                sign = -1;
            }else if(c == '('){
                stack.push(sum);
                stack.push(sign);
                sum = 0;
                sign = 1;
            }else if(c == ')'){
                sign = stack.pop();
                int previousNum = stack.pop();
                sum = previousNum + sign * sum;
            }else{
                
            }   
        }
        return sum;
    }
}