Parse Array (Home) - リストの構文解析
Home島に新しい問題が追加されていた。例題だけ見て面白そうな問題だなぁと思い、問題文をろくに読まずに解いたのだが、後から他の人の答えを見てびっくり。この問題は、普通に解くのではなく、あらかじめ書いてある解答のバグを見つけて修正せよ、という問題だった・・・。orz
教訓:問題文はちゃんと読みましょう。
どんな問題?
Parse Array
http://www.checkio.org/mission/parse-array/
文字列で書かれたリストを構文解析して、リストを得よ。
※このタスクでは、あらかじめ解答が与えられる。ただし、この解答にはバグがあるので、このバグを見つけて修正せよ。
リストの要素には、整数またはネストしたリストが含まれている。ネストの深さは5未満。
整数値には、「+」または「-」記号が先頭に付くことがある。整数値は-1000<x<1000
文字列が正しいリスト形式でないときは、ValueError例外を発生させること。
例題:
parse_array("[1, 2, 3]") == [1, 2, 3] parse_array("[[1], 2, 3]") == [[1], 2, 3] parse_array("[-3, [-2, 0], 10]") == [-3, [-2, 0], 10]
どうやって解く?
問題の意図とは違う解答だけど、せっかくなので、自分の書いたコードを紹介しておく。
(あらかじめCheckiOエディタに解答が書いてあったから、変だなぁとは思ってたんだけど、深く気にしてなかった・・・。)
一番外側のリストの要素を列挙して、要素がリストなら、そのリストの要素を列挙、、、という形で処理すればよさそうだ。再帰を使えば、簡単に書けそうだ。
def recurse(parent, s): for e in get_list_elements(s): # リストの要素を列挙 if is_list(e): # 要素がリスト parent.append(recurse([], e)) elif is_integer(e): # 要素が整数 parent.append(int(e)) else: raise ValueError return parent def parse_array(s): return recurse([], s)
あとは、get_list_elements()、is_list()、is_integer()を実装すればいい。リストの要素を列挙するときは、「[」と「]」の数を数えて、深さ0のときだけコンマをスプリッタとして扱う。
def get_list_elements(s): s = s.strip() if not is_list(s): raise ValueError level = 0 token = '' for c in s[1:-1]: # sの[]を除去 if c == '[': # [ なら深さ+1 level += 1 elif c == ']': # ] なら深さ-1 level -= 1 if level == 0 and c == ',': # 深さ0のコンマ token = token.strip() if token != '': yield token token = '' else: # コンマの前の要素が空ならエラー 例:[1,,2] raise ValueError else: token += c token = token.strip() if token != '': # 最後の要素が空なら何もしない 例:[1,2,] → [1,2] yield token
いくつか、はまった点があった。
- ホワイトスペースの処理。最初に引数sをstripして、要素を返すときにもstripするようにした。
- [1,,2]では例外発生させるが、[1,2,]では例外発生させてはいけない。これは、コンマの前のtokenが空なら例外、最後のtokenが空のときは何もしない、という処理にすることで対応した。
まとめ
def is_integer(s): return all(c in '-0123456789' for c in s) def is_list(s): return s[0] == '[' and s[-1] == ']' def get_list_elements(s): s = s.strip() if not is_list(s): raise ValueError level = 0 token = '' for c in s[1:-1]: if c == '[': level += 1 elif c == ']': level -= 1 if level == 0 and c == ',': token = token.strip() if token != '': yield token token = '' else: raise ValueError else: token += c token = token.strip() if token != '': yield token def recurse(parent, s): for e in get_list_elements(s): if is_list(e): parent.append(recurse([], e)) elif is_integer(e): parent.append(int(e)) else: raise ValueError return parent def parse_array(s): return recurse([], s)
http://www.checkio.org/mission/parse-array/publications/natsuki/python-3/first/
公開後に見直すと、is_integer()が手抜き過ぎだなぁ。そもそも「+」を考慮してないし、「1-23」のように符号が数字の先頭でなくてもエラーにならない。
新しい問題だからって、急いで解こうとして失敗してしまった。。。( ´・ω・)ショボン