# 0726. 原子的数量

### 题目地址(726. 原子的数量)

<https://leetcode-cn.com/problems/number-of-atoms/>

### 题目描述

```
给定一个化学式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}。


注意:

所有原子的第一个字母为大写，剩余字母都是小写。
formula的长度在[1, 1000]之间。
formula只包含字母、数字和圆括号，并且题目中给定的是合法的化学式。
```

### 前置知识

* 栈

### 公司

* 暂无

### 思路

这道题我们可以利用从`后往前遍历`+`对次数入栈`的技巧，这样问题就和诸如[394. 字符串解码](/leetcode-solution/medium/394.decode-string.md) 这种中等题目并无二致了。

具体来说，我们可以使用一个字典存储每一个原子的出现情况，字典的 key 为原子，value 为原子出现次数，最后对该字典进行排序处理输出即可。

那么字典如何生成呢？

我们可以从后往前遍历，这样遇到一个**大写字母**我们就将其作为一个分界线。记当前位置为 s1，其右侧第一个大写字母的左侧位置记为 s2，那么 s\[s1]s\[s1+1]...s\[s2-1] 就是一个**完整的原子**。接下来，我们需要知道**完整的原子**的出现次数。

1. 接下来需要本题的第二个技巧。那就是将数字入栈，而不是原子，（这是因为我们是从后往前遍历的）然后根据栈中存储的数字决定当前原子出现的次数。比如 K4(ON(SO3)2)2，我们从后往前面遍历，栈中开始是 \[1] -> \[1,2] -> \[1,2,4] -> \[1,2,4,12]。我们就知道 O 需要重复 12 次，接下来栈变为 \[1,2,4] ，我们就知道 S 需要重复 4 次。接下来栈变为 \[1,2]，我们就知道 O 和 N 分别出现 2 次，继续栈变为 \[1]，不难得出 K 出现 4 次，累加即可得到字典。

### 关键点

* 从后往前遍历

### 代码

* 语言支持：Python3

Python3 Code:

```python

class Solution:
    def countOfAtoms(self, s: str) -> str:
        stack = [1]
        i = len(s) - 1
        dic = collections.defaultdict(int)
        lower = count = ''
        while i > -1:
            if '0' <= s[i] <= '9':
                count = s[i] + count
            elif 'a' <= s[i] <= 'z':
                lower = s[i] + lower
            elif s[i] == ')':
                stack.append(stack[-1] * int(count or '1'))
                count = ''
            elif s[i] == '(':
                stack.pop()
            elif 'A' <= s[i] <= 'Z':
                dic[s[i] + lower] += stack[-1] * int(count or '1')
                count = ''
                lower = ''
            i -= 1
        ans = ''
        for k, v in sorted(dic.items()):
            if v == 1:
                ans += k
            else:
                ans += k + str(v)
        return ans


```

**复杂度分析**

令 n 为 s 长度。

* 时间复杂度：由于使用到了排序，因此时间复杂度为 $O(nlogn)$
* 空间复杂度：由于使用到了哈希表和栈，并且栈的大小和哈希表的大小都不会超过 s 的长度，因此空间复杂度为 $O(n)$

> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。

力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~

以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。

![](https://p.ipic.vip/vgf8uk.jpg)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/726.number-of-atoms.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.