ソフ開のアルゴリズムの勉強

ソフ開で出題されるアルゴリズムの理解を深めるために実装してみるコーナー。
「スタックを用いて括弧の対応を調べる」

開き括弧を見つけると、括弧のある行数と位置をスタックに積む。
閉じ括弧を見つけると、スタックに中身があれば、2回POP()（行数と位置の情報を捨てる）を行う。
スタックに中身がなければ、括弧の対応が取れていないので、エラー情報を吐き出す。

全ての行数をチェックし終わった後に、スタックの中を見る。
スタックに要素が残っていると、閉じ括弧との対応が取れていない開き括弧の存在と場所が分かる。

# -*- encoding : utf-8 -*-

def check():
    f = open("kakko.txt", "r")

    stack = []
    line = 0
    pos = 0
    for lines in f.readlines():
        line += 1
        for ch in lines:
            pos += 1
            if ch != "\n":
                k = kind(ch)
                if k == 1:
                    stack.append(pos)
                    stack.append(line)
                elif k == 2:
                    if len(stack) > 0:
                        stack.pop()
                        stack.pop()
                    else:
                        print u"対応する開き括弧がありません"
                        print "Line:%d Position:%d\n" % (line, pos)
        pos = 0

    if len(stack) > 0:
        while len(stack) > 0:
            print u"対応する閉じ括弧がありません"
            print "Line:%d Position:%d\n" % (stack.pop(), stack.pop())


def kind(ch):
    if ch == "(":
        return 1
    elif ch == ")":
        return 2
    else:
        return 0
def main():
    check()


if __name__ == "__main__":
    main()

↑のコードで↓のファイルを調べた。

(1+2)
abc)
((def)gx))
(((h)
ij)(k
(lml)

結果

D:\workspace>python check.py
対応する開き括弧がありません
Line:2 Position:4

対応する開き括弧がありません
Line:3 Position:10

対応する閉じ括弧がありません
Line:5 Position:4

対応する閉じ括弧がありません
Line:4 Position:1

うまく動いている。
ちなみに、この実装では括弧の種類が一種類の場合にのみ対応。