使用Python實現(xiàn)一個棧判斷括號是否平衡

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

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

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

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

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

棧的實現(xiàn) 下面就通過借助Python的列表，來自定義一個棧類：

class Stack(object):
  """使用數(shù)組實現(xiàn)一個棧"""
  def __init__(self):
    self.data = []
  def push(self, num):
    """壓棧操作"""
    self.data.append(num)
  def pop(self):
    """返回從棧中彈出的元素, 當棧為空的時候, 拋出IndexError"""
    return self.data.pop()
  def peek(self):
    """查看當前棧頂?shù)脑? 當棧為空的時候, 拋出IndexError"""
    return self.data[-1]
  def __len__(self):
    """返回棧的長度, 調(diào)用len(obj)時會自動調(diào)用obj對象的__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):
    """當前對象的表現(xiàn)形式, 在終點直接鍵入對象時會調(diào)用"""
    return 'Stack_' + str(self.data)
  def __str__(self):
    """當前對象的字符串表示, 使用print(obj)時會調(diào)用"""
    return 'Stack_' + str(self.data)

以上代碼實現(xiàn)了一個簡單的基于列表的棧。

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

(...)...(...)
(...)...(...
)...((...)
def isBalance(text):
  """棧的應用,檢查括號是否平衡"""
  result_stack = Stack()
  for i in text:
    if i in ['{', '[', '(']:
      result_stack.push(i)
    elif i in ['}', ']', ')']:
      # 遇到結(jié)束括號的情況
      if result_stack.isEmpty():
        # 如果當前棧為空, 不匹配,返回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é)果棧為空, 則代表括號匹配, 棧不為空, 括號不匹配
  return result_stack.isEmpty()

補充：Python中的棧

在python中，個人理解為棧可以用列表來代替

服從FILO：First In Last Out

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