题目描述

给定一个化学分子表达式，带有’(‘ 与 ‘)’ 求出每个元素对应的总个数.

样例

Input: 
formula = "H2O"
Output: "H2O"
解释： 
元素个数： {'H': 2, 'O': 1}.

Input: 
formula = "Mg(OH)2"
Output: "H2MgO2"
解释: 
元素个数： {'H': 2, 'Mg': 1, 'O': 2}.

算法1

(递归) $O(n)$

一个表达式简称为expr.
expr开头有4种情况

1 expr -> (expr).... 以’(‘ 开头
1.1 expr->(expr1)num expr2 expr3 … exprn
1.2 expr->(expr1) expr2 expr3 … exprn

2 expr -> item expr2 expr3 … exprn 以 某个元素开头
2.1 item-> token num
2.2 item-> token

3 expr 开头 为) 表明这个表达式已经读取完毕.

4 expr读取到达结尾.

那么按照上述表述递归就可。
我们每次查看当前字符，如果是’(‘ 那么按照1处理，是字符按照2处理，如果是’)’那么直接返回当前这一层的结果’.
每一个递归表示的含义为：处理完当前这一级的表达式返回的结果.

例如：
以Mg(OH)2为例
第一层递归先读取Mg 接下来调用 get_expr求解OH。
进入第二层递归，
第二层递归OH在运算到)时返回。
第一层递归按照末尾数字来乘以结果。

时间复杂度分析：只需要扫描一遍，因此复杂度只有O(n)

C++ 代码

class Solution {
public:
    string countOfAtoms(string formula) {
        int pos = 0;
        unordered_map<string,int> res = get_expr(formula,pos);
        vector<pair<string,int>> tep;
        for (auto iter = res.begin();iter!=res.end();++iter){
            tep.push_back(make_pair(iter->first,iter->second));
        }
        sort(tep.begin(),tep.end());

        string str_res = "";
        for (auto iter = tep.begin();iter!=tep.end();++iter){
            str_res += iter->first+ (iter->second==1? "": to_string(iter->second));
        }

        return str_res;
    }

    void add(unordered_map<string,int> &input, const string &right, int num ){
        if (input.count(right))
            input[right] += num;
        else
            input[right] = num;
    }


    unordered_map<string,int> get_expr(string &formula, int & pos){
        unordered_map<string,int> res;
        while(pos<formula.length()){
            if (formula[pos] == '('){
                ++pos;
                unordered_map<string,int> next = get_expr(formula,pos);
                ++pos;
                if (pos< formula.length() && is_num(formula[pos])){


                    int num = get_num(formula,pos);
                    for(auto iter = next.begin();iter!=next.end();++iter){
                        iter->second *= num;
                    }
                }
                for (auto iter =  next.begin();iter!=next.end();++iter){
                    add(res,iter->first,iter->second);
                }

            }
            else if (formula[pos] == ')'){
                break;
            }
            else {
                string token = get_token(formula,pos);
                int num = 1;
                if (pos < formula.length() && is_num(formula[pos]))
                    num = get_num(formula,pos);
                add(res,token,num);
            }
        }

        return res;
    }

    int get_num(string & formula, int &pos){
        string res = formula.substr(pos++,1);


        while(pos<formula.length() && is_num(formula[pos]))
            res = res + formula[pos++];
        return stoi(res);
    }

    string get_token(string & formula,int &pos){
        string res  = formula.substr(pos++,1);

        while(pos<formula.length() && is_alpha(formula[pos]) )
            res = res + formula[pos++];

        return res;
    }

    bool is_num(char c){
        if (c>='0' && c<='9') return true;
        return false;
    }

    bool is_alpha(char c){
        if (c>='a' && c<='z') return true;
        return false;

    }

};