726. 原子的數(shù)量

編譯原理語法分析中的遞歸下降

class Solution {
public:
    map<string, int> dfs(int &u, string str) {
        int i, n = str.size(), left = 0;
        map<string, int> curmp;

        for (i = u; i < str.size(); i++) {
            if (str[i] == '(') left++;
            else if (str[i] == ')')left--;
            if (!left) {
                i++;
                break;
            }
        }

        int len = i - 1;

        int endnum = 0;
        if (i == n || !isdigit(str[i])) endnum = 1;
        else {
            string dig;
            while (i < n && isdigit(str[i])) {
                dig += str[i];
                i++;
            }
            endnum = stoi(dig);
        }

        int endpos = i - 1;

        for (i = u + 1; i < len; i++) {
            if (isalpha(str[i])) {
                int j = i + 1;
                if (j < n && islower(str[j]))j++;
                string name = str.substr(i, j - i);
                if (j == n || !isdigit(str[j])) {
                    curmp[name] += 1;
                } else {
                    string dig;
                    while (j < n && isdigit(str[j])) {
                        dig += str[j];
                        j++;
                    }
                    int num = stoi(dig);
                    curmp[name] += num;
                }
                i = j - 1;
            } else if (str[i] == '(') {
                int pos = i;
                auto tmp = dfs(pos, str);
                for (auto p:tmp) {
                    curmp[p.first] += p.second;
                }
                i = pos;
            }
        }

        u = endpos;
        for (auto &p:curmp) {
            p.second *= endnum;
        }
        return curmp;
    }

    string countOfAtoms(string str) {
        str = "(" + str + ")";
        int u = 0;
        auto mp = dfs(u, str);
        string res;
        for (auto p:mp) {
            res += p.first;
            if (p.second > 1)res += to_string(p.second);
        }
        return res;
    }
};