C++ solution using a parse tree


  • 0
    D

    After attempting (and failing with) a one-pass solution through the string, I decided that the most reliable way to do this would be to produce a parse tree first, then translate that into the map to count the atoms, and then print the map. I put each of those tasks into separate subroutines; hopefully others will find this this decently readable.

    class Solution {
    public:
        
        struct Formula {
            string elem;
            int count;
            vector<Formula> v;
            Formula() : count(0) {}
        };
        
        string printResult(map<string,int> &resultMap) {
            ostringstream os;
            map<string,int>::iterator it = resultMap.begin();
            while( it != resultMap.end() ) {
                os << it->first;
                if (it->second > 1) os << it->second;
                ++it;
            }
            return os.str();
        }
        
        void ptree2map( vector<Formula> &parseTree, map<string,int> &resultMap, int multiplier ) {
            for( Formula &f : parseTree ) {
                if (f.elem.empty()) {
                    ptree2map( f.v, resultMap, f.count*multiplier);
                }
                else {
                    map<string,int>::iterator it = resultMap.find(f.elem);
                    if (it == resultMap.end()) resultMap[f.elem] = 0;
                    resultMap[f.elem] += f.count * multiplier;
                }
            }
        }
        
        void parse(string formula, int &i, vector<Formula> &parseTree) {
            string elem;
            int count = 0;
            parseTree.resize(1);
            while( i < formula.length()) {
                char c = formula[i];
                if (c == '(') {
                    parseTree.back().elem = elem;
                    parseTree.back().count = (count == 0) ? 1 : count;
                    parseTree.resize(parseTree.size()+1);
                    elem = "";
                    count = 0;
                    ++i;
                    parse(formula,i,parseTree.back().v);
                }
                else if (c == ')') {
                    parseTree.back().elem = elem;
                    parseTree.back().count = (count == 0) ? 1 : count;
                    parseTree.resize(parseTree.size()+1);
                    ++i;
                    return;
                }
                else if ('0' <= c && c <= '9') {
                    count = count*10 + (c-'0');
                    ++i;
                }
                else if ('a' <= c && c <= 'z') {
                    // continuation of elem name
                    elem += c;
                    ++i;
                }
                else if ('A' <= c && c <= 'Z') {
                    // new elem starting.
                    parseTree.back().elem = elem;
                    parseTree.back().count = (count == 0) ? 1 : count;
                    parseTree.resize(parseTree.size()+1);
                    elem = c;
                    count = 0;
                    ++i;
                }
            }
            parseTree.back().elem = elem;
            parseTree.back().count = (count == 0) ? 1 : count;
            parseTree.resize(parseTree.size()+1);
        }
        
        string countOfAtoms(string formula) {
            vector<Formula> parseTree;
            int i=0;
            parse(formula,i,parseTree);
            map<string,int> resultMap;
            ptree2map(parseTree,resultMap,1);
            return printResult(resultMap);
        }
    };
    

Log in to reply
 

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