# O(n) time O(n) space C++ iterative solution using stack + map

• ``````class Solution {
public:
string countOfAtoms(string f) {
int fact = 1, i = f.length()-1, local_fact = 1; // traverse string from backward
stack<int> s;
map<string, int> m;
string pre = "", ans;
while (i >= 0) {
if (isupper(f[i])) { // upper case means we've got one complete element
pre = f[i] + pre;
m[pre] += local_fact * fact;
pre = "";
local_fact = 1;
i--;
}
else if (islower(f[i])) { // we continue till we encounter upper case
pre = f[i] + pre;
while (islower(f[--i]))
pre = f[i] + pre;
}
else if (isdigit(f[i])) { // we continue till we get complete number
local_fact *= (f[i] - '0');
int j = 1;
while (isdigit(f[--i])) {
local_fact += (f[i] - '0') * pow(10, j++);
}
}
else if (f[i] == ')') { // closing brace, items to it's left are multiplied by fact; deep by 1 level
s.push(local_fact);
fact *= local_fact;
local_fact = 1;
i--;
}
else if (f[i] == '(') { // coming op one level, discard factor attributed to it
fact /= s.top();
s.pop();
i--;
}
}
for (auto kv : m) {
ans +=  kv.first;
if (kv.second > 1)
ans += to_string(kv.second);
}
return ans;
}
};
``````

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