该题的思路非常明白就是将中缀表达式转换为后缀表达式。然后通过后缀表达式来求值。

class Solution {
public:

    int calculate(string s) {        
        vector<string> postorder;
        stack<char> ccache;
        stack<int> icache;
        string tmp;
        int len = s.length();
        if(s.length() < 1)
            return 0;
//构造后缀表达式
        for(int i = 0; i < len; ){
            if(s[i] == ‘ ‘){
                i++;
                continue;
            }
            if(s[i] == ‘+‘ || s[i] == ‘-‘ || s[i] == ‘(‘ || s[i] == ‘)‘){
                if(s[i] == ‘(‘ || ccache.empty()){
                    ccache.push(s[i]);
                    i++;
                    continue;
                }
                if(s[i] == ‘)‘){
                    while(ccache.top() != ‘(‘){
                        tmp = "";
                        tmp += ccache.top();
                        postorder.push_back(tmp);
                        ccache.pop();
                    }
                    ccache.pop();
                    i++;
                    continue;
                }
                if(s[i] == ‘+‘ || s[i] == ‘-‘){
                    while(!ccache.empty() && ccache.top() != ‘(‘ ){
                        tmp = "";
                        tmp += ccache.top();
                        postorder.push_back(tmp);
                        ccache.pop();
                    }
                    ccache.push(s[i]);
                    i++;
                    continue;
                }
            }else{
                int j = i;
                while(j < len && s[j] >= ‘0‘ && s[j] <= ‘9‘)
                    j++;
                tmp = "";
                tmp = s.substr(i, j - i);
                postorder.push_back(tmp);
                i = j;
            }
        }
//将栈中剩余的元素所有加入到后缀表达式字串中
        while(!ccache.empty()){
            tmp = "";
            tmp += ccache.top();
            ccache.pop();
            postorder.push_back(tmp);
        }

//通过后缀表达式求值
        int fir, sec;
        for(int i = 0; i < postorder.size(); i++){
            if(postorder[i] == "+" || postorder[i] == "-"){
                sec = icache.top();
                icache.pop();
                fir = icache.top();
                icache.pop();
                if(postorder[i] == "+")
                    icache.push(fir + sec);
                if(postorder[i] == "-")
                    icache.push(fir - sec);
            }else{
                icache.push(atoi(postorder[i].c_str()));
            }
        }
        return icache.top();
    }
}