逆ポーランド記法とは何でしょうか。日本語プログラミング言語「なでしこ」を使う場合、どのように実装すれば良いでしょうか。２点について紹介します。
逆ポーランド記法とは
Wikipediaが分かりやすいです。
逆ポーランド記法（ぎゃくポーランドきほう、英語: Reverse Polish Notation, RPN）は、数式やプログラムの記法の一種。演算子を被演算子の後にすることから、後置記法 (Postfix Notation) とも言う。
その他の記法として、演算子を被演算子の中間に記述する中置記法、前に記述する前置記法（ポーランド記法）がある。 名称の由来は、演算子と被演算子の順序がポーランド記法の逆になっていることによる。
具体的に言うと・・・
例えば、「3 と 4 を加算する」という演算を、一般的に数式の表記に用いられる中置記法で記述すると、以下のようになる。
3 + 4
一方、逆ポーランド記法では、加算を表す演算子 + を、被演算子である 3 と 4 の後（右）に置いて、以下のよう記述する。
3 4 +
この書き方って、助詞を加えると次のようになり、なでしこの日本語記述方式と似ていますね。
3(に) 4(を) +(足す)
どのように逆ポーランド記法を計算すれば良いか
逆ポーランド記法を計算するには、次の手順で計算すれば良いのです。
- (1) 文字列を空白でトークンに区切る
- (2) トークンを1つ読む
- (3) 数値なら、スタックに積む
- (4) 演算子なら、スタックから2つ値を取り出して計算してスタックに積む
- (5) トークンが空でなければ(2)に戻る
- (6) スタックに残っている値が答えとなる
さっそくなでしこで作ってみよう
それでは、上記の手順に基づいて逆ポーランド記法を実装してみましょう！
ちなみに、タイムトライアルで何分で作れるか測ってみましょう！
以下が答えです。こちらの貯蔵庫から実行できます。
式エディタ＝「3 5 +」のエディタ作成。
計算ボタン＝「計算」のボタン作成
結果エディタ＝「」のエディタ作成。
計算ボタンをクリックした時には
S=(式エディタからテキスト取得)
Sを逆ポーランド計算して答えに代入。
結果エディタに答えをテキスト設定。
ここまで。
●（Sを）逆ポーランド計算とは
スタックは[]
Sを「 」で区切って反復
C=対象
「+-*/%」でCが何文字目
もし、そうならば
B=スタックから配列ポップ。
A=スタックから配列ポップ。
もし、C=「+」ならば
スタックに(A+B)を配列追加💧
もし、C=「-」ならば
スタックに(A-B)を配列追加💧
もし、C=「*」ならば
スタックに(A*B)を配列追加💧
もし、C=「/」ならば
スタックに(A/B)を配列追加💧
もし、C=「%」ならば
スタックに(A%B)を配列追加💧
違えば
C=INT(C)
スタックにCを配列追加。
ここまで。
# スタックをJSONエンコードして表示。
ここまで。
スタックから配列ポップ。
ここまで。
タイムトライアルで、だいたい10分くらいで実装できました！
皆さんは、手順を見てどのくらいの時間で実装できるでしょうか。
まとめ
以上、逆ポーランド記法は「スタック構造」を使うと、簡単に計算できることも分かったと思います。いろいろな定番アルゴリズムをなでしこで実装するのは楽しいと思いますので挑戦してみてください！
ちなみに、この記事を書くのもタイムトライアルでした。
貯蔵庫へプログラムの投稿も含めて20分でやりきりました！！
投稿に際して、Twitterの認証コードを入れるのが一番時間かかったかも。。。