<p>这个问题来自<a href="https://leetcode.com/problems/number-of-atoms/" rel="nofollow noreferrer">726. Number of Atoms</a></p>
<p>基于a<a href="https://github.com/cherryljr/LeetCode/blob/master/Number%20of%20Atoms.java#L103" rel="nofollow noreferrer">Java Solution on Github to Python</a>平移的算法</p>
<pre><code>class Solution:
def __init__(self, formula):
self.formula = formula
def count_of_atoms(self):
" Main routine to count the atoms "
if len(self.formula) <= 1:
return self.formula
self.index = 0
mp = self.recursion() # use recursive function to count
# create result for display
return dict(sorted(mp.items(), key = lambda kv: kv[0]))
def recursion(self):
" Recursive counts the atoms (uses recursion to handle parens) "
# Placing formula count in dictionary
rst = {}
while self.index < len(self.formula):
if self.formula[self.index] == "(":
# Start paren group (recursive call)
self.index += 1
sub_rst = self.recursion() # dictionary for paren group
count = self.get_count() # count of paren group
# Merge paren group dictionary (sub_rst) with current (rst)
for k, v in sub_rst.items():
if not k in rst:
rst[k] = 0
rst[k] += v*count
elif self.formula[self.index] == ")":
# Ending paren group
self.index += 1
return rst
else:
name = self.get_name()
if not name in rst:
rst[name] = 0
rst[name] += self.get_count()
return rst
def get_name(self):
" name of atom "
i, j = self.index, self.index + 1
while j < len(self.formula) and self.formula[j].islower():
j += 1
self.index = j
return self.formula[i:j]
def get_count(self):
" Count of atoms or () group "
i = j = self.index
while j < len(self.formula) and self.formula[j].isdigit():
j += 1
self.index = j
return 1 if i == j else int(self.formula[i:j])
</code></pre>
<p><strong>测试</strong></p>
<p>使用来自<a href="https://leetcode.com/problems/number-of-atoms/" rel="nofollow noreferrer">726. Number of Atoms</a>的测试用例</p>
<pre><code>tests = ["H2O", "Mg(OH)2", "K4(ON(SO3)2)2"]
for t in tests:
s = Solution(t)
print(f"Formula {t} has atom count {s.count_of_atoms()}")
</code></pre>
<p><strong>输出</strong></p>
<pre><code>Formula H2O has atom count {'H': 2, 'O': 1}
Formula Mg(OH)2 has atom count {'H': 2, 'Mg': 1, 'O': 2}
Formula K4(ON(SO3)2)2 has atom count {'K': 4, 'N': 2, 'O': 14, 'S': 4}
</code></pre>