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))