# Elegant & Clean C++ Iterative Solution Using stack ( via Reverse the Formula)

• Aha, I think this is by far the cleanest solution. The idea is very simple, reverse the formula and iteratively process the formula with the help of a stack recording the multiplication factor of the current element.

The code is quite self-explanatory. Hope it helps!

Updated:

Special thanks to @xmeng525 to make it more clear.

``````class Solution {
public:
string countOfAtoms(string formula) {
std::map<string, int> stats;
std::reverse(formula.begin(), formula.end());
compute(formula, stats);
string result;

for (auto& kv : stats) {
result += kv.first;
if (kv.second > 1) {
result += std::to_string(kv.second);
}
}
return result;
}

private: // K4(ON(SO3)2)2
void compute(string& formula, std::map<string, int>& stats) {
int n = formula.size();

std::stack<int> stk; // factor
stk.push(1);

string elem; // chemical element, e.g., C, N, O, Na, Mg, Al, etc.
int factor = 1; // number of this element, default to 1 if not otherwise specified

for (int i = 0; i < n; ++i) {
auto& c = formula[i];
if (isdigit(c)) { // E.g., original 312 was reverse to 213.
int val = 0, expo = 1;
do {
val += (c - '0') * expo;
++i; expo *= 10;
} while (isdigit(c = formula[i]));
factor = val; // explicit number of this element

i -= 1;
} else if (c == ')') {
stk.push(factor * stk.top());
factor = 1; //            Al(OH)3
} else if (c >= 'A' && c <= 'Z') {
elem += c;
std::reverse(elem.begin(), elem.end());
stats[elem] += factor * stk.top();
factor = 1;
elem.clear();
} else if (c >= 'a' && c <= 'z') {
elem += c;
} else { // (c == '(') {
stk.pop();  // Ca(OH)2
// elem.clear();
}
}
}
};
``````

• This post is deleted!

• Hi,

Thank you very much for your solution. It's very clear!

By the way, I find that there is no need to clear the 'elem' in the final 'else'.
i.e.

``````else { // (c == '(') {
stk.pop();  // Ca(OH)2
elem.clear();
}
``````

can be simplified to

``````else { // (c == '(') {
stk.pop();  // Ca(OH)2
}
``````

Also,

``````else if (c >= 'A' && c <= 'Z') {
elem += c;
std::reverse(elem.begin(), elem.end());
cout << elem << ", count=" << stk.top() << "\n";
stats[elem] += factor * stk.top();
factor = 1;
elem.clear();
}
``````

can be simplified to

``````else if (c >= 'A' && c <= 'Z') {
elem = c + elem;
cout << elem << ", count=" << stk.top() << "\n";
stats[elem] += factor * stk.top();
factor = 1;
elem.clear();
}
``````

to avoid using the reverse().

• @xmeng525 Thank you for pointing it out. Clearing the 'elem' was already done by "previous" uppercase letters in the final 'else'.

Have updated the solution.

• I thought of using reverse too, below is my solution (longer but I think more explicit):

``````class Solution {
public:
string countOfAtoms(string formula) {
stack<map<string, int>> mpSt;
stack<int> intSt;
map<string, int> curr;
string element = "";
int factor = 1, n = formula.size();
reverse(formula.begin(), formula.end());

for (int i = 0; i < n; i++) {
char c = formula[i];
if (isdigit(c)) {
string factorStr = "";
while (i < n && isdigit(formula[i])) {
factorStr += formula[i++];
}
reverse(factorStr.begin(), factorStr.end());
factor = stoi(factorStr);
i--;
}
else if (c == ')') {
mpSt.push(curr);
intSt.push(factor);
curr.clear();
factor = 1;
element = "";
}
else if (c == '(') {
curr = mergeDict(mpSt.top(), curr, intSt.top());
mpSt.pop(); intSt.pop();
}
else if (isupper(c)) {
element = c + element;
curr[element] += factor;
element = "";
factor = 1;
}
else element += c;
}
string res = "";
for (auto it = curr.begin(); it != curr.end(); it++) {
res += it -> first + (it -> second == 1 ? "" : to_string(it -> second));
}
return res;
}

map<string, int> mergeDict(map<string, int> prev, map<string, int> curr, int n) {
for (auto it = curr.begin(); it != curr.end(); it++) {
prev[it -> first] += (it -> second) * n;
}
return prev;
};
};
``````

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