每日一题之原子的数量

1.对应letecode连接：

726. 原子的数量 - 力扣（LeetCode）

2.题目描述：

 3.解题思路

这道题看起来很复杂，涉及到了括号嵌套的问题。博主之前写过一篇关于括号嵌套问题的博客，个人认为那种方法解决这种问题真的非常的好用在这里给出链接：http://t.csdn.cn/uHr26

下面我们就用递归来看看这种括号嵌套问题如何来实现的。大概的流程如下：

• 我们从前往后开始撸串，遇到左括号调用递归让其把递归处理完的结果告诉我们并且要告诉我你递归的时候算到了那个位置。然后我接着这个位置继续往后撸串。
• 递归函数遇到右括号了就需要将结果和自己算到了那个位置返回给调用他的地方
• 收到递归函数的返回值之后需要继续往后遍历看有没有数字如果有数字需要将递归函数返回的结果中字母出现的次数进行翻倍处理
• 遇到的是普通原子我们首先提取他的名称然后再提取他的倍率将其加入到有序表当中

下面我们以字符串"Mg(OH)2K2"为列。注意实际当中可能没有这个化学式在这里只是为了方便举例子而已：

首先我们调用f函数从前往后撸字符串撸着撸着到了2位置遇到了左括号那么我们就调用递归让子函数进行处理：

 

然后f2这个函数就从3位置开始继续撸字符串到了5位置发现到了右括号。 将自己撸到位置也就是5位置和结果返回给调用给他的老大。f2就根f1说你给你我的任务我已经完成了，结果是这个。f1收到之后从f2返回的结果当中的位置从下一个位置继续往后看有没有数字如果有将f2返回的结果中的字符出现的次数翻倍然后在合并到自己的cntMap当中即可.然后继续往后撸串

4.对应代码：

class Solution {
  public:
    struct Info {
        Info(mapint>& c, int e) {
            cntMap = move(c); //移动资源提供效率
            end = e;
        }
        mapint>cntMap; //用来统计词频
        int end;//计算到了哪里
    };
 
    string countOfAtoms(string formula) {
        auto ret = process(formula, 0);
        string ans;
        for (auto& node : ret->cntMap) {
            ans += node.first;
            if (node.second > 1) {
                ans += to_string(node.second);
            }
        }
        return ans;
    }
    Info* process(const string& str, int index) {
 
        mapint>cnt; //用来统计词频
        while (index < str.size() && str[index] != ')') {
            if (str[index] == '(') { //遇到了左括号了
                //开始进行递归
                Info* RetInfo = process(str, index + 1);
                int num = 0; //看后面是否有数字
                index = RetInfo->end + 1;
                while (index < str.size() && str[index] >= '0' && str[index] <= '9') {
                    num = num * 10 + str[index++] - '0';
                }
                //看是否需要扩大倍率
                auto& tmpMap = RetInfo->cntMap;
                for (auto& node : tmpMap) {
                    node.second *= (num == 0 ? 1 : num);
                    cnt[node.first] += node.second;
                }
                delete RetInfo;
 
            } else {
                //遇到的是字符和数字
                string name = string(1, str[index++]);
                //原子第一个字母是大写
                while (index < str.size() && str[index] >= 'a' && str[index] <= 'z') {
                    name += str[index++];
                }
                int num = 0; //用来统计原子的倍率
                while (index < str.size() && str[index] >= '0' && str[index] <= '9') {
                    num = num * 10 + str[index++] - '0';
                }
 
                cnt[name] += (num > 0 ? num : 1); //添加原子的倍率
 
 
            }
        }
        return new Info(cnt, index);
    }
 
};