class Solution {
public:
    bool isDigit(char ch) {
        return ch >= '0' && ch <= '9';
    }
    bool isCapital(char ch) {
        return (ch >= 'A' && ch <= 'Z');
    }
    bool isSmall(char ch) {
        return ch >= 'a' && ch <= 'z';
    }
    string toString(int x) {
        if(x == 0) return "0";
        string s;
        while(x) {
            s.push_back( (x%10) + '0');
            x /= 10;
        }
        reverse(s.begin(), s.end());
        return s;
    }

    void Merge(unordered_map<string,int> &a, unordered_map<string,int> &b) {
        for(auto itr : b) {
            a[itr.first] += itr.second;
        }
    }

    void multiply(stack<unordered_map<string,int>> &stk, int mul) {
        for(auto &itr : stk.top()) {
            itr.second *= mul;
        }
    }

    string countOfAtoms(string formula) {
        formula = "(" + formula + ")";
        stack<unordered_map<string,int>> stk;
        int n = formula.size();
        for(int i = 0; i < n; i++) {
            if(formula[i] == ')') {
                auto t0 = stk.top();
                stk.pop();
                while(!stk.top().empty()) {
                    auto t1 = stk.top();
                    stk.pop();
                    Merge(t0, t1);
                }
                stk.pop();
                stk.push(t0);
            }
            else if(formula[i] == '(') {
                stk.push(unordered_map<string,int>());
            }
            else if(isCapital(formula[i])) {
                string symbol;
                symbol.push_back(formula[i]);
                ++i;
                while(isSmall(formula[i])) {
                    symbol.push_back(formula[i]);
                    ++i;
                }
                --i;
                unordered_map<string,int> t;
                t[symbol] = 1;
                stk.push(t);
            }
            else if(isDigit(formula[i])) {
                int number = 0;
                while(isDigit(formula[i])) {
                    number = 10*number + formula[i]-'0';
                    ++i;
                }
                --i;
                multiply(stk, number);
            }
        }
        vector<pair<string,int>> res;
        for(auto itr : stk.top()) {
            res.push_back({itr.first, itr.second});
        }
        sort(res.begin(), res.end());
        string ans;
        for(int i = 0; i < res.size(); i++) {
            ans += res[i].first;
            if(res[i].second > 1) ans += toString(res[i].second);
        }
        return ans;
    }
};