[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()