Brackets (Electronic Station) 括弧をチェック

どんな問題？

Brackets
http://www.checkio.org/mission/brackets/

いつものように、ストーリーは華麗にスルー。

数式で正しく括弧が使われているかをチェックせよ。

数式は'((5+3)*2+1)' のような文字列
数字や記号は無視する
括弧は { } ( ) [ ] の3種類
正しく括弧が使われていれば True、でなければ False

例はこちら。

checkio("((5+3)*2+1)") == True
checkio("{[(3+1)+2]+}") == True
checkio("(3+{1-1)}") == False
checkio("[1+1]+(2*2)-{3/3}") == True
checkio("(({[(((1)-2)+3)-3]/3}-3)") == False

どうやって解く？

こういう構文解析って定番のやり方があるんだろうなと思って、「括弧アルゴリズム」で検索したら、いっぱい出てきた。でも、先に見てしまうとつまらないので、最初は何も見ずに解いてみることにする。

まず、頭から1文字ずつチェックして、{ ( [ が出てきたら階層を1下げる、] ) } が出てきたら階層を1上げる、ペアの組み合わせが間違ってたらNG、文字列の最後まで調べて、終わったときに階層が0ならOK、こんな感じでいけそう。括弧をスタックに入れていく形になりそうだ。

Pythonでのスタックとキュー

ところで、PythonってQueueクラスはあるのに、Stackクラスはないのかな。スタックはどうすればいいんだ？
調べてみたら、どちらもリストを使えばいいだけらしい。

スタック(stack)	list.append() で追加、list.pop()で最後の要素を取り出す
キュー(queue)	list.append() で追加、list.pop(0)で最初の要素を取り出す

ただし、pop(0)は遅いので、collections.dequeクラスを使うとよい。
右に追加(append)、左に追加(appendleft)、右側から取り出す(pop)、左側から取り出す(popleft)メソッドがあって、スタックでもキューでも高速に処理できる。さらに反転(reverse)、ローテート(rotate)などもできる優れもの。（そういや、先日の Open Labyrinth でもdeque.rotate使ったっけ。）

queue.Queueクラスはマルチスレッド対応が必要なときに使う、ってことかな？

dequeクラス http://docs.python.jp/3.3/library/collections.html#collections.deque
Queueクラス http://docs.python.jp/3.3/library/queue.html

コード書いてみた

open_brackets = ('(', '[', '{')
close_brackets = (')', ']', '}')

def checkio(expr):
    stack = []
    for c in expr:
        if c in open_brackets:
            stack.append(c)
        elif c in close_brackets:
            if len(stack) == 0:
                return False  # 開く括弧が不足
            else:
                last = stack.pop()
                if open_brackets.index(last) != close_brackets.index(c):
                    return False  # 括弧の種類が違う
    if len(stack) != 0:
        return False  # 閉じる括弧が不足
    return True

テストはあっさりクリア。

でも、実際にこういう構文解析するときには、True/Falseじゃなくて、例外処理を使って、詳しいメッセージを出すよなぁ。そういう場合は、どう書けばいいんだろう？

def check_brackets(expr):
    # 問題があるときは例外発生させる。例、raise BracketError('}が足りません')
    # 何も問題なければ、return True
    pass

def checkio(expr):
    try:
        return check_brackets(expr)
    except BracketError as e:
        # ここでエラーメッセージを表示する
        return False

みたいな感じでいいのかな？

他の人の答え

だいたい似たような感じか。正規表現を使っている人もいた。

いろいろ見てると、自分のを直したくなってくる。まず、Pythonは定数を全部大文字で書くんだっけ？
（別に見た目の問題だけで、機能的には普通の変数と同じなんだが。）

OPEN_BRACKETS = ('(', '[', '{')

と書いた方がわかりやすいな。

OPEN_BRACKETS = '([{'

でもいいけど、タプルの方が見やすいか。

if open_brackets.index(last) != close_brackets.index(c):

この、括弧のペアチェックも、別の関数 is_pair_bracket() とした方がわかりやすいかな。

OPEN_BRACKETS = ('(', '[', '{')
CLOSE_BRACKETS = (')', ']', '}')

def is_pair_bracket(o, c):
    return OPEN_BRACKETS.index(o) == CLOSE_BRACKETS.index(c)

def checkio(expr):
    stack = []
    for ch in expr:
        if ch in OPEN_BRACKETS:
            stack.append(ch)  # push open bracket
        elif ch in CLOSE_BRACKETS:
            if len(stack) == 0:
                return False
            o = stack.pop()  # pop open bracket
            if not is_pair_bracket(o, ch):
                return False
    return len(stack) == 0

完成！

summer_tree_home

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