快捷導(dǎo)航

使用Python實(shí)現(xiàn)一個(gè)棧判斷括號(hào)是否平衡

更新時(shí)間：2018年08月23日 11:19:41 作者：soong

棧（Stack）在計(jì)算機(jī)領(lǐng)域是一個(gè)被廣泛應(yīng)用的集合，棧是線性集合，訪問(wèn)都嚴(yán)格地限制在一段，叫做頂（top）。這篇文章主要介紹了使用Python實(shí)現(xiàn)一個(gè)棧判斷括號(hào)是否平衡,需要的朋友可以參考下

棧（Stack）在計(jì)算機(jī)領(lǐng)域是一個(gè)被廣泛應(yīng)用的集合，棧是線性集合，訪問(wèn)都嚴(yán)格地限制在一段，叫做頂（top）。舉個(gè)例子，棧就想一摞洗干凈的盤子，你每次取一個(gè)新盤子，都是放在這一摞盤子的最上頭，當(dāng)你往里面添加盤子的時(shí)候，也是放在最上面，處在底部的盤子，你可能永遠(yuǎn)也用不到。棧的最常見(jiàn)操作，有如下兩個(gè)：

push(a) # 壓入，將a壓入的棧中
pop(） # 彈出，將棧的最后一個(gè)元素彈出

可是使用Python的列表數(shù)據(jù)結(jié)構(gòu)，來(lái)模擬棧的操作，使用 append 來(lái)模擬 push ，使用列表的 pop 來(lái)模擬棧的 pop ，但是這樣做有一個(gè)弊端，那就是列表原本自帶的操作方法同樣能夠使用，可能會(huì)造成混亂。

棧的實(shí)現(xiàn) 下面就通過(guò)借助Python的列表，來(lái)自定義一個(gè)棧類：

class Stack(object):
  """使用數(shù)組實(shí)現(xiàn)一個(gè)棧"""
  def __init__(self):
    self.data = []
  def push(self, num):
    """壓棧操作"""
    self.data.append(num)
  def pop(self):
    """返回從棧中彈出的元素, 當(dāng)棧為空的時(shí)候, 拋出IndexError"""
    return self.data.pop()
  def peek(self):
    """查看當(dāng)前棧頂?shù)脑? 當(dāng)棧為空的時(shí)候, 拋出IndexError"""
    return self.data[-1]
  def __len__(self):
    """返回棧的長(zhǎng)度, 調(diào)用len(obj)時(shí)會(huì)自動(dòng)調(diào)用obj對(duì)象的__len__方法"""
    return len(self.data)
  def isEmpty(self):
    """判斷棧是否為空"""
    return True if len(self.data)==0 else False
  def clear(self):
    """清空棧"""
    self.data = []
  def __repr__(self):
    """當(dāng)前對(duì)象的表現(xiàn)形式, 在終點(diǎn)直接鍵入對(duì)象時(shí)會(huì)調(diào)用"""
    return 'Stack_' + str(self.data)
  def __str__(self):
    """當(dāng)前對(duì)象的字符串表示, 使用print(obj)時(shí)會(huì)調(diào)用"""
    return 'Stack_' + str(self.data)

以上代碼實(shí)現(xiàn)了一個(gè)簡(jiǎn)單的基于列表的棧。

棧的應(yīng)用棧應(yīng)用的一個(gè)很典型的例子，就是檢查括號(hào)是否匹配。例如：每一個(gè)開始的 [ 后面，都應(yīng)該跟著一個(gè)位置正確的 ] ，并且每一個(gè) ( 后面，也應(yīng)該跟著一個(gè)位置正確的結(jié)束的 ) .

(...)...(...)
(...)...(...
)...((...)
def isBalance(text):
  """棧的應(yīng)用,檢查括號(hào)是否平衡"""
  result_stack = Stack()
  for i in text:
    if i in ['{', '[', '(']:
      result_stack.push(i)
    elif i in ['}', ']', ')']:
      # 遇到結(jié)束括號(hào)的情況
      if result_stack.isEmpty():
        # 如果當(dāng)前棧為空, 不匹配,返回False
        return False
      chFromStack = result_stack.pop()
      if not ((chFromStack == '{' and i == '}' )
          or (chFromStack == '[' and i == ']')
          or (chFromStack == '(' and i == ')')):
        # 如果不滿足匹配條件, 則返回False
        return False
  # 遍歷結(jié)束后, 如果結(jié)果棧為空, 則代表括號(hào)匹配, 棧不為空, 括號(hào)不匹配
  return result_stack.isEmpty()

補(bǔ)充：Python中的棧

在python中，個(gè)人理解為?？梢杂昧斜韥?lái)代替

服從FILO：First In Last Out

其中入棧為（利用append函數(shù)）

stack = []
stack.append(<item>)

出棧為（利用pop函數(shù)）

stack.pop(-1) #stack.pop()也可

服從FIFO：First In First Out

入棧為：

stack = []
stack.append(<item>)

出棧為：

stack.pop(0)

總結(jié)

以上所述是小編給大家介紹的使用Python實(shí)現(xiàn)一個(gè)棧判斷括號(hào)是否平衡，希望對(duì)大家有所幫助，如果大家有任何疑問(wèn)請(qǐng)給我留言，小編會(huì)及時(shí)回復(fù)大家的。在此也非常感謝大家對(duì)腳本之家網(wǎng)站的支持！

您可能感興趣的文章: