[10/18/2012] Challenge #104 [Hard] (Stack Attack) : dailyprogrammer
問題
あのDijkstraが発明した手法だそう。
説明
あなたは邪悪なエンジニアであり、D++という新しい言語を作ろうとしている。これはあなたのお気に入りの計算機科学者にちなんで"Dijkstra++"という意味を込めている。
さて、この言語のインタプリタに数式をパースする機能をつけたい。もっとも、あなたの言語は外部的には中置記法（infix notation, 例: "1+2*3"）しかサポートせず、内部的にはその数式文字列を逆ポーランド記法で扱いたい（reverse polish notation, スタックベースであり計算しやすい）。この問題では、正しい中置記法の数式が与えられたさい、それを逆ポーランド記法に変換するプログラムを書いていただきたい。入出力例
"1 + 2" => "1 2 +" "(1+2)*3" => "3 2 1 + *" "(6 * (7 - 2)) / 3 + 9 * 4" => "6 7 2 - * 3 / 9 4 * +"ノート
操車場アルゴリズム - Wikipediaを大いに参考にしましょう。
まず単純な場合を考える
というのも、簡単な部分問題を解くことによって一般的な問題に対する展望がひらけることがあるからだ。2つの数と1つの中置演算子をパースするような関数infix2rpnを書こう。また簡単のために式中の数値は0≦n≦9とする。
infix2rpnに期待する動作を先に書いておこう。noseというテストツールを初めて使ってみた。
from nose.tools import eq_ def test_simple_infix2rpn(): eq_(infix2rpn("3+4"), "3 4 +") eq_(infix2rpn("3-4"), "3 4 -") eq_(infix2rpn("4*2"), "4 2 *") eq_(infix2rpn("4/2"), "4 2 /") if __name__ == "__main__": import nose nose.main()
さて、この単純な式("3+4")の変換手順は以下のように示される。
手順を操車場として図示すると以下のとおり。
右が入力、左が出力、下が演算子スタックである。手描きでちょっと詰まりすぎて見づらいかも。
実装はこうなる。
# rpn: reverse polish notation def infix2rpn(expression): rpn_stack = [] # 出力キュー operator_stack = [] # 演算子スタック operators = "+-*/" for character in expression: if character.isdigit(): rpn_stack.append(character) # 数値ならばキューに追加 elif character in operators: operator_stack.append(character) # 演算子ならば演算子スタックへ rpn_stack.extend(operator_stack) # 演算子をすべてキューへ return " ".join(rpn_stack)
演算子の判定が単純にすぎるきらいがあるが、とりあえず2数値1中置演算子の式はこれで正しく変換できているのでよしとしよう。
一般的な場合
入力例
"3 + 4 * 2 / ( 1 - 5 )"
を考えよう。
これは単純なケースと何が違うだろうか。まず新しい記号が追加されている。()は囲まれた部分の計算を優先して行うことを意味する記号だ。また演算子が1つだけではない。直感的に、演算子が2つ以上に増えると最初のプログラムでは問題があるように思える。演算子には結合の優先順位があるからだ。どのように考えたらよいのだろう。
……分からない。どうもまだ一息で扱うには複雑すぎる問題であるように思える。幾つかの小さい問題に分割してみよう。
部分問題 1. 四則演算
まず和と積の優先順位を考える。手で中置演算式を書き下してみる。
"3 + 4 * 2" # => (3 + (4 * 2)) => 11
これの逆ポーランド表現は次のようになる。
"3 4 2 * +" # => (3 (4 2 *) +) => (3 8 +) => 11
infix2rpnに関するテストコードを追加しよう。
def test_operator_priority(): eq_(infix2rpn("3 + 4 * 2"), "3 4 2 * +")
これを現行のinfix2rpnについて実行してみると以下のような結果になる。
AssertionError: '3 4 2 + *' != '3 4 2 * +'
左辺を見ると、演算子の順序が期待されるものとは逆になっていることが分かる。*が先に計算されるようにしなければならない。具体的にどうすればよいのか。トークンを処理するさい、+と*の演算子の優先順位を比較して演算子スタックを操作する必要がある。
Wikipediaの記述を引く。
左結合という言葉が出てきたが、これはひとまず無視する。四則演算については演算子は左結合だからだ。
それにしても2行目の条件がやや飲み下しづらい文章かもしれない。
少し実例を見てみよう。
例題 1.1
例えば"3 + 4 * 2"において+と*の比較とスタックの操作は次のように行われる。
例題 1.2
では"3 * 4 + 2"の場合はどうなるだろうか？
優先順位の高い演算子がスタックに積まれている場合は、それをpopして出力キューに移動する。
この場合、入力と演算子スタックの比較は繰り返し行う。
例題 1.3
比較の繰り返しは、"3 + 4 * 2 + 1"を例にするとこうなる。
(1)まず演算子スタックの*と入力+を比較し、*を出力キューに移動する。
(3)演算子スタックが空なので入力+をpushする。
以上の例題3つをテストにまとめておく。
def test_operator_priority(): eq_(infix2rpn("3 + 4 * 2"), "3 4 2 * +") eq_(infix2rpn("3 * 4 + 2"), "3 4 * 2 +") eq_(infix2rpn("3 + 4 * 2 + 1"), "3 4 2 * + 1 +")
実装
さて、パースの仕方がわかったのでいよいよ実装していこう。
四則演算子の優先順位を次のように定義する。
plus = "+" minus = "-" mul = "*" div = "/" operator_priority = { plus : 2, minus: 2, mul : 3, div : 3 }
infix2rpnは次のように書きなおす。
def infix2rpn(expression): rpn_stack = [] operator_stack = [] for character in expression: if character.isdigit(): rpn_stack.append(character) elif operator_priority.has_key(character): # 演算子スタックが空でなく、かつ # 演算子スタックの最上部の演算子の優先順位が # 入力演算子の優先順位より高いあいだ while operator_stack and \ operator_priority[operator_stack[-1]] >= operator_priority[character]: rpn_stack.append(operator_stack.pop()) # 演算子スタックをpopして出力に加える operator_stack.append(character) operator_stack = list(reversed(operator_stack)) # 残った演算子は頭から結合する rpn_stack.extend(operator_stack) return " ".join(rpn_stack)
これで一桁の数値の中置式四則演算に関して問題なく逆ポーランド記法を出力するプログラムが完成した。
あとはこのコードに細かな磨きをかけていくだけだ。
部分問題 2. カッコで演算の優先順位を変更する
左カッコが来たときはそのまま演算子スタックにpushする。
問題は右カッコの場合だ。右カッコが入力された場合、演算子スタックから左カッコが現れるまで繰り返しpopして、出力に演算子を加えていく必要がある。今回は入力の正しさが前提として保証されているので、カッコの対応エラーを考慮する必要はない。
ところで左カッコは演算子スタックに積むので優先順位を決めておく。カッコはなんら計算を行わないので最も低い優先順位でよいだろう。
left_paren = "(" right_paren = ")" operator_priority = { plus : 2, minus: 2, mul : 3, div : 3, left_paren : -1, right_paren: -1 }
以上を踏まえてinfix2rpnは次のように書く。
is_paren = lambda c: c == right_paren or c == left_paren def infix2rpn(expression): rpn_stack = [] operator_stack = [] for character in expression: if character.isdigit(): rpn_stack.append(character) elif operator_priority.has_key(character) and not is_paren(character): # カッコは出力に含めない while operator_stack and \ operator_priority[operator_stack[-1]] >= operator_priority[character]: rpn_stack.append(operator_stack.pop()) operator_stack.append(character) elif character == left_paren: operator_stack.append(character) elif character == right_paren: # 左カッコが現れるまで演算子スタックから出力へ積んでゆく while operator_stack[-1] != left_paren: rpn_stack.append(operator_stack.pop()) operator_stack.pop() # 左カッコそのものは捨てる operator_stack = list(reversed(operator_stack)) rpn_stack.extend(operator_stack) return " ".join(rpn_stack)
これにて所与の入力例をすべてパスする関数が実装できた。ヽ(´ー｀)ノﾊﾞﾝｻﾞｰｲ
def test_parenthesis(): eq_(infix2rpn("(3 + 4) * 2"), "3 4 + 2 *") eq_(infix2rpn("(6 * (7 - 2)) / 3 + 9 * 4"), "6 7 2 - * 3 / 9 4 * +")
右結合や大きな数の取り扱い(tokenizeする)は気が向いたらやります(´・ω・｀)
感想
- スタックと分岐をちゃんと使うことができれば解くことができるのでいい練習になった。
- 変数名長すぎ？
- 解説くどすぎ？
- いちおう自力で書いたけど汚くなったところはここを見て手直ししていたりするshuntingyard/shuntingyard.py at master · ekg/shuntingyard
