[C++] Recursive Parser


  • 5
    /**
     * formula :
     *     unit[]
     * unit :
     *     atom (count)
     *     '(' formula ')' count
     * atom :
     *    upper (lower[])
     * count :
     *    digit[]
     * -----------------------------
     * upper : '[A-Z]'
     * lower : '[a-z]'
     * digit : '[0-9]'
     */
    
    class Solution {
    public:
        string countOfAtoms(string formula) {
            string output;
            const int n = formula.size();
            int i = 0;
            map<string, int> counts = parseFormula(formula, i);
            for (pair<string, int> p : counts) {
                output += p.first;
                if (p.second > 1) output += to_string(p.second);
            }
            return output;
        }
    
    private:
        map<string, int> parseFormula(string& s, int& i) {
            map<string, int> counts;
            const int n = s.size();
            while (i < n && s[i] != ')') {
                map<string, int> cnts = parseUnit(s, i);
                merge(counts, cnts, 1);
            }
            return counts;
        }
    
        map<string, int> parseUnit(string& s, int& i) {
            map<string, int> counts;
            const int n = s.size();
            if (s[i] == '(') {
                map<string, int> cnts = parseFormula(s, ++i); // ++i for '('
                int digits = parseDigits(s, ++i); // ++i for ')'
                merge(counts, cnts, digits);
            }
            else {
                int i0 = i++; // first letter
                while (i < n && islower(s[i])) { i++; }
                string atom = s.substr(i0, i - i0);
                int digits = parseDigits(s, i);
                counts[atom] += digits;
            }
            return counts;
        }
    
        int parseDigits(string& s, int& i) {
            int i1 = i;
            while (i < s.size() && isdigit(s[i])) { i++; }
            int digits = i == i1 ? 1 : stoi(s.substr(i1, i - i1));
            return digits;
        }
    
        void merge(map<string, int>& counts, map<string, int>& cnts, int times) {
            for (pair<string, int> p : cnts) counts[p.first] += p.second * times;
        }
    };
    

Log in to reply
 

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