Iterative C++ using stack of stacks


  • 0
    F
    class Solution {
    public:
        string countOfAtoms(string formula) {
            map<string, int> myMap;
            stack<stack<pair<string, int>>> myStack;
            stack<pair<string, int>> currStack;
            for(int i=0; i<formula.size();) {
                if(isupper(formula[i])) {
                    string currAtom(1, formula[i]);
                    while(islower(formula[++i]))
                        currAtom += formula[i];
                    currStack.push(pair<string, int>(currAtom, 1));
                } else if(formula[i]==')') {
                    string::size_type sz = 0;
                    int number = (i+1 < formula.size() && isdigit(formula[i+1])) ? stoi(formula.substr(i+1), &sz) : 1;
                    i += sz+1;
                    stack<pair<string, int>>& topMyStack = myStack.top();
                    while(!currStack.empty()) {
                        pair<string, int> currStackTop = currStack.top();
                        topMyStack.push(pair<string, int>(currStackTop.first, currStackTop.second*number));
                        currStack.pop();
                    }
                    currStack = myStack.top();
                    myStack.pop();
                } else if(isdigit(formula[i])) {
                    int num = 0;
                    while(isdigit(formula[i]))
                        num = num*10 + formula[i++] - '0';
                    currStack.top().second =  num;
                } else if(formula[i]=='(') {
                    myStack.push(currStack);
                    currStack = stack<pair<string, int>>();
                    ++i;
                }
            }
            if(!currStack.empty())
                myStack.push(currStack);
            stack<pair<string, int>> topMyStack = myStack.top();
            while(!topMyStack.empty()) {
                myMap[topMyStack.top().first] += topMyStack.top().second;
                topMyStack.pop();
            }
            string result;
            for(auto it = myMap.begin(); it != myMap.end(); ++it)
                result += it->first + ((it->second == 1) ? "" : to_string(it->second));
            return result;
        }
    };
    

Log in to reply
 

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