[C++] Recursive Parser

• ``````/**
* formula :
*     unit[]
* unit :
*     atom (count)
*     '(' formula ')' count
* atom :
*    upper (lower[])
* count :
*    digit[]
* -----------------------------
* upper : '[A-Z]'
* lower : '[a-z]'
* digit : '[0-9]'
*/
``````
``````class Solution {
public:
string countOfAtoms(string formula) {
string output;
const int n = formula.size();
int i = 0;
map<string, int> counts = parseFormula(formula, i);
for (pair<string, int> p : counts) {
output += p.first;
if (p.second > 1) output += to_string(p.second);
}
return output;
}

private:
map<string, int> parseFormula(string& s, int& i) {
map<string, int> counts;
const int n = s.size();
while (i < n && s[i] != ')') {
map<string, int> cnts = parseUnit(s, i);
merge(counts, cnts, 1);
}
return counts;
}

map<string, int> parseUnit(string& s, int& i) {
map<string, int> counts;
const int n = s.size();
if (s[i] == '(') {
map<string, int> cnts = parseFormula(s, ++i); // ++i for '('
int digits = parseDigits(s, ++i); // ++i for ')'
merge(counts, cnts, digits);
}
else {
int i0 = i++; // first letter
while (i < n && islower(s[i])) { i++; }
string atom = s.substr(i0, i - i0);
int digits = parseDigits(s, i);
counts[atom] += digits;
}
return counts;
}

int parseDigits(string& s, int& i) {
int i1 = i;
while (i < s.size() && isdigit(s[i])) { i++; }
int digits = i == i1 ? 1 : stoi(s.substr(i1, i - i1));
return digits;
}

void merge(map<string, int>& counts, map<string, int>& cnts, int times) {
for (pair<string, int> p : cnts) counts[p.first] += p.second * times;
}
};
``````

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