class Solution {
public:
    /**
     * @param expression: a vector of strings;
     * @return: an integer
     */
    int evaluateExpression(vector<string> &expression) {
        // write your code here

        int n=expression.size();
        opands.push(0);
        for(int i=0;i<n;i++) {
            if(isdigit(expression[i][0])) { // hacky: only check the first char
                opands.push(atoi(expression[i].c_str()));
            } else if(expression[i]==")") {
                while(ops.top()!='(') {
                    computeAndPush();
                }
                ops.pop();
            } else {
                if(!ops.empty() && hasPrecedence(ops.top(), expression[i][0])) {
                    computeAndPush();
                }
                ops.push(expression[i][0]);
            }
        }

        while(!ops.empty()) {
            computeAndPush();
        }
        return opands.top();
    }

    void computeAndPush() {
        int opand2=opands.top(); opands.pop();
        int opand1=opands.top(); opands.pop();
        char op=ops.top(); ops.pop();
        switch(op){
            case '+': opands.push(opand1+opand2); break;
            case '-': opands.push(opand1-opand2); break;
            case '*': opands.push(opand1*opand2); break;
            case '/': opands.push(opand1/opand2); break;
        }
    }

    bool hasPrecedence(char op1, char op2) {
        if(op2=='(') return false;
        if((op2=='*' || op2=='/') && (op1=='+' || op1=='-')) return false;
        return true;
    }
private:
    stack<char> ops;
    stack<int> opands;
};