Problem: 770. Basic Calculator IV 基本计算器 IV
解题过程
困难题，步骤太多了，多项式加法和乘法，写了300多行的codes，平时就几十行，首先放入列表中，将字符串、运算符号全部放入列表中，当字符是(时，入栈找到)然后递归调用，拿到列表以后，将-号全部放入到数字或者字符串内，就开始运算，实现了多项式加法和乘法，每次算完就替换掉，并且删除两个，继续运算的，
加法数字单独考虑，两个多项式，若都是数字直接累加，若都是变量则提取出系数和字符串，系数累加的，若是没找到匹配的，就是累加到数字或者放入结果列表中，若是数字！=0则放入列表
乘法数字单独考虑，若都是变量则提取出系数和字符串，系数累加的，字符串根据字典序排列并用*号拼接起来，若一个变量一个数字则系数累乘的而且字符串不变，还需要考虑结果列表中有相同字符串的结果，此时需要合并起来也就是系数累加起来，若是没找到匹配的，就是累加到数字或者放入结果列表中，若是数字！=0则放入列表
还需要考虑结果是0的情况，此时也放入列表中当作占位符，最后删掉即可
排序的时候统计*号的个数，*号越多越靠前，否则按照字典序排序，数字排在最后
Code
class Solution { public: unordered_map<string, int> ump; int findparentheses(string& expression, int start) { stack<char> tk; tk.push('('); for(int i = start; i < expression.size(); i++) { if(expression[i]=='(') tk.push('('); else if(expression[i]==')') tk.pop(); if(tk.empty()) { return i; } } return 0; } vector<string> dfs(string& expression) { string tmp; vector<vector<string>> tk; for(int i = 0; i < expression.size(); i++) { if(isalpha(expression[i])||isdigit(expression[i])|| expression[i]=='-'||expression[i]=='+'||expression[i]=='*') { tmp += expression[i]; } if(expression[i]==' ' || i == expression.size()-1) { if(ump.find(tmp) != ump.end()) { tk.push_back( { to_string( ump[tmp] ) } ); } else { tk.push_back({tmp}); } int n = tk.size(); if(tk[n-1][0]!="+" && tk[n-1][0]!="-" && tk[n-1][0]!="*" && !isNum(tk[n-1][0])) { tk[n-1][0] = {"1*" + tk[n-1][0]}; } tmp.clear(); }else if(expression[i]=='(') { int j = findparentheses(expression, i+1); string tmptg = expression.substr(i+1, j - i - 1); vector<string> trtg = dfs(tmptg); if(trtg.size() > 0) { tk.push_back(trtg); } else { tk.push_back({"0"}); } i = j + 1; } } for(int j = 0; j < tk.size()-1; j++) { if(j >= (int)tk.size()-1) { break; } if(tk[j][0].size()==1 && tk[j][0]=="-") { tk[j][0] = {"+"}; for(int k = 0; k < tk[j+1].size(); k++) { if(isNum(tk[j+1][k])) { if(tk[j+1][k][0]!='-') { tk[j+1][k] = "-" + tk[j+1][k]; } else { tk[j+1][k] = tk[j+1][k].substr(1); } } else { int id = tk[j+1][k].find('*'); string tri = tk[j+1][k].substr(id+1); if(tk[j+1][k][0]!='-') { tk[j+1][k] = "-" + tk[j+1][k]; } else { tk[j+1][k] = tk[j+1][k].substr(1); } } } } } if(tk.size() > 0 && tk.front()[0] == "+") { tk.erase(tk.begin()); } for(int i = tk.size()-2; i >= 0; i--) { //// "(av * 9) - (ar + 0) - ((bq - cv) + v * (b + bq - bk)) * (a - 12 + 2 - (6 * cc - 8 - bv + ag))" if(i - 2 >= 0 && tk[i-2].size()==1 && tk[i-2][0]=="*") { vector<string> tgt = multiply(tk[i-3], tk[i-1]); // tk[i-1] = tgt; if(tgt.size() > 0) { tk[i-1] = tgt; } else { tk[i-1] = {"0"}; } tk.erase(tk.begin() + i - 3); tk.erase(tk.begin() + i - 3); i--; }else if(tk[i].size()==1 && (tk[i][0]=="+" || tk[i][0]=="-" || tk[i][0]=="*")) { vector<string> tgt; if(tk[i][0]=="+"){ tgt = add_sub(tk[i-1], tk[i+1], 1); } else if(tk[i][0]=="*"){ tgt = multiply(tk[i-1], tk[i+1]); } if(tgt.size() > 0) { tk[i+1] = tgt; } else { // tk.erase(tk.begin() + i + 1); tk[i+1] = {"0"}; } tk.erase(tk.begin() + i - 1); tk.erase(tk.begin() + i - 1); i--; } if(tk.size() == 1) break; } if(tk.size()==0) return {}; if(tk[0][0]=="0") return {}; return tk[0]; } bool isNum(string t) { for(char& c : t) { if(c>='a' && c<='z') { return false; } } return true; } vector<string> add_sub(vector<string>&a, vector<string>&c, int type) { vector<string> ret; unordered_set<int> te; int number = 0; for(int i = 0; i < a.size(); i++) { int find = -100; for(int j = 0; j < c.size(); j++) { if(te.find(j)!=te.end()) continue; if(isNum(a[i]) && isNum(c[j])) { te.insert(j); find = 1; int n1 = stoi(a[i]); int n2 = stoi(c[j]); if(type < 0) { number = number + n1 - n2; } else { number = number + n1 + n2; } } else { int id1, id2; string t1, t2, p1, p2; id1 = a[i].find('*'); id2 = c[j].find('*'); if(id1!=string::npos && id2!=string::npos) { t1 = a[i].substr(id1); t2 = c[j].substr(id2); p1 = a[i].substr(0, id1); p2 = c[j].substr(0, id2); if(t1==t2) { int nt; if(type < 0) { nt = stoi(p1) - stoi(p2); } else { nt = stoi(p1) + stoi(p2); } a[i] = to_string(nt) + t1; find = 0; te.insert(j); } } } } if(find < 0) { if(isNum(a[i])) number += stoi(a[i]); else ret.push_back(a[i]); } else if(find==0) { int id1 = a[i].find('*'); if(id1!=string::npos) { string t1 = a[i].substr(0, id1); if(stoi(t1)!=0) { ret.push_back(a[i]); } } } } for(int j = 0; j < c.size(); j++) { if(te.find(j)!=te.end()) continue; ret.push_back(c[j]); } if(number!=0) { ret.push_back(to_string(number)); } return ret; } vector<string> multiply(vector<string>&a, vector<string>&c) { vector<string> ret; int number = 0; for(int i = 0; i < a.size(); i++) { for(int j = 0; j < c.size(); j++) { if(isNum(a[i]) && isNum(c[j])) { int n1 = stoi(a[i]); int n2 = stoi(c[j]); number = number + n1 * n2; } else { int id1, id2; string t1, t2, p1, p2; id1 = a[i].find('*'); id2 = c[j].find('*'); if(id1!=string::npos && id2!=string::npos) { t1 = a[i].substr(id1); t2 = c[j].substr(id2); p1 = a[i].substr(0, id1); p2 = c[j].substr(0, id2); vector<string> testr; string tmptmp; for(int k = 0; k < t1.size(); k++) { if(t1[k]!='*') { tmptmp += t1[k]; } if((t1[k]=='*'||k==t1.size()-1) && tmptmp.size()!=0) { testr.push_back(tmptmp); tmptmp.clear(); } } tmptmp.clear(); for(int k = 0; k < t2.size(); k++) { if(t2[k]!='*') { tmptmp += t2[k]; } if((t2[k]=='*'||k==t2.size()-1) && tmptmp.size()!=0) { testr.push_back(tmptmp); tmptmp.clear(); } } tmptmp.clear(); sort(testr.begin(), testr.end()); for(auto& tg : testr) { tmptmp = tmptmp + "*" + tg; } int nt; nt = stoi(p1) * stoi(p2); for(int k = 0; k < ret.size(); k++) { id2 = ret[k].find('*'); if(id2 != string::npos) { p2 = ret[k].substr(0, id2); t2 = ret[k].substr(id2); if(t2 == tmptmp) { nt = nt + stoi(p2); ret.erase(ret.begin() + k); break; } } } if(nt!=0) ret.push_back(to_string(nt) + tmptmp); } else { if(id1!=string::npos && id2==string::npos) { t1 = a[i].substr(id1); t2 = ""; p1 = a[i].substr(0, id1); p2 = c[j]; } else { t1 = ""; t2 = c[j].substr(id2); p1 = a[i]; p2 = c[j].substr(0, id2); } string tmptmp = t1 + t2; int nt; nt = stoi(p1) * stoi(p2); for(int k = 0; k < ret.size(); k++) { id2 = ret[k].find('*'); if(id2 != string::npos) { p2 = ret[k].substr(0, id2); t2 = ret[k].substr(id2); if(t2 == tmptmp) { nt = nt + stoi(p2); ret.erase(ret.begin() + k); break; } } } if(nt!=0) ret.push_back(to_string(nt) + tmptmp); } } } } if(number!=0) { ret.push_back(to_string(number)); } return ret; } static bool compare(string&as, string& cs) { int id1, id2, n1 = 0, n2 = 0; string tt1, tt2; id1 = as.find('*'); id2 = cs.find('*'); if(id1!=string::npos && id2!=string::npos) { for(int i = id1; i < as.size(); i++) { if(as[i]=='*') n1++; // else tt1 += as[i]; } for(int i = id2; i < cs.size(); i++) { if(cs[i]=='*') n2++; // else tt2 += cs[i]; } tt1 = as.substr(id1+1); tt2 = cs.substr(id2+1); if(n1==n2) return tt1 < tt2; else return n1 > n2; } else if(id1==string::npos) { return false; } else { return true; } } vector<string> basicCalculatorIV(string expression, vector<string>& evalvars, vector<int>& evalints) { for(int i = 0; i < evalvars.size(); i++) { ump[evalvars[i]] = evalints[i]; } vector<string> ret = dfs(expression); for(int i = 0; i < ret.size(); i++) { if(ret[i]=="0") { ret.erase(ret.begin() + i); i--; } } if(ret.size()==0) return {}; sort(ret.begin(), ret.end(), compare); return ret; } };
