九章演算法 | Google面試題：原子計數
撰文 | JZ
專欄 | 九章演算法
題目描述
以字元串形式給出一個化學分子式，返回每個原子的計數。原子元素始終以大寫字母開始，然後是零個或多個小寫字母，代表名稱。如果個數大於1，則可以跟隨1個或多個代表該元素的個數。如果個數為1，則不會有數字。
例如，存在H2O和H2O2，但是不存在H1O2。兩個式子連接在一起產生另一個式子。例如，H2O2He3Mg4也是一個式子。式子可以放在括弧內，並可為整個帶括弧的式子添加個數。 例如，(H2O2)和(H2O2)3是合理的。
給定一個分子式，將所有元素的個數輸出為以下形式的字元串：第一個原子名稱（按排序順序），後面是計數（如果該計數大於1）；然後是第二個原子名稱（按排序順序 ），然後計數（如果該計數大於1），依此類推……
樣例:
輸入: "H2O"
輸出: "H2O"解釋:元素計數為 {H: 2, O: 1}.
輸入: "Mg(OH)2"
輸出: "H2MgO2"
解釋:元素計數為 {H: 2, Mg: 1, O: 2}.
輸入: "K4(ON(SO3)2)2"
輸出: "K4N2O14S4"
解釋:元素計數為 {K: 4, N: 2, O: 14, S: 4}.
注意：
1.所有的原子名稱的非首字母都小寫，首字母都大寫。
2.分子式的長度將在[1，1000]的範圍內。
3.分子式將只包含字母，數字和圓括弧，並且是問題中的有效公式。
解題思路分析
這道題目稍許複雜，感覺像是在操作一段複雜的字元串，但細想之下其實整個過程並不繁瑣。接下來給出三種方法，這三種方法本質相同，但實現方法上存在差異，第一種採用遞歸，而後兩種採用棧式結構。
方法一：首先編寫一個解析器Parse，這個解析器應當能統計出從當前字元串位置開始，直到遇到一個右括弧「）」或讀到字元串末尾，然後連帶上右括弧「）」後面可能跟上的數字，這可做為一段整體。用一個counter來記錄這一段各個元素的個數。最後返回counter。
具體操作：
1.首先初始化counter
2.在解析器循環中：當遇到左括弧「（」時，就遞歸調用Parse；並把Parse子程序中元素統計結果加入當前的counter當中。如果不遇到左括弧，那麼會發現一定是大寫字母，也就是一個原子名稱的開頭，那麼就統計這個元素的個數。
3.循環結束後，檢查右括弧後面是否跟有數字，如果有的話要對當前的counter進行相應倍乘。
4.最後返回counter。
Parse可以寫成一個遞歸函數，然後用主函數做驅動函數。
方法二：和第一種方法類似，思想相同，但是寫法上有差異。不採用遞歸函數，採用棧來進行操作。（其實函數的遞歸和棧本就具有極大的相似性）。
這時，先初始化counter棧，然後仍舊需要一層循環，直到讀完所有字元。循環中：當遇到左括弧「（」時一層新的counter入棧。遇到右括弧「）」時棧頂counter彈出，並檢查後面是否跟有數字，如果有的話對當前counter進行相應倍乘，並把結果累計到新露出的棧頂。遇到大寫字母，就統計這個元素的個數，計入counter，類似方法一。
方法三：同方法二，但是不手動解析字元串，而是採用正則表達式（又稱規則表達式Regular Expression，通常被用來檢索、替換那些符合某個模式的文本），把字元串分成一個一個獨立的塊，這裡採用的表達式為："([A-Z][a-z]*)(d*)|(()|())(d*)"。這裡面的塊分別表示：可能帶有數字的元素如「Fe3」、「H」等；左括弧「（」；可能帶有數字的右括弧「）」、「）3」等。然後在循環中對正則表達式中的每塊進行各自對應的處理。
複雜度分析：以上無論哪種方法，理論的複雜度相同。但是這裡推薦使用第三種方法，一者棧式結構比遞歸的寫法更加簡潔；二者正則表達式極大地簡化匹配操作。時間複雜度為O(N^2)，這裡N為字元串的長度，遍歷一遍字元串需要O(N)的時間，但是當遇到左括弧時，會對子式的元素向外累加，這就有可能達到O(N)的時間，而總字元串長度為O(N)，所以左括弧的個數為O(N)（注意大O記號的含義是「不超過」，這裡的意思是不超過線性界，而不是等於線性界）。故所花時間為O(N^2)，這裡給出一種時間比較逼近N^2的表達式：A(B(C(D(E(F3)4)5)6)7)。
注意：正則表達式的時間界不容易判斷，這裡正則表達式沒有回溯，所以總的時間複雜度不會超過O(N^2)，這與正則表達式的實現方法有關。
空間複雜度為O(N)，這裡無論是棧還是Map，空間複雜度不會超過O(N)。
參考程序
這裡給出方法三，採用正則表達式的棧式寫法
http://www.jiuzhang.com/solution/number-of-atoms/
面試官角度分析
本題是一道比較難的的題目，考察到了字元串的操作（實際上從形式語言與自動機的角度看，這是對於給定文法的一種特殊的解釋執行），以及遞歸或者棧的靈活應用。如果能寫出遞歸或者棧式結果，可以給出Hire；如果能了解並想到用正則表達式的方法，可以給出Strong Hire。
lintcode相關問題
http://www.lintcode.com/zh-cn/problem/url-parser/
http://www.lintcode.com/zh-cn/problem/regular-expression-matching/
推薦閱讀：