/*
 * @lc app=leetcode id=726 lang=cpp
 *
 * [726] Number of Atoms
 * T(n) = O(N)
 * S(n) = O(N)
 */
class Solution
{
public:
    string countOfAtoms(string f)
    {
        stack<map<string, int>> st;
        map<string, int> cur;
        int i = 0;
        while (i < f.size())
        {
            if (f[i] == '(')
            {
                processLeftBracket(cur, st, i);
            }
            else if (f[i] == ')')
            {
                processRightBracket(i, f, cur, st);
            }
            else
            {
                processCount(i, f, cur);
            }
        }
        string ans;
        for (auto p : cur)
        {
            ans += p.first;
            if (p.second > 1)
                ans += to_string(p.second);
        }

        return ans;
    }

private:
    void processLeftBracket(map<string, int> &cur,
                            stack<map<string, int>> &st,
                            int &i)
    {
        st.push(move(cur));
        cur = map<string, int>();
        ++i;
    }

    void processRightBracket(int &i,
                             string f,
                             map<string, int> &cur,
                             stack<map<string, int>> &st)
    {
        int j = i + 1;
        int num = 0;
        while (j < f.size() && isdigit(f[j]))
            num = num * 10 + (f[j++] - '0');
        num = max(num, 1);
        for (auto p : cur)
            st.top()[p.first] += p.second * num;
        cur = move(st.top());
        st.pop();
        i = j;
    }

    void processCount(int &i,
                      string f,
                      map<string, int> &cur)
    {
        int j = i + 1;
        int num = 0;
        while (j < f.size() && f[j] >= 'a' && f[j] <= 'z')
            ++j;
        auto name = f.substr(i, j - i);
        while (j < f.size() && isdigit(f[j]))
            num = num * 10 + (f[j++] - '0');
        num = max(num, 1);
        cur[name] += num;
        i = j;
    }
};