リバースポーランドへようこそ
なんか意味もなくLispいじりながら、ブログネタ探しにIPA試験の項目眺めてたら丁度よさげなネタがあったので今日は逆ポーランド記法とかの話でもしようと思います。このブログを読んでいる聡明な読者の皆様ならご存知だと思いますが、今日はこのネタで記事でも書いていきます。
逆ポーランド記法とは、この世界とは逆の存在にすむリバースポーランド人の使う公用語のことです [要出典]。嘘です。
逆ポーランド記法(ぎゃくポーランドきほう、英語: Reverse Polish Notation, RPN)は、数式やプログラムの記法の一種。演算子を被演算子の後にすることから、後置記法 (Postfix Notation) とも言う。
その他の記法として、演算子を被演算子の中間に記述する中置記法、前に記述する前置記法(ポーランド記法)がある。
逆ポーランド記法でも、演算子早出し逆ポーランド記法 ERP(early-operator reverse Polish notation)と、演算子遅出し(late-operator)逆ポーランド記法 LRP の分類があり、特に演算子早出し逆ポーランド記法は「その記号の配列順を些かも崩さずに和文に移せる」という特徴がある。
こんなのです。
何言っているのかサッパリなので具体的な問題を解いていきましょう。問題で言うとこんなのがわかるようになります。
A=1,B=3,C=5,D=4,E=2 のとき,逆ポーランド表記法で表現された式 AB+CDE/-* の演算結果はなにか。
解法
以下のように、後ろの式を直前の値で計算してやっていくと解けます。
AB+CDE/-*
(A+B)C(D/E)-*
(A+B)C(D/E)-*
(A+B)(C-(D/E))*
(A+B)(C-(D/E))*
(A+B)*(C-(D/E))
こんな感じに変形すれば解けます。
突然なんでこんな話をしたのかと言えばその昔この記法呪文だとか思っていたんですけど、Lispいじるようになってからはこういった問題文見た瞬間解けるようになってしまってビビったので紹介しようと思ったのでした。だからみんなもLispをやろう*1。