堆棧

概念

在生活中，我們可以用疊盤子這個(gè)經(jīng)典的場面來理解堆棧，先洗好的盤子放在下面，后洗好的盤子放盤子堆的最上面，一個(gè)一個(gè)壘起來。用的時(shí)候，從上面一個(gè)一個(gè)取出來用。用一個(gè)歇后語說就是：砌墻的磚頭--后來居上。

一句話總結(jié)就是：“先進(jìn)后出，后進(jìn)先出?！?/p>

實(shí)現(xiàn)

其實(shí)pyhton的list數(shù)據(jù)類型就帶有堆棧屬性，那么我們直接封裝成類

class Stack(object):

    __data = []

    def __init__(self):
        pass

    def push(self, data):
        self.__data.append(data)

    def pop(self):
        if self.__data:
            return self.__data.pop()

>>> from data_structure import Stack
>>> a=Stack()
>>> a.push(1)
>>> a.push(2)
>>> a.push(3)
>>> a.pop()
3
>>> a.pop()
2
>>> a.pop()
1
>>> a.pop()

實(shí)戰(zhàn)：

給定一個(gè)化學(xué)式（以字符串形式給出），返回每個(gè)原子的計(jì)數(shù)。原子元素始終以大寫字母開頭，然后是零個(gè)或多個(gè)小寫字母，代表名稱。如果計(jì)數(shù)大于1，則可以跟隨1個(gè)或多個(gè)表示該元素計(jì)數(shù)的數(shù)字。如果計(jì)數(shù)為1，則不跟隨數(shù)字。例如，H2O和H2O2是可能的，但H1O2是不可能的。連接在一起的兩個(gè)公式將生成另一個(gè)化學(xué)式。例如，H2O2He3Mg4也是一個(gè)化學(xué)式。
放在括號中的公式以及一個(gè)計(jì)數(shù)（可選添加）也是一個(gè)公式。例如，（H2O2）和 (H2O2)3是化學(xué)式。
給定一個(gè)化學(xué)式，以以下形式將所有元素的計(jì)數(shù)輸出為字符串：第一個(gè)名稱（按排序順序），然后是其計(jì)數(shù)（如果該計(jì)數(shù)大于1），然后是第二個(gè)名稱（按排序順序） ），然后是其計(jì)數(shù)（如果該計(jì)數(shù)大于1），依此類推。

分析：
這道題的核心就是要把括號拆分出來，把(H2O2)3拆分成H2O2H2O2H2O2在這樣拆分完括號的基礎(chǔ)上，就能方便的統(tǒng)計(jì)化學(xué)元素的個(gè)數(shù)了。拆分括號就能很好的用到堆棧。

這里我們還要考慮到括號套括號的情況，即((H2O)2)5這種，但默認(rèn)傳入?yún)?shù)都是正確的化學(xué)式，即不考慮)H2O(等之類的情況，換句話說，這里默認(rèn)所有括號都是成對且正確的。

我們從左到右遍歷化學(xué)式，遇到(括號就開始把括號里的數(shù)據(jù)壓入堆棧，遇到)就將數(shù)據(jù)取出來，直到取到(然后乘以)后面的數(shù)字即可。

func為主函數(shù)，主要處理整個(gè)遍歷化學(xué)表達(dá)式和壓站出站過程
find_num函數(shù)尋找）后的數(shù)字 也就是找到例子中的 
find_string函數(shù)把展開的無括號的表達(dá)式統(tǒng)計(jì)其中元素個(gè)數(shù)。
以K4(ON(SO3)2)2為例
主函數(shù)func從頭遍歷 壓棧進(jìn)result 直到遇到第一個(gè)) 
然后出棧，直到第一個(gè)( 然后得到SO3 乘以)后面的數(shù)字2 得到SO3SO3 再壓入棧
此時(shí)表達(dá)式就變成了K4(ONSO3SO32)2
然后跳過被乘了的數(shù)字2 （tail_num 變量存儲的） 繼續(xù)遍歷之后的字符串

def find_num(string):
    # 尋找“)”后面的數(shù)字
    num = ""
    for i in string:
        if i.isdigit():
            num += i
        else:
            break
    if not num:
        num = '1'
    return num

def find_string(list_string):
    # 把展開后的不帶括號的分子式 處理為最后的結(jié)果
    result = dict()
    element = ""
    num = ""
    for i, key in enumerate(list_string):
        if key.isupper():
            if element:
                if not num:
                    num = "1"
                result[element] = result.get(element, 0) + int(num)
                num = ""
            element = key
        elif key.islower():
            element += key
        elif key.isdigit():
            num += key
    if element:
        if not num:
            num = "1"
        result[element] = result.get(element, 0) + int(num)
    return result

def func(string):
    print(string)
    result = list()
    result_dict = dict()
    tail_num = []
    for i, key in enumerate(string):
        if key  == ')':
            string_son = ""
            last_value = result.pop()
            while last_value != "(":
                string_son += last_value
                try:
                    # 出棧
                    last_value = result.pop()
                except:
                    print('出現(xiàn)意外，沒有對應(yīng)的括號匹配')
                    break
            tail_string = string[i+1:]
            num = find_num(tail_string)
            # num 為)后面的數(shù)字，賦值給全局變量tail_num 以便在入棧的時(shí)候跳過
            tail_num = list(num)
            # 展開括號
            result += list(string_son[::-1]  * int(num))
        else:
            if key.isdigit():
                if key in tail_num:
                    tail_num.remove(key)
                    # 跳過)后面的數(shù)字
                    continue
            else:
                tail_num = []
            # 壓棧
            result.append(key)
    print(result)
    return find_string(result)