Pythonを使用してスタックを実装し、カッコがバランスしているかどうかを判断します.

スタック(Stack)はコンピュータの分野で広く応用されている集合であり、スタックは線形集合であり、アクセスはすべて厳密に1段に制限され、トップと呼ばれている.(top).例を挙げると、スタックはきれいに洗った皿を積み重ねたいと思っています.新しい皿を取るたびに、この皿の一番上に置いています.中に皿を追加するときも、一番上に置いて、底にある皿で、永遠に使えないかもしれません.スタックの最も一般的な操作は、次の2つあります.

push(a) #   ， a     
pop(） #   ，           

しかしPythonのリストデータ構造を用いてスタックの操作をシミュレートし,appendを用いてpushをシミュレートし,リストのpopを用いてスタックのpopをシミュレートしたが,これにはリストが本来持っている操作方法と同様に使用でき,混乱をもたらす可能性があるという弊害がある.

スタックの実装は、Pythonのリストを使用して、スタッククラスを定義することによって、

に続く.

class Stack(object):
    """         """
    def __init__(self):
        self.data = []

    def push(self, num):
        """    """
        self.data.append(num)

    def pop(self):
        """          ,        ,   IndexError"""
        return self.data.pop()

    def peek(self):
        """         ,        ,   IndexError"""
        return self.data[-1]

    def __len__(self):
        """      ,   len(obj)      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):
        """         ,              """
        return 'Stack_' + str(self.data)

    def __str__(self):
        """          ,   print(obj)    """
        return 'Stack_' + str(self.data)

以上のコードは、リストベースの単純なスタックを実現しています.

スタックのアプリケーションスタックアプリケーションの典型的な例は、カッコが一致しているかどうかを確認することである.例えば、各開始の[の後には、正しい位置の]が続くべきであり、各(の後には、正しい位置の終了の)が続くべきである.

(...)...(...)マッチング

(...)...(...不整合

)...((...)不整合像第3例では、左右の括弧の数は等しいが不整合であるため、簡単な検査数で括弧の検出を実現することはできない.1つの非常に効果的な解決策はスタックを使用することです:

文字列全体をスキャンし、開始カッコに遭遇した場合はスタックに

を押し込む

終了括弧に遭遇した場合、スタックの一番上の要素をチェックし、終了括弧であれば、現在の括弧をスタックに押し込み、開始括弧であれば、現在の括弧とペアリングできるかどうかをチェックし、ペアリングできない場合は

に一致しません.

終了括弧に遭遇し、現在のスタックが空の場合も一致しません.コード実装は、

def isBalance(text):
    """    ,        """
    result_stack = Stack()
    for i in text:
        if i in ['{', '[', '(']:
            result_stack.push(i)
        elif i in ['}', ']', ')']:
            #          
            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

    #      ,        ,        ,     ,      
    return result_stack.isEmpty()