224. Basic Calculator

T: O(n)

S: O(n)

巧妙之處在於何時入 stack, 看到 ()就想到 stack

( => push

) => pop, cal result

( => push result, sign, set inital result, sign

) => cal result = result*pop(sign) + pop(result)

class Solution {
    public int calculate(String s) {
        int len = s.length();
        int result = 0;
        int sign = 1;
        Stack<Integer> stack = new Stack<>();
        
        for (int i = 0; i < len; i++) {
            char c = s.charAt(i);
            
            if (Character.isDigit(c)) {
                int num = c - '0';
                // ex: 10, when index 0, get 10, then when index = 1, break!, so smart
                while (i + 1 < len && Character.isDigit(s.charAt(i+1))) {
                    num = num*10 + (s.charAt(i+1) - '0');
                    i++;
                }
                result += num*sign;
                
            } else if (c == '+' || c == '-') {
                sign = (c == '+') ? 1 : -1;
                
            } else if (c == '(') { // push to stack
                stack.push(result);
                stack.push(sign);
                result = 0; // after push, set to init value
                sign = 1;
            } else if (c == ')') { // cal result, pop
                result = result*stack.pop() + stack.pop();
            }
        }
        return result;
    }
}

/*
time: O(n)
space: O(n)

(1+(4+5+2)-3)+(6+8)

( => push result, sign, set inital result, sign

) => cal result = result*pop(sign) + pop(result)

*/

or like this, just chande number part

class Solution {
    public int calculate(String s) {
        int len = s.length();
        int result = 0;
        int sign = 1;
        Deque<Integer> stack = new ArrayDeque<>();
        int i = 0;
        while (i < len) {
            if (Character.isDigit(s.charAt(i))) {
                int num = 0;
                // 10
                // 因為整個最外層有 i++, 所以這裡最後要 i--
                while (i < len && Character.isDigit(s.charAt(i))) {
                    num = num*10+ (s.charAt(i) - '0');
                    i++;
                }
                i--;
                result += sign*num;
            } else if (s.charAt(i) == '+' || s.charAt(i) == '-' ) { 
                sign = (s.charAt(i) == '+') ? 1 : -1;
                
            } else if (s.charAt(i) == '(') {
                stack.push(result);
                stack.push(sign);
                result = 0;
                sign = 1;
                
            } else if (s.charAt(i) == ')') {
                result = stack.pop()*result + stack.pop();
            }
            i++;
        }
        return result;
    }
}

/*
"(1+(4+5+2)-3)+(6+8)"

result = 14
sign = 1


1
8

14 + 8 = 22

*/

recursion

T: O(k*n), k is call dfs times, n is String length

S: O(n)

class Solution {
    public int calculate(String s) {
        return dfs(s, 0)[0];
    }
    private int[] dfs(String s, int i) {
        int result = 0;
        int sign = 1;
        while (i < s.length()) {
            
            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--;
                result += sign*num;
            } else if (s.charAt(i) == '(') {
                int temp[] = dfs(s, i+1);
                i = temp[1];
                result += sign*temp[0];
                
            } else if (s.charAt(i) == ')') {
                return new int[] {result, i};
            } else if (s.charAt(i) == '+' || s.charAt(i) == '-') {
                sign = (s.charAt(i) == '+') ? 1 : -1;
            }
            i++;
        }
        return new int[] {result, 0};
    }
}

/*
(1+(4+5+2)-3)+(6+8)


when ( => dfs

) => return ans
*