python實(shí)現(xiàn)棧的代碼回顧

class Stack(object):
    # Stack() 創(chuàng)建一個(gè)空的新棧。
    def __init__(self):
        self.items = []

    # push(new_item)將一個(gè)新的元素添加到棧頂阎肝。
    def push(self, new_item):
        self.items.append(new_item)

    # 返回棧頂元素锦针，但不會(huì)彈出它。
    def top(self)：
        return self.items[-1]

    # 彈出并返回棧頂元素
    def pop(self):
        return self.items.pop()

    # 返回棧是否為空。椂遥空返回true，否則返回false亚隅。
    def isEmpty(self):
        return [] == self.items

    # 返回棧的長(zhǎng)度，即棧中元素的個(gè)數(shù)狮崩。
    def size(self):
        return len(self.items)

后綴表達(dá)式回顧

后綴表達(dá)式是計(jì)算機(jī)科學(xué)中的一種常見(jiàn)的數(shù)學(xué)表達(dá)式形式。相比于人類(lèi)常用的中綴表達(dá)鹿寻，后綴表達(dá)式在沒(méi)有括號(hào)的情況下也不會(huì)引起運(yùn)算順序上的歧義，這是其最重要的優(yōu)點(diǎn)诽凌。

中綴表達(dá)式 → 后綴表達(dá)式
A+B → AB+
A+BC → ABC+
(A+B)C → AB+C
(A+B)(C+D) → AB+CD+
A+B+C+D → AB+C+D+

中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式

假設(shè)表達(dá)式中只有大寫(xiě)字母毡熏、數(shù)字和運(yùn)算符，如何將一個(gè)中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式侣诵？
解決這一問(wèn)題的要點(diǎn)有如下：

• 大寫(xiě)字母和數(shù)字的排列順序痢法，中綴表達(dá)式和后綴表達(dá)式是相同的。
• 優(yōu)先級(jí)更高的運(yùn)算符和靠左的同級(jí)別運(yùn)算符應(yīng)當(dāng)更早在后綴表達(dá)式中出現(xiàn)杜顺。
• 括號(hào)相當(dāng)于更高的一個(gè)平臺(tái)财搁，左括號(hào)作為平臺(tái)的開(kāi)始，右括號(hào)作為平臺(tái)的結(jié)束躬络。

class Stack(object):
    # Stack() 創(chuàng)建一個(gè)空的新棧尖奔。
    def __init__(self):
        self.items = []
    
    # push(new_item)將一個(gè)新的元素添加到棧頂。
    def push(self, new_item):
        self.items.append(new_item)
    
    # 返回棧頂元素穷当，但不會(huì)彈出它提茁。
    def top(self):
        return self.items[-1]
        
    # 彈出并返回棧頂元素
    def pop(self):
        return self.items.pop()
        
    # 返回棧是否為空。椖俨耍空返回true茴扁，否則返回false。
    def isEmpty(self):
        return [] == self.items
    
    # 返回棧的長(zhǎng)度汪疮，即棧中元素的個(gè)數(shù)峭火。
    def size(self):
        return len(self.items)
    
# 將中綴表達(dá)式變換成后綴表達(dá)式
# trans_string為傳入的待轉(zhuǎn)換的中綴表達(dá)式
# op_rank為運(yùn)算符的優(yōu)先級(jí)毁习，數(shù)字越大，優(yōu)先級(jí)越高
def mid2post(trans_string, op_rank):
    post_list = [] #創(chuàng)建一個(gè)空列表卖丸，用于保存生成中的后綴表達(dá)式
    stack = Stack() #創(chuàng)建一個(gè)新的棧用于保存未被輸出的運(yùn)算符
    
    for checking_char in trans_string: #從左到右蜓洪，逐個(gè)遍歷中綴表達(dá)式中的字符
        if checking_char in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789': #當(dāng)前字符為字母或數(shù)字
            post_list.append(checking_char) #將字符接入后綴表達(dá)式
        elif checking_char == '(': #當(dāng)前符號(hào)為左括號(hào)
            stack.push(checking_char) #將左括號(hào)入棧，代表著后面出現(xiàn)的運(yùn)算符優(yōu)先級(jí)更高
        elif checking_char == ')': #當(dāng)前符號(hào)為右括號(hào)
            top_char = stack.pop() 
            while top_char != '(': #彈出元素坯苹，接入后綴表達(dá)式隆檀，直到出現(xiàn)配對(duì)的左括號(hào)
                post_list.append(top_char)
                top_char = stack.pop()
        else: #符號(hào)為運(yùn)算符
            while (not stack.isEmpty()) and (op_rank[stack.top()]>=op_rank[checking_char]): #棧不為空，且棧頂符號(hào)優(yōu)先級(jí)不低于當(dāng)前符號(hào)
                post_list.append(stack.pop()) #彈出這個(gè)更靠前的運(yùn)算符粹湃，并接入后綴表達(dá)式
            stack.push(checking_char) #將運(yùn)算符壓入棧
    
    while not stack.isEmpty(): #當(dāng)棧未空
        post_list.append(stack.pop()) #彈出所有運(yùn)算符恐仑，并接入后綴表達(dá)式
    
    return ''.join(post_list) #將列表轉(zhuǎn)換為字符串并返回
        
def main():
    op_rank = {'*':2, '/':2, '+':1, '-':1, '(':0}
    string_list = ['A+B', 'A+B*C', '(A+B)*C', '(A+B)*(C+D)', 'A+B+C+D']
    for trans_string in string_list:
        print("%s --> %s"%( trans_string, mid2post(trans_string,op_rank)))
        print("-----------------")

if __name__ == "__main__":
    main()

運(yùn)行結(jié)果如下：

A+B --> AB+
-----------------
A+B*C --> ABC*+
-----------------
(A+B)*C --> AB+C*
-----------------
(A+B)*(C+D) --> AB+CD+*
-----------------
A+B+C+D --> AB+C+D+
-----------------

計(jì)算后綴表達(dá)式

如何高效的計(jì)算后綴表達(dá)式？
這一問(wèn)題同樣可以使用棧來(lái)解決为鳄，而且相比之前的轉(zhuǎn)換問(wèn)題更加簡(jiǎn)單裳仆。
解決這一問(wèn)題的要點(diǎn)有如下：

• 每當(dāng)在輸入上看到運(yùn)算符時(shí)，計(jì)算兩個(gè)最近的操作數(shù)孤钦。
• 操作數(shù)的先后次序不能變歧斟。

我們以最簡(jiǎn)單的個(gè)位數(shù)運(yùn)算為例，編寫(xiě)代碼：

class Stack(object):
    # Stack() 創(chuàng)建一個(gè)空的新棧偏形。
    def __init__(self):
        self.items = []
    
    # push(new_item)將一個(gè)新的元素添加到棧頂静袖。
    def push(self, new_item):
        self.items.append(new_item)
    
    # 返回棧頂元素，但不會(huì)彈出它俊扭。
    def top(self):
        return self.items[-1]
        
    # 彈出并返回棧頂元素
    def pop(self):
        return self.items.pop()
        
    # 返回棧是否為空队橙。棧空返回true萨惑，否則返回false捐康。
    def isEmpty(self):
        return [] == self.items
    
    # 返回棧的長(zhǎng)度，即棧中元素的個(gè)數(shù)庸蔼。
    def size(self):
        return len(self.items)
    
# 將中綴表達(dá)式變換成后綴表達(dá)式
# trans_string為傳入的待轉(zhuǎn)換的中綴表達(dá)式
# op_rank為運(yùn)算符的優(yōu)先級(jí)解总，數(shù)字越大，優(yōu)先級(jí)越高
def mid2post(trans_string, op_rank):
    post_list = [] #創(chuàng)建一個(gè)空列表姐仅，用于保存生成中的后綴表達(dá)式
    stack = Stack() #創(chuàng)建一個(gè)新的棧用于保存未被輸出的運(yùn)算符
    
    for checking_char in trans_string: #從左到右花枫，逐個(gè)遍歷中綴表達(dá)式中的字符
        if checking_char in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789': #當(dāng)前字符為字母或數(shù)字
            post_list.append(checking_char) #將字符接入后綴表達(dá)式
        elif checking_char == '(': #當(dāng)前符號(hào)為左括號(hào)
            stack.push(checking_char) #將左括號(hào)入棧，代表著后面出現(xiàn)的運(yùn)算符優(yōu)先級(jí)更高
        elif checking_char == ')': #當(dāng)前符號(hào)為右括號(hào)
            top_char = stack.pop() 
            while top_char != '(': #彈出元素萍嬉，接入后綴表達(dá)式乌昔，直到出現(xiàn)配對(duì)的左括號(hào)
                post_list.append(top_char)
                top_char = stack.pop()
        else: #符號(hào)為運(yùn)算符
            while (not stack.isEmpty()) and (op_rank[stack.top()]>=op_rank[checking_char]): #棧不為空，且棧頂符號(hào)優(yōu)先級(jí)不低于當(dāng)前符號(hào)
                post_list.append(stack.pop()) #彈出這個(gè)更靠前的運(yùn)算符壤追，并接入后綴表達(dá)式
            stack.push(checking_char) #將運(yùn)算符壓入棧
    
    while not stack.isEmpty(): #當(dāng)棧未空
        post_list.append(stack.pop()) #彈出所有運(yùn)算符磕道，并接入后綴表達(dá)式
    
    return ''.join(post_list) #將列表轉(zhuǎn)換為字符串并返回
    
# 將計(jì)算后綴表達(dá)式
# post_string為傳入的待計(jì)算的后綴表達(dá)式
# op_rank為運(yùn)算符的優(yōu)先級(jí)，數(shù)字越大行冰，優(yōu)先級(jí)越高
def compute_post(post_string):
    stack = Stack() #創(chuàng)建一個(gè)新的棧用于保存未被輸出的運(yùn)算符
    
    for computing_char in post_string: #從左遍歷
        if computing_char in '01234567889': #如果當(dāng)前為數(shù)字
            stack.push(computing_char) #壓入棧
        else: #如果為運(yùn)算符
            value_2 = int(stack.pop()) #先彈出后一個(gè)操作數(shù)
            value_1 = int(stack.pop()) #后彈出前一個(gè)操作數(shù)
            if computing_char == '+':
                value_3 = value_1 + value_2
            elif computing_char == '-':
                value_3 = value_1 - value_2
            elif computing_char == '*':
                value_3 = value_1 * value_2
            else:
                value_3 = value_1 / value_2
            stack.push(value_3) #將運(yùn)算結(jié)果入棧
            
    return stack.pop()
        
def main():
    op_rank = {'*':2, '/':2, '+':1, '-':1, '(':0}
    string_list = ['1+2', '1+2*3', '(1+2)*3', '(1+2)*(3+4)', '1+2+3+4']
    for trans_string in string_list:
        print("%s --> %s --> %d" % (trans_string, mid2post(trans_string,op_rank), compute_post(mid2post(trans_string,op_rank)) ))
        print("-----------------")

if __name__ == "__main__":
    main()

運(yùn)行結(jié)果為：

1+2 --> 12+ --> 3
-----------------
1+2*3 --> 123*+ --> 7
-----------------
(1+2)*3 --> 12+3* --> 9
-----------------
(1+2)*(3+4) --> 12+34+* --> 21
-----------------
1+2+3+4 --> 12+3+4+ --> 10
-----------------

結(jié)果正確溺蕉。如果需要計(jì)算兩位數(shù)以上的操作數(shù)伶丐，則需要利用空格等分隔符來(lái)對(duì)操作數(shù)進(jìn)行分隔。