# [726. Number of Atoms] C++ AC Unordered_map + recursion

• This question is not hard, just a little bit of complex. You have to consider different cases.

``````class Solution {
public:
string countOfAtoms(string formula) {
int i = 0;
string s = '(' + formula + ')';
auto mp = dfs(formula, i);
vector<pair<string,int>> vec;
for(auto m : mp){
vec.push_back(m);
}
sort(vec.begin(), vec.end(), [](pair<string, int> a, pair<string, int> b){
return a.first < b.first;
});
string res = "";
for(auto v : vec){
res += v.first;
if(v.second > 1) res += to_string(v.second);
}
return res;
}

unordered_map<string, int> dfs(string formula, int& i){
unordered_map<string, int> mp;
while(i < formula.size()){
if(formula[i] == ')'){
i = i + 1;
int total = 0;
while(i < formula.size() && isdigit(formula[i])){total = total * 10 + formula[i++] - '0';}
if(total > 0) {for(auto m : mp){mp[m.first] = m.second * total;}}
break;
}else if(formula[i] == '('){
i++;
auto mp_2 = dfs(formula,i);
for(auto m : mp_2){
if(mp.find(m.first) == mp.end()) mp[m.first] = 0;
mp[m.first] += m.second;
}
}else{
string element = "";
int number = 0;
if(formula[i] - 'A' >= 0 && formula[i] - 'A' < 26){
element += formula[i];
i++;
while(i < formula.size() && formula[i] - 'a' >= 0 && formula[i] - 'a' < 26){element += formula[i++];}
if(i < formula.size() && isdigit(formula[i])){
while(i < formula.size() && isdigit(formula[i])) {number = number * 10 + formula[i++] - '0';}
}else{
number = 1;
}
}
if(mp.find(element) == mp.end()) mp[element] = 0;
mp[element] += number;
}
}
return mp;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.