FreeStyleWiki

操車場アルゴリズムと逆ポーランド記法

このエントリーをはてなブックマークに追加

[数学]

操車場アルゴリズムと逆ポーランド記法

  • 操車場アルゴリズム
    • 操車場アルゴリズム(Shunting-yard algorithm)を使うと、数式をいい感じに逆ポーランド記法に変換できる

出力を出力順にそのまま並べれば逆ポーランド記法 (RPN) になるし、あるいは抽象構文木を構築したり、数値と四則演算等の算術式のようなものであればその場で直接計算結果を得てしまってもよい

便利

  Rubyでの実装

  • Wikipediaの記事をもとに、Rubyでの実装を作ってみた
    • べき乗に「^」以外に「**」を使えるようにしている以外はほぼWikipediaのアルゴリズムと変わらない

+ 操車場アルゴリズムRubyソース

  • これはしかし実行してみると問題がある
# 数字のみだとうまくいく
@shuting_yard = ShutingYard.new
tokens = @shuting_yard.tokenize("3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3")
prn = @shuting_yard.parse(tokens).join(" ")
expect(prn).to eq "3 4 2 * 1 5 - 2 3 ^ ^ / +"

  二項演算子と単項演算子は異なる

一方-のときは、勝手に取り外すわけにも行きません。

ですが、二項演算子としての-と混同するのもよくないので、代わりに~という演算子に差し替えました。

さらっと重要なこと書いてないか?そのへんの整理を次はしていきたい。

上記作者様のサイトでの例を上の操車場アルゴリズムに入れてみる

@shuting_yard = ShutingYard.new
tokens = @shuting_yard.tokenize("((-37*x)^2 + (-y)^2 + a^2 - 3*((-x)*y+(-3)*a)^2*a + 3*a*(-x))^5")
prn = @shuting_yard.parse(tokens).join(" ")

expect(prn).to eq "37 x * - 2 ^ y - 2 ^ + a 2 ^ + 3 x - y * 3 - a * + 2 ^ * a * - 3 a * x - * + 5 ^"  # 操車場アルゴリズム
                  "37 ~ x * 2 ^ y ~ 2 ^ + a 2 ^ + 3 x ~ y * 3 ~ a * + 2 ^ * a * - 3 a * x ~ * + 5 ^"  # 二項演算子/単項演算子が区別される
                      ^           ^                   ^       ^                           ^

  Next