题目描述：
给定一个化学式formula（作为字符串），返回每种原子的数量。
原子总是以一个大写字母开始，接着跟随0个或任意个小写字母，表示原子的名字。
如果数量大于 1，原子后会跟着数字表示原子的数量。如果数量等于 1 则不会跟数字。例如，H2O 和 H2O2 是可行的，但 H1O2 这个表达是不可行的。
两个化学式连在一起是新的化学式。例如 H2O2He3Mg4 也是化学式。
一个括号中的化学式和数字（可选择性添加）也是化学式。例如 (H2O2) 和 (H2O2)3 是化学式。
给定一个化学式，输出所有原子的数量。格式为：第一个（按字典序）原子的名子，跟着它的数量（如果数量大于 1），然后是第二个原子的名字（按字典序），跟着它的数量（如果数量大于 1），以此类推。
示例 1:
输入:
formula = "H2O"
输出: "H2O"
解释:
原子的数量是 {'H': 2, 'O': 1}。
题源：https://leetcode-cn.com/problems/number-of-atoms/
错误点：
1、没有考虑到括号不仅仅是嵌套的问题，还有平行的关系，所以需要用stack进行存储；
2、括号外面可能没有数字，表示1.
3、在力扣中，写sort函数的比较函数cmp，前面需要加上static。
代码：
class Solution { public: /* struct nodee{ string ch; int ti; }; bool cmp(nodee a,nodee b) { return a.ch<b.ch; } */ //不知道为什么sort一直报错，然后发现map键值就是有序的，所以最后没有用。 string countOfAtoms(string formula) { struct node { int up,down,ti; node(int a,int b,int c){up=a; down=b; ti=c;} }; vector<node> kuohao; stack<int> st; int l=formula.length(); for(int i=0;i<l;i++) //统计括号的对数，以及对应的数字。 { if(formula[i]=='(') {st.push(i); continue;} if(formula[i]==')') { int k=i+1; int s=0; if(formula[k]>='0' && formula[k]<='9') { while(k<l && formula[k]>='0' && formula[k]<='9') { s=s*10+formula[k]-'0'; k++; } } else s=1; kuohao.push_back(node(st.top(),i,s)); st.pop(); } } //for(int i=0;i<kuohao.size();i++) //cout<<kuohao[i].up<<" "<<kuohao[i].down<<" "<<kuohao[i].ti<<endl; int i=0; map<string,int> mp; while(i<l) //对每个元素进行计数 { while(i<l && !(formula[i]>='A' && formula[i]<='Z')) i++; string ch=""; int num=1; if (formula[i]>='A' && formula[i]<='Z') { ch+=formula[i]; i++; while(i<l && formula[i]>='a' && formula[i]<='z') { ch+=formula[i]; i++;} } if (i<l && formula[i]>='0' && formula[i]<='9') { num=formula[i]-'0'; i++; while(i<l && formula[i]>='0' && formula[i]<='9') {num=num*10+formula[i]-'0'; i++;} } for(int ii=0;ii<kuohao.size();ii++) { node p=kuohao[ii]; if(i-1>p.up && i-1 <p.down) num=num*p.ti; } if (mp.find(ch)!=mp.end()) mp[ch]+=num; else mp[ch]=num; } string res=""; /* nodee a[1005]; int k=0; for(auto ii: mp) { a[k].ch=ii.first; a[k++].ti=ii.second; } //sort(a,a+k,cmp); for(int i=0;i<k;i++) { res+=a[i].ch; if (a[i].ti>1) res+=to_string(a[i].ti); }*/ for(auto ii: mp) # 发现map的键值就是从小到大有序的。 { res+=ii.first; if(ii.second>1) res+=to_string(ii.second); } return res; } };
当我不知道map的键值是有序的情况下：效率极高，耗时0ms，打败100%用户，虽然代码长了不少。
class Solution { public: struct nodee{ string ch; int ti; }; static bool cmp(nodee a,nodee b) //关键的static，不然报错 { return a.ch<b.ch; } string countOfAtoms(string formula) { struct node { int up,down,ti; node(int a,int b,int c){up=a; down=b; ti=c;} }; vector<node> kuohao; stack<int> st; int l=formula.length(); for(int i=0;i<l;i++) { if(formula[i]=='(') {st.push(i); continue;} if(formula[i]==')') { int k=i+1; int s=0; if(formula[k]>='0' && formula[k]<='9') { while(k<l && formula[k]>='0' && formula[k]<='9') { s=s*10+formula[k]-'0'; k++; } } else s=1; kuohao.push_back(node(st.top(),i,s)); st.pop(); } } //for(int i=0;i<kuohao.size();i++) //cout<<kuohao[i].up<<" "<<kuohao[i].down<<" "<<kuohao[i].ti<<endl; int i=0; map<string,int> mp; while(i<l) { while(i<l && !(formula[i]>='A' && formula[i]<='Z')) i++; string ch=""; int num=1; if (formula[i]>='A' && formula[i]<='Z') { ch+=formula[i]; i++; while(i<l && formula[i]>='a' && formula[i]<='z') { ch+=formula[i]; i++;} } if (i<l && formula[i]>='0' && formula[i]<='9') { num=formula[i]-'0'; i++; while(i<l && formula[i]>='0' && formula[i]<='9') {num=num*10+formula[i]-'0'; i++;} } for(int ii=0;ii<kuohao.size();ii++) { node p=kuohao[ii]; if(i-1>p.up && i-1 <p.down) num=num*p.ti; } if (mp.find(ch)!=mp.end()) mp[ch]+=num; else mp[ch]=num; } string res=""; nodee a[1005]; int k=0; for(auto ii: mp) { a[k].ch=ii.first; a[k++].ti=ii.second; } sort(a,a+k,cmp); for(int i=0;i<k;i++) { res+=a[i].ch; if (a[i].ti>1) res+=to_string(a[i].ti); } /*for(auto ii: mp) { res+=ii.first; if(ii.second>1) res+=to_string(ii.second); }*/ return res; } };