该题的思路非常明白就是将中缀表达式转换为后缀表达式。然后通过后缀表达式来求值。
class Solution {public: int calculate(string s) { vector postorder; stack ccache; stack 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(); }}