カッコの対応を判定する[10/18/2012] Challenge #104 [Intermediate] (Bracket Racket) : dailyprogrammer

[10/18/2012] Challenge #104 [Intermediate] (Bracket Racket) : dailyprogrammer

問題文

カッコ"()", カギカッコ"[]", 波カッコ"{}", 山カッコ"<>" を含む文字列がちゃんと対応して閉じているか確認する。

入力と出力の形式

入力は文字列、返り値は真偽値。

サンプルインプット

True: "123", "(abc)", "()abc()", and "([<{abc123abc}>])"
False: "(abc[123)abc]", "(abc>"

解答

def brackets_valid(string):
    stack = []
    left = "([{<"
    right = ")]}>"
    for char in string:
        if char in left:
            stack.append(char)
        elif char in right:
            if not stack:
                return False
            c = stack.pop()
            lindex = left.index(c)
            rindex = right.index(char)
            if lindex != rindex:
                return False
    return not stack

思いつきで、

left = "([{<"
right = ")]}>"

などとしてindexから対応しているかどうか判断している。
これが駄目なのはすぐわかる。なぜかというと、異なる変数leftとrightの順序関係を暗に前提としているから。変更を加えづらくなっている。
でもどうやって書きなおせばいいのか思いつかない。
あとあとのことを考えると

pairs = ["()", "[]", "{}", "<>"]

としたほうがすっきりするんだろうけど面倒になってきた。

テストコードを書いた。

from nose.tools import eq_

def test_brackets_valid():
    eq_(brackets_valid("123"), True)
    eq_(brackets_valid("<"), False)
    eq_(brackets_valid(">"), False)
    eq_(brackets_valid("()"), True)
    eq_(brackets_valid("([])"), True)
    eq_(brackets_valid("([{<>}])"), True)
    eq_(brackets_valid("([<]>)"), False)
    eq_(brackets_valid("([abcd])"), True)
    eq_(brackets_valid("([ab)cd])"), False)
    eq_(brackets_valid("()abc()"), True)
    eq_(brackets_valid("(abc[123)abc]"), False)

if __name__ == "__main__":
    import nose
    nose.main()