class Solution {
public:
    int recursive_calculator (string& s, int& i, int& last_indx) {
        long num = 0;
        stack<int> num_stack;
        char prev_sign = '+'; // default sign
        int tmp_sum = 0;

        for (; i < s.size(); i++) {
            if (s[i] == ' ' && i != last_indx) continue;

            if (isdigit(s[i]))  {
                num = num * 10 + (s[i] - '0');
            } else if ( s[i] == '(' ) {
                i++;
                num = recursive_calculator(s, i, last_indx);
            }

            if ( s[i] == ')' ||  i == last_indx || !isdigit(s[i]) ) {
                long num_pushed = 0;

                switch(prev_sign) {
                    case '+':
                        num_stack.push(num);
                        break;
                    case '-':
                        num_stack.push(-num);
                        break;
                    case '/':
                        num_pushed = ( num_stack.top() ) / num;
                        num_stack.pop();
                        num_stack.push(num_pushed);
                        break;
                    case '*':
                        num_pushed = ( num_stack.top() ) * num;
                        num_stack.pop();
                        num_stack.push(num_pushed);
                        break;
                    default:
                        break;
                }

                num = 0;

                if (s[i] == ')') {
                    i++;
                    break;
                }

                // prev sign may get assigned ' ' or ')'  but the switch case will take care
                // all invalid prev sign will fall in the default;
                if (i < last_indx) prev_sign = s[i];
            }
        }

        while (!num_stack.empty()) {
            tmp_sum += num_stack.top();
            num_stack.pop();
        }
        return tmp_sum;
    }



    int calculate(string s) {
        int new_start_pos = 0;
        int last_indx = s.size()-1;
        return recursive_calculator(s, new_start_pos, last_indx);
    }
};