726. Number of Atoms
## 思路
先观察:
Aa(Bb)3 = AaBb3
Aa(Bb2)3 = AaBb6
(AaBb2)3 = Aa3Bb6
(Aa(Bb2)3)2 = Aa2Bb12
((AaBb2)3)2 = Aa6Bb12
Cc(Aa(Bb2)3)2 = Aa2Bb12Cc
反向iterate, Stack存目前的num, Counter存atom的数量
- `)`: 把新的num * stack[-1] 加到stack
- `(`: pop掉
- 大写: 更新counter
- 数字/小写
最后再把counter sort产生output
## Complexity
Time, Space: O(N)
## Code
```python
class Solution:
def countOfAtoms(self, formula: str) -> str:
stack = [1]
counter = Counter()
atom, num = '', ''
for ch in formula[::-1]:
if ch.isdigit():
num = ch + num
elif ch == ')':
stack.append(stack[-1] * (int(num) if num else 1))
num = ''
elif ch == '(':
stack.pop()
num = ''
elif ch.islower():
atom = ch
else:
atom = ch + atom
counter[atom] += stack[-1] * (int(num) if num else 1)
atom, num = '', ''
res = []
for atom in sorted(counter):
if counter[atom] == 1:
res.append(atom)
else:
res.append(f'{atom}{counter[atom]}')
return ''.join(res)
```