題目描述
- 給定一個化學式formula（作為字元串），傳回每種原子的數量。
- 原子總是以一個大寫字母開始，接着跟随0個或任意個小寫字母，表示原子的名字。
- 如果數量大于 1，原子後會跟着數字表示原子的數量。如果數量等于 1 則不會跟數字。例如，H2O 和 H2O2 是可行的，但 H1O2這個表達是不可行的。
- 兩個化學式連在一起是新的化學式。例如 H2O2He3Mg4 也是化學式。
- 一個括号中的化學式和數字（可選擇性添加）也是化學式。例如 (H2O2) 和 (H2O2)3 是化學式。
-
給定一個化學式 formula ，傳回所有原子的數量。格式為：第一個（按字典序）原子的名字，跟着它的數量（如果數量大于
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}。
解題思路
1. 按照哪個順序掃描字元串呢？
看到括号肯定想到是用棧的形式儲存右括号後的數字，那麼正序周遊字元串就無法直接得到括号内元素的具體個數。
是以我們應選擇逆序周遊字元串
2. 該如果儲存右括号的數？
先來看一個例子
從圖中可以看出先掃描的右括号後被消除，這個規律是不是很像棧？
每掃描到一個右括号我們就把括号後面的數壓入棧，每掃描到一個左括号我們就把對棧進行一個pop。
3.什麼時候該暫停掃描，計算元素的數量？
字元串裡有什麼？
- 數字
- 大寫字母
- 小寫字母
- 左右括号
事實上題中明确說明每個元素首部都是大寫字母，且一個元素隻有是首部是大寫字母。
那麼說明讀取到大寫字母時将我們temp字元串取出計算就行，計算完後temp字元串重置為空。
（temp字元串是我們用于暫時儲存掃描過的元素的字元串，應在掃描開始時定義，在計算一次後及時重置）
（讀到除左、右括号，或者括号後的數字以為的字元時都該将其添加到temp的首部 #逆序掃描）
4.如何計算元素的數量？
首先通過逆序周遊temp字元串，得到後面的數字，并由string類型轉為int類型，記為A
通路棧，并将棧内所有的數相乘，記為B
A與B相乘便是該元素的數量，将其儲存在哈希表中
代碼
Python實作，代碼寫的略雜，歡迎指點
class Solution:
def countOfAtoms(self, formula: str) -> str:
numbers = dict()
point = len(formula) - 1
temp = ""
temp_ji = 1
num = [1]
while point >= 0:
flag = -2
if 65 <= ord(formula[point]) and 90 >= ord(formula[point]):
temp = formula[point] + temp
dd = ord(temp[-1])
if dd >= 48 and dd <= 57:
point2=len(temp)-2
while point2>=0:
if ord(temp[point2])>=48 and 57>=ord(temp[point2]):
point2-=1
else:
break
temp_a=temp[0:point2+1]
if temp_a not in numbers:
numbers[temp[0:point2+1]] = 1 * (int(temp[point2+1:])) * temp_ji
else:
numbers[temp[0:point2+1]] += 1 * (int(temp[point2+1:])) * temp_ji
else:
if temp not in numbers:
numbers[temp] = 1 * temp_ji
else:
numbers[temp] += 1 * temp_ji
temp = ""
elif 97 <= ord(formula[point]) and 122 >= ord(formula[point]):
temp = formula[point] + temp
elif formula[point] == "(":
if len(num)!=0:
temp_wei = num.pop()
temp_ji //= temp_wei
elif formula[point] == ")":
pass
else:
if formula[point - 1] == ")":
num.append(int(formula[point]))
temp_ji *= int(formula[point])
else:
if ord(formula[point - 1]) >= 48 and 57 >= ord(formula[point - 1]):
point2 = point - 2
while point2 >= 0:
if ord(formula[point2]) >= 48 and ord(formula[point2]) <= 57:
point2 -= 1
else:
break
if formula[point2] == ")":
num.append(int(formula[point2 + 1:point + 1]))
temp_ji *= int(formula[point2 + 1:point + 1])
else:
temp = formula[point2 + 1:point + 1]
flag = point2
else:
temp = formula[point]
if flag == -2:
point -= 1
else:
point = point2
answer = list(numbers.keys())
answer.sort()
ans = ""
for i in answer:
temp = numbers[i]
if temp > 1:
ans += (i + str(numbers[i]))
else:
ans += i
return ans