python-代數式括弧有效性檢驗

• 2020 年 10 月 3 日
• 筆記
• Python, 演算法

思路：

利用棧實現代數式中括弧有效行的的檢驗：

程式碼：

class mychain(object): #利用鏈表建立棧，鏈表為父類
    length=0
    def __init__(self,value=None,next=None):#創建鏈表，長度並不包含頭部
        self.value=value
        self.next=next
        #mychain.length=mychain.length+1
    def append(self,value=None):
        while self.next!=None:
            self=self.next
        self.next=mychain(value)
        mychain.length=mychain.length+1 #追加時，鏈表長度增加
    def travle(self):#遍歷鏈表
        print(self.value)
        if self.next!=None:
            self.next.travle()
    def drop (self,value):#刪除特定值的第一個匹配節點
        while  self.next!=None:
            if self.next.value!=value:
                self=self.next
            else:
                self.next=self.next.next
                mychain.length=mychain.length-1 #刪除時，鏈表長度減小
                break
    def pop(self):#刪除未節點
        if self.next!=None:#並不刪除頭結點
            while self.next.next!=None:
                self=self.next
            self.next=None
            mychain.length=mychain.length-1#彈出為節點，並減小長度，頭結點不彈出



class stock(mychain):#棧類
    bottom=None   　　#棧底
    top=None　　　　　#棧頂
    n_count=0　　　　#計數
    def Max(self):　　#佔中最大值
        if self.next!=None:
            tmp = self.next.value
            while  self.next.next!=None:
                self=self.next
                if self.next.value>tmp:
                    tmp=self.next.value
            return tmp
        else:
            print('棧為空！')
    def Min(self):#棧中的最小值
        if self.next!=None:
            tmp = self.next.value
            while  self.next.next!=None:
                self=self.next
                if self.next.value<tmp:
                    tmp=self.next.value
            return tmp
        else:
            print('棧為空！')

    def push(self,value): #壓棧
        while self.next != None:
            self = self.next
        self.next = mychain(value)
        stock.top=self.next
        stock.length=stock.length+1
        stock.n_count=stock.n_count+1
    def __init__(self,value='',next=None):
        self.value=value
        self.next=next
        stock.bottom=self
        stock.top=self
        #stock.n_count=stock.n_count+1
        #stock.length=stock.length+1
    def append(self,value=''):#取消追加函數
        print('請使用Push()!')
    def pop(self):
        if self.next!=None:#並不刪除頭結點
            while self.next.next!=None:
                self=self.next
            self.next=None
            stock.top=self
            stock.length=stock.length-1#彈出為節點，並減小長度，頭結點不彈出
class solution(object):
    def validationofbrackets(self,astr=''):#檢驗串中的括弧合法性
        braketsstock=stock()
        for i in astr:
            if i in ['{','(','[']:
                braketsstock.push(i)
            else:
                if i==')':
                    if braketsstock.top.value=='(':
                        braketsstock.pop()
                    else:
                        return False
                elif i==']':
                    if braketsstock.top.value=='[':
                        braketsstock.pop()
                    else:
                        return False
                elif i=='}':
                    if braketsstock.top.value=='{':
                        braketsstock.pop()
                    else:
                        return False
                else:
                    pass
        print(astr)
        print(braketsstock.length)
        if braketsstock.length==0:
            return True
        else:
            return False


運行：

bstr='([{((({{}})))}]){{}}{{}{}{}[][]()(123)(((sin5)))}'
f=solution()
print(f.validationofbrackets(bstr))