Elegant & Clean C++ Iterative Solution Using stack ( via Reverse the Formula)


  • 3
    S

    Aha, I think this is by far the cleanest solution. The idea is very simple, reverse the formula and iteratively process the formula with the help of a stack recording the multiplication factor of the current element.

    The code is quite self-explanatory. Hope it helps!

    Updated:

    Special thanks to @xmeng525 to make it more clear.

    class Solution {
    public:
        string countOfAtoms(string formula) {
            std::map<string, int> stats;
            std::reverse(formula.begin(), formula.end());
            compute(formula, stats);
            string result;
            
            for (auto& kv : stats) {
                result += kv.first;
                if (kv.second > 1) {
                    result += std::to_string(kv.second);
                }
            }
            return result;
        }
        
    private: // K4(ON(SO3)2)2
        void compute(string& formula, std::map<string, int>& stats) {
            int n = formula.size();
            
            std::stack<int> stk; // factor
            stk.push(1);
            
            string elem; // chemical element, e.g., C, N, O, Na, Mg, Al, etc.
            int factor = 1; // number of this element, default to 1 if not otherwise specified
            
            for (int i = 0; i < n; ++i) {
                auto& c = formula[i];
                if (isdigit(c)) { // E.g., original 312 was reverse to 213.
                    int val = 0, expo = 1;
                    do {
                        val += (c - '0') * expo;
                        ++i; expo *= 10;
                    } while (isdigit(c = formula[i]));
                    factor = val; // explicit number of this element
                    
                    i -= 1;
                } else if (c == ')') { 
                    stk.push(factor * stk.top());
                    factor = 1; //            Al(OH)3
                } else if (c >= 'A' && c <= 'Z') {
                    elem += c;
                    std::reverse(elem.begin(), elem.end());
                    stats[elem] += factor * stk.top();
                    factor = 1;
                    elem.clear();
                } else if (c >= 'a' && c <= 'z') {
                    elem += c;
                } else { // (c == '(') {  
                    stk.pop();  // Ca(OH)2
                    // elem.clear();
                } 
            }   
        }
    };
    

  • 0
    S
    This post is deleted!

  • 0
    X

    Hi,

    Thank you very much for your solution. It's very clear!

    By the way, I find that there is no need to clear the 'elem' in the final 'else'.
    i.e.

    else { // (c == '(') {  
                    stk.pop();  // Ca(OH)2
                    elem.clear();
                } 
    

    can be simplified to

    else { // (c == '(') {  
                    stk.pop();  // Ca(OH)2
                }
    

    Also,

    else if (c >= 'A' && c <= 'Z') {
                    elem += c;
                    std::reverse(elem.begin(), elem.end());
                    cout << elem << ", count=" << stk.top() << "\n";
                    stats[elem] += factor * stk.top();
                    factor = 1;
                    elem.clear();
                }
    

    can be simplified to

    else if (c >= 'A' && c <= 'Z') {
                    elem = c + elem;
                    cout << elem << ", count=" << stk.top() << "\n";
                    stats[elem] += factor * stk.top();
                    factor = 1;
                    elem.clear();
                }
    

    to avoid using the reverse().


  • 0
    S

    @xmeng525 Thank you for pointing it out. Clearing the 'elem' was already done by "previous" uppercase letters in the final 'else'.

    Have updated the solution.


  • 0
    D

    I thought of using reverse too, below is my solution (longer but I think more explicit):

    class Solution {
    public:
        string countOfAtoms(string formula) {
            stack<map<string, int>> mpSt;
            stack<int> intSt;
            map<string, int> curr;
            string element = "";
            int factor = 1, n = formula.size();
            reverse(formula.begin(), formula.end());
            
            for (int i = 0; i < n; i++) {
                char c = formula[i];
                if (isdigit(c)) {
                    string factorStr = "";
                    while (i < n && isdigit(formula[i])) {
                        factorStr += formula[i++];
                    }
                    reverse(factorStr.begin(), factorStr.end());
                    factor = stoi(factorStr);
                    i--;
                }
                else if (c == ')') {
                    mpSt.push(curr);
                    intSt.push(factor);
                    curr.clear();
                    factor = 1;
                    element = "";
                }
                else if (c == '(') {
                    curr = mergeDict(mpSt.top(), curr, intSt.top());
                    mpSt.pop(); intSt.pop();
                }
                else if (isupper(c)) {
                    element = c + element;
                    curr[element] += factor;
                    element = "";
                    factor = 1;
                }
                else element += c;
            }
            string res = "";
            for (auto it = curr.begin(); it != curr.end(); it++) {
                res += it -> first + (it -> second == 1 ? "" : to_string(it -> second));
            }
            return res;
        }
        
        map<string, int> mergeDict(map<string, int> prev, map<string, int> curr, int n) {
            for (auto it = curr.begin(); it != curr.end(); it++) {
                prev[it -> first] += (it -> second) * n;
            }
            return prev;
        };
    };
    

Log in to reply
 

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