Java: Basic Calculator

Thought Process

The problem involves evaluating a basic arithmetic expression containing digits, '+', '-', and parentheses. We use a stack to handle the nested structure introduced by parentheses. The key idea is to maintain a result variable for the current computation and a sign variable to handle the effect of subtraction. When encountering a '(', we push the current result and sign onto the stack and reset them. For ')', we pop the previous result and sign from the stack and combine them with the current computation. 

class Solution {
    public int calculate(String s) {
        
        int sign = 1;
        int num = 0;
        int ans = 0;

        Stack<Integer> st = new Stack<>();
        for(int i=0;i<s.length();i++){

            char ch = s.charAt(i);
            if(Character.isDigit(ch)){
                num = num*10 + ch-'0';
            }
            else if(ch == '+'){
                ans = ans + num*sign;
                sign = 1;
                num = 0;
            }
            else if(ch == '-'){
                ans = ans + num*sign;
                sign = -1;
                num = 0;
            }
            else if(ch == '('){
                st.push(ans);
                st.push(sign);
                ans = 0;
                sign = 1;
            }
            else if(ch == ')'){  // Assume something like .. +3)

                int prevSign = st.pop();
                int prevAns = st.pop();
                ans = ans + num*sign;  
                ans = ans*prevSign + prevAns;
                num = 0;
                sign = 1;
            }
        }
        ans = ans + num*sign;
        return ans;
    }
}

Code Complexity

Time Complexity: O(n)

The algorithm processes each character in the string once, where 'n' is the length of the string.

Space Complexity: O(n)

The stack can store up to 'n' elements in the worst case, depending on the depth of nested parentheses.

Code copied!