[栈递归]LeetCode726.原子的数量

题目描述

给出化学式，计算化学式中所有出现原子以及原子个数，字典序升序输出
一个括号中的化学式和数字（可选择性添加）也是化学式。例如 (H2O2) 和 (H2O2)3 是化学式。

思路

看到括号典型的递归，用栈写递归更加方便一点。
顺便可以学习一下C++ map和stack的用法
map的特性：

1. key值不能重复，如果是数字或者string char等会自动排序非常适用这道题


2. log级复杂的增删改以及搜索


3. 可以直接用数组方式进行检索并对value值操作

具体思路：
非括号内的原子直接进入答案map
括号内原子进入栈，碰到右括号则括号内原子个数乘以相应数字，再放回栈
如果栈内没括号了那么栈内原子进入map
可以再写一个pair数组维护，将栈中元素弹出存入数组中，碰到栈中左括号停止，此时如果栈空，那么数组所有元素进入map，否则全部入栈
元素进入map不需要find，直接map[string]+=num即可

代码

bool isbig(char a){return a>='A'&&a<='Z';}bool issmall(char a){return a>='a'&&a<='z';}bool isnum(char a){return a>='0'&&a<='9';}int tonum(string a){if(a.length()==0)return 1;int res=0;for(int i=0;i<a.length();i++){res=res*10+a[i]-'0';}return res;}string countOfAtoms(string formula) {stack<pair<string,int>>q;stack<pair<string,int>>tmpstack;pair<string,int>tmppair;map<string,int>ans;int type=1,n=formula.length();string tmpstr="";string tmpnum="";for(int i=0;i<n;i++){char c=formula[i];if(isbig(c)){tmpstr+=c;i++;c=formula[i];while(issmall(c)&&i<n){tmpstr+=c;i++;c=formula[i];}while(isnum(c)&&i<n){tmpnum+=c;i++;c=formula[i];}if(type==1)ans[tmpstr]+=tonum(tmpnum);else q.push({tmpstr,tonum(tmpnum)});tmpstr.clear();tmpnum.clear();i--;}else if(c=='('){q.push({"",0});type=2;}else if(c==')'){i++;c=formula[i];while(isnum(c)&&i<n){tmpnum+=c;i++;c=formula[i];}int x=tonum(tmpnum);tmpnum.clear();while(!q.empty()){tmppair=q.top();q.pop();if(tmppair.second==0)break;tmpstack.push({tmppair.first,tmppair.second*x});}if(!q.empty()){while(!tmpstack.empty()){q.push(tmpstack.top());tmpstack.pop();}}else{while(!tmpstack.empty()){tmppair=tmpstack.top();tmpstack.pop();ans[tmppair.first]+=tmppair.second;}type=1;}i--;}}string res="";for(auto it:ans)if(it.second!=1)res=res+it.first+to_string(it.second);else res=res+it.first;return res;}