アルゴリズムの演習問題をやっていたら「逆ポーランド記法」という初めて聞く言葉が出てきたので、まとめました。
そもそも逆ポーランド記法とは？
- 演算子を被演算子の後にする。（後置記法とも言う。（？））
- その他の記法としては、演算子を被演算子の中間に記述する中間記法、前に記述する前置記法（ポーランド記法）がある。
例えば、
3 + 4
これは中間に「＋」を置いているから、中間記法、というわけですね。
逆ポーランド記法は後ろに演算子を置くので、
3 4 +
と書きます。（34+〇〇に見えるから慣れないとややこしい、、、）
どういうシーンで「逆ポーランド記法」が出てくる？
一言で言うと、電卓を実装する場合は、逆ポーランド記法を使って演算するようです。
逆ポーランド記法はコンピュータ処理に適した記法らしいです。
実現方法は、「スタック」と呼ばれるデータ構造を使用します。
手順は以下です。
① 式からトークンを１つ取り出してtとする
② もし、tが数値であれば、スタックに積む
③ もし、tが演算子であれば、スタックから3つ値を下ろし、計算を行って、スタックに乗せる
④ 式が空になるまで上記手順を繰り返す
⑤ スタックから値を１つおろし、それを式の答えとする
おまけ：スタックとは
スタックは、後に入れたものが先に出る構造をしていて、キューの逆です。
説明は下記サイトに任せます。
「スタックとは｜「分かりそう」で「分からない」でも「分かった」気になれるIT用語辞典」
https://wa3.i-3-i.info/word14717.html