summer_tree_home

Check iOでPython3をマスターするぜっ

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」のように符号が数字の先頭でなくてもエラーにならない。


新しい問題だからって、急いで解こうとして失敗してしまった。。。( ´・ω・)ショボン