# C++ solution using a parse tree

• After attempting (and failing with) a one-pass solution through the string, I decided that the most reliable way to do this would be to produce a parse tree first, then translate that into the map to count the atoms, and then print the map. I put each of those tasks into separate subroutines; hopefully others will find this this decently readable.

``````class Solution {
public:

struct Formula {
string elem;
int count;
vector<Formula> v;
Formula() : count(0) {}
};

string printResult(map<string,int> &resultMap) {
ostringstream os;
map<string,int>::iterator it = resultMap.begin();
while( it != resultMap.end() ) {
os << it->first;
if (it->second > 1) os << it->second;
++it;
}
return os.str();
}

void ptree2map( vector<Formula> &parseTree, map<string,int> &resultMap, int multiplier ) {
for( Formula &f : parseTree ) {
if (f.elem.empty()) {
ptree2map( f.v, resultMap, f.count*multiplier);
}
else {
map<string,int>::iterator it = resultMap.find(f.elem);
if (it == resultMap.end()) resultMap[f.elem] = 0;
resultMap[f.elem] += f.count * multiplier;
}
}
}

void parse(string formula, int &i, vector<Formula> &parseTree) {
string elem;
int count = 0;
parseTree.resize(1);
while( i < formula.length()) {
char c = formula[i];
if (c == '(') {
parseTree.back().elem = elem;
parseTree.back().count = (count == 0) ? 1 : count;
parseTree.resize(parseTree.size()+1);
elem = "";
count = 0;
++i;
parse(formula,i,parseTree.back().v);
}
else if (c == ')') {
parseTree.back().elem = elem;
parseTree.back().count = (count == 0) ? 1 : count;
parseTree.resize(parseTree.size()+1);
++i;
return;
}
else if ('0' <= c && c <= '9') {
count = count*10 + (c-'0');
++i;
}
else if ('a' <= c && c <= 'z') {
// continuation of elem name
elem += c;
++i;
}
else if ('A' <= c && c <= 'Z') {
// new elem starting.
parseTree.back().elem = elem;
parseTree.back().count = (count == 0) ? 1 : count;
parseTree.resize(parseTree.size()+1);
elem = c;
count = 0;
++i;
}
}
parseTree.back().elem = elem;
parseTree.back().count = (count == 0) ? 1 : count;
parseTree.resize(parseTree.size()+1);
}

string countOfAtoms(string formula) {
vector<Formula> parseTree;
int i=0;
parse(formula,i,parseTree);
map<string,int> resultMap;
ptree2map(parseTree,resultMap,1);
return printResult(resultMap);
}
};
``````

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