class Solution {
public:
    int calculate(string s) {
        stack<int> operands;
        stack<char> operations;
        string operand;
        for (int i = (int)s.length() - 1; i >= 0; i--) {
            if (s[i] == ')' || s[i] == '+' || s[i] == '-')
                operations.push(s[i]);
            else if (isdigit(s[i])) {
                operand = s[i] + operand;
                if (!i || !isdigit(s[i-1])) {
                    operands.push(stoi(operand));
                    operand.clear();
                }
            }
            else if (s[i] == '(') {
                while (operations.top() != ')') {
                    compute(operands, operations);
                }
                operations.pop();
            }
        }
        while (!operations.empty()) {
            compute(operands, operations);
        }
        return operands.top();
    }
    
    void compute(stack<int>& operands, stack<char>& operations) {
        int left = operands.top();
        operands.pop();
        int right = operands.top();
        operands.pop();
        int op = operations.top();
        operations.pop();
        if (op == '+')  operands.push(left + right);
        if (op == '-')  operands.push(left - right);
    }
};

class Solution {
public:
    int calculate(string s) {
        int result = 0, d = 0;
        char sign = '+';
        stack<int> nums;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] >= '0') {
                d = d * 10 + s[i] - '0';
            }
            if (!isdigit(s[i]) && s[i] != ' ' || i == s.size() - 1) {
                if (sign == '+') nums.push(d);
                if (sign == '-') nums.push(-d);
                if (sign == '*' || sign == '/') {
                    int temp = sign == '*' ? nums.top() * d : nums.top() / d;
                    nums.pop();
                    nums.push(temp);
                } 
                sign = s[i];
                d = 0;
            }
        }
        while (!nums.empty()) {
            result += nums.top();
            nums.pop();
        }
        return result;
    }
};