C++: 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) {
        
        // Either number (digit) will come or 
        // + sign or - sign or bracket
        // have to handle sign.

        int number = 0;
        int sign = 1;
        int result = 0;
        stack<int> st;
        for(int i=0;i<s.size();i++){

            char ch = s[i];
            if(isdigit(ch)){
                number = number*10 + (ch-'0');
            }
            else if(ch=='+'){
                result = result + number*sign;
                number = 0;
                sign = 1;
            }
            else if(ch=='-'){
                result = result + number*sign;
                number = 0;
                sign = -1;
            }
            else if(ch=='('){
                st.push(result);
                st.push(sign);
                result = 0;
                sign = 1;
                number = 0;
            }
            else if(ch==')'){
                result = result + number*sign;
                result = result*st.top();   st.pop();
                result = result + st.top(); st.pop();
                number = 0;
                sign = 1;
            }
        }
        result = result + number*sign;
        return result;
    }
};

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!