Webページでは数式を表すためにLaTeX表記が使えるMathJaxを利用しています。 WebブラウザにはSafari/Chrome/Firefoxを使って下さい（IEでは表示できないようです。）

データクラス stack

スタック（stack）はデータの並びが1次元的で、しかもデータアクセスにLIFO（Last-In First-Out）の制約がついたデータ構造をしている。

Pythonでは、Python入門(6)リストで紹介したように、リストデータ list に対して list.pop() や list.append(item) のようなスタック的メソッドが用意されているが、list.insert(item) のようなスタック構造には許されていないメソッドも併せて定義されているので（これらは大変便利なメソッドではあるが）、ここでは「純粋に」スタックデータクラスを定義して、これを利用したアルゴリズムを考えよう。

stackクラスのインスタンス mystack には次のメソッドが定義される。

Pythonでstackクラスを定義する

stackクラスの定義に従って、リストデータを使って以下のように書いてみよう。 スタックトップの位置は、リスト末尾 len(self.items)-1 であること、 空スタックのサイズは 0 であることに注意する。

class stack:
    def __init__(self):
       self.items = []
       
    def is_empty(self):
       return self.items == []
       
    def push(self, item):
       self.items.append(item)
       
    def pop(self):
       return self.items.pop()
       
    def peek(self):
       return self.items[len(self.items)-1]
       
    def size(self):
       return len(self.items)

このスタックトップの位置をリスト末尾としてstackクラスを定義する以外に、次のようにスタックトップをリストの先頭と考え、stackクラスのメソッドを定義することも可能である。

  def push(self, item):
    self.items.insert(0, item)

  def pop(self):
    return self.items.pop(0)

  def peek(self):
    return self.items[0]

括弧の対応の整合性を調べる

スタックを使った典型的な応用として、括弧の対応を調べる問題がある。 多くのテキストエディタにも組み込まれており、括弧 ( { [ がそれぞれ ]}) に「合理的に」対応しているかをチェックするものだ（たとえば ( { [ と ) } ] とは合理的対応にはない ）。

括弧の対応がとれているかどうかは、記号列を左から右へと読んでいったときに、直前の開き括弧 ( { [ どれかがが今注目している同じ種類の閉じ括弧 ] } ) に対応しているかを調べればよい。

まず、簡単のために、括弧文字からだけからなる文字列、それも1種類の括弧文字列だけならなる場合の処理を考えてから、他の記号も混じった文字列での1種類括弧の整合性を検出してみる。 次に、複数の括弧文字列だけなる括弧対応の整合性を調べてから、他の記号が混じった場合に拡張する。 最後に、引数で指定したファイルの括弧対応の整合性の検出スクリプトを書いてみよう。

1種類の括弧対応

簡単のために括弧が ( と ) の1種類の場合、文字 ( と ) からだけからなる文字列 given_string において括弧が対応しているかを判定してboole値を返す関数 parenthese_balance(given_string) は次のようになる。

5,6行で、まず括弧の対応がとれているとして balanced を True に、文字列内の指定した位置にある文字にアクセスするための添字 index を先頭の 0 にセットする。 7,8行で、与えられた文字列範囲内で balanced が True であるときに、while文で文字列 given_string の index 位置にある文字 given_string[index] を調べていく。

開き括弧 ( が見つかったら、スタックにプッシュし、そうでない、つまり対応する文字 ) が見つかったら、空でないスタック（にある直前の文字 ( ）をポップする。 そうして、次の文字列位置を調べていく。 こうして全ての文字を調べ終わったときに、balanced が True で、スタックが空であるときにだけ、文字列の括弧対応がとれていたとするのである。

# declaration of stack class is assumed

def parenthese_balance(given_string):
    st = stack()
    balanced = True
    index = 0
    while index < len(given_string) and balanced:
        symbol = given_string[index]
        if symbol == "(":
            st.push(symbol)
        else:
            if not st.is_empty():
                st.pop()
            else:
                balanced = False
        index = index + 1
    if balanced and st.is_empty():
        return True
    else:
        return False

print parenthese_balance('()(()())')

3種類の括弧対応

given_string の括弧文字が ( と ) だけでなく、{ と } および [ と ] だけからなる場合に、それらが「対応している」かを判定してboole値を返すように関数 parenthese_balance(given_string) を修正してみよう。

文字列の先頭から読み込んだ記号 symbol が開き括弧 (, {, [ のどれかである判定するために、Python的に9行目のように書くことができる。 その開き括弧記号 symbol をスタックにプッシュする。

そうでないとき（(,{,[ のどれかではない、つまり閉じ括弧 ), }, ] のどれかの記号 symbol を読みこんだとき）、12行目でスタックが空でないことを確認した上で、14行目で関数 is_correspond を使ってスタックトップからポップした記号 top と読み込んだ記号 symbol とが対応していばければその時点で balanced 値 を False とする。 17行目にあるように、記号 symbol を読みこんだときうにスタックが空であるときもbalanced 値 を False とするのである。

# declaration of stack class is assumed

def parenthese_balance(given_string):
    st = stack()
    balanced = True
    index = 0
    while index < len(given_string) and balanced:
        symbol = given_string[index]
        if symbol in "({[":
            st.push(symbol)
        else:
            if not st.is_empty():
                top = st.pop()
                if not is_correspond(top, symbol):
                    balanced = False
            else:
                balanced = False
        index = index + 1
    if balanced and st.is_empty():
        return True
    else:
        return False

def is_correspond(open, close):
    openep = "([{"
    closedp = ")]}"
    return openp.find(open) == closedp.find(close)

括弧記号が対応しているかを判定する関数 is_correspond(open, close) は、与えておいた開き括弧文字列 openp および閉じ括弧文字列 closedp から記号 open と close のある文字位置を比較するというようにして判定させている。

指定したファイルの括弧対応の整合性

$ ./parenthese_balance.py my_program.cc
True