C++ | String processing L-R and keeping count of nested string
We iterate the string from left to right. and Also while traversing, we keep the built string so far. If any given point we encounter consecutive digits, we pro
We iterate the string from left to right. and Also while traversing, we keep the built string so far. If any given point we encounter consecutive digits, we process them and then put that parsed string as the count of previous string.\n\nIf we encounter any opening parantheses `(`, we try to find the answer recursively and from the recursion call we return the strings and their count. We try to process the current depth till we encounter the next `)`, after encountering `)` we either try to find the consecutive digits or end the string here. If not found, we return the currently built map to the parent recursion call and add these values with their count into the map of parent recursion call. \n\n```cpp\nclass Solution {\npublic:\n    bool isDigit(char ch) {\n        return (ch >= \'0\' && ch <= \'9\');\n    }\n    \n    unordered_map<string, int> dfs(int &pos, string &formula) {\n        int n = formula.size();\n        if (pos >= n) {\n            return {};\n        }\n        unordered_map<string, int> curMap;\n        string prev = "";\n        while (pos < n) {\n            if (formula[pos] == \'(\') {\n                if (prev.size() > 0) {\n                    curMap[prev] += 1;\n                    prev = "";\n                }\n                ++pos;\n                unordered_map<string, int> retMap = dfs(pos, formula);\n                for (pair<string, int> entry: retMap) {\n                    curMap[entry.first] += entry.second;   \n                }\n            } else if (formula[pos] == \')\') {\n                if (prev.size() > 0) {\n                    curMap[prev] += 1;\n                    prev = "";\n                }\n                int val = 0;\n                //This block is to check If there is any \n                //digit available\n                if (pos + 1 < n) {\n                    ++pos;\n                    while (pos < n) {\n                        if (isDigit(formula[pos])) {\n                            val = val * 10 + formula[pos] - \'0\';\n                        } else break;\n                        ++pos;\n                    }\n                }\n                val = val > 0? val : 1;\n                for (auto &entry: curMap) {\n                    entry.second *= val;\n                }\n                return curMap;\n            } else {\n                if (isDigit(formula[pos])) {\n                    int val = 0;\n                    while (pos < n) {\n                        if (isDigit(formula[pos]))\n                            val = val * 10 + formula[pos] - \'0\';\n                        else break;\n                        ++pos;\n                    }\n                    if (prev.size() > 0) {\n                        curMap[prev] += val;\n                        prev = "";\n                    }                \n                } else {\n                    if (prev.size() > 0 && isupper(formula[pos])) {\n                        curMap[prev] += 1;\n                        prev = "";\n                    }\n                    prev += formula[pos];\n                    ++pos;\n                }\n            }\n        }\n        if (prev.size() > 0) {\n            curMap[prev] += 1;\n        }\n        return curMap;\n    }\n    \n    string countOfAtoms(string formula) {\n        int pos = 0;\n        unordered_map<string, int> f = dfs(pos, formula);\n        vector<string> res;\n        for (pair<string, int> entry: f) {\n            res.push_back(entry.first);\n        }\n        sort(begin(res), end(res), [&] (const string &a, const string &b) {\n            return a < b;\n        });\n        string result = "";\n        for (string s: res) {\n            result += s;\n            if (f[s] > 1)\n                result += to_string(f[s]);\n        }\n        return result;\n    }\n};\n```
[]