726. 原子的数量

给定一个化学式formula（作为字符串），返回每种原子的数量。

原子总是以一个大写字母开始，接着跟随0个或任意个小写字母，表示原子的名字。

如果数量大于 1，原子后会跟着数字表示原子的数量。如果数量等于 1 则不会跟数字。例如，H2O 和 H2O2 是可行的，但 H1O2 这个表达是不可行的。

两个化学式连在一起是新的化学式。例如 H2O2He3Mg4 也是化学式。

一个括号中的化学式和数字（可选择性添加）也是化学式。例如 (H2O2) 和 (H2O2)3 是化学式。

给定一个化学式，输出所有原子的数量。格式为：第一个（按字典序）原子的名子，跟着它的数量（如果数量大于 1），然后是第二个原子的名字（按字典序），跟着它的数量（如果数量大于 1），以此类推。

示例 1:

输入:
formula = "H2O"
输出: "H2O"
解释:
原子的数量是 {'H': 2, 'O': 1}。
示例 2:

输入:
formula = "Mg(OH)2"
输出: "H2MgO2"
解释:
原子的数量是 {'H': 2, 'Mg': 1, 'O': 2}。
示例 3:

输入:
formula = "K4(ON(SO3)2)2"
输出: "K4N2O14S4"
解释:
原子的数量是 {'K': 4, 'N': 2, 'O': 14, 'S': 4}。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-atoms
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

 1 class Solution {
 2 public:
 3     //用栈来解决括号问题
 4     /*若是左括号 就将左括号入栈
 5     若是元素 则将元素与其对应的数量入栈
 6     若是右括号 则从stk尾部向前遍历，每个元素的值都乘以右括号后面的数字，直到遇到第一个未使用的左括号为止*/
 7     string countOfAtoms(string formula) {
 8         map<string, int> m;
 9         vector<pair<string, int>> stk;
10         int len = formula.length(), i = 0;
11         string cur = ""; int num = 0;
12         while (i < len)
13         {
14             if (formula[i] == '(')
15                 stk.push_back({ "(",1 });
16             else if (formula[i] == ')')
17             {
18                 num = 0;
19                 while (i + 1 < len && (formula[i + 1] >= '0' && formula[i + 1] <= '9')) { num = num * 10 + formula[++i] - '0'; }
20                 if (!num)num = 1;
21                 for (int j = stk.size() - 1; j >= 0; j--)
22                 {
23                     if (stk[j].first == "(" && stk[j].second)
24                     {
25                         stk[j].second = 0;
26                         break;
27                     }
28                     stk[j].second *= num;
29                 }
30             }
31             else//解决字母问题 和数字问题
32             {
33                 cur = "";
34                 num = 0;
35                 cur += formula[i];
36                 while (i + 1 < len && (formula[i + 1] >= 'a' && formula[i + 1] <= 'z'))cur += formula[++i];
37                 while (i + 1 < len && (formula[i + 1] >= '0' && formula[i + 1] <= '9')) { num = num * 10 + formula[++i] - '0'; }
38                 if (!num)num = 1;
39                 stk.push_back({ cur,num });
40             }
41             i++;
42         }
43         for (auto item : stk)
44             m[item.first] += item.second;
45         string res = "";
46         for (auto item : m)
47             if (item.second)
48                 res += (item.first + (item.second == 1 ? "" : to_string(item.second)));
49         return res;
50     }
51 };