逆ポーランド記法の解き方

効率的なプログラムを書きたい＆コンピュータサイエンスを学びたいなと思い、

「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」という本を使っています。

その中で出てきた、逆ポーランド記法というものについて、普通の数式から逆ポーランド記法化、

逆ポーランド記法化されたものの、普通の数式化をする方法についてまとめています。

基本情報技術者試験にも出てくる、基本的なもののようです。

結論

普通の数式（中置記法ともいう）→逆ポーランド記法

の時は、計算の順番に、演算子を後ろへ移動させる。

逆ポーランド記法→普通の数式

の時は、数式にスペースを入れてみて、演算子が出てきたら1番近いスペースへ演算子を代入する。

と解けます

そもそも逆ポーランド記法とは？

今まで日常で使ってきた数式の記述方法は、中置記法と言います。

「１＋２」のように、数字（被演算子）に対して演算子（＋）が中間に置いてあります。

（私これに名前があるなんて知らなかったです。。。）

そして、逆ポーランド記法というものは、「１ ２ ＋」のように、演算子が、被演算子の後ろにあります。

逆というからには、ポーランド記法（前置記法）というのもあって、これは「＋ １ ２」というふうに、

演算子が前に置かれます。

…逆ポーランド記法の何が良いかというと、（）を使わないで記述できたり、計算効率があがるようです。

この、（）を使わないで記述できる、というのは、逆ポーランド記法から普通の数式に戻すときに気をつけないといけないところです。

普通の数式→逆ポーランド記法の方法

動画の方が分かりやすいかと思い、動画にしてみました（字が汚ないというのはすみません）。

通常に計算する順序で、演算子を被演算子の後ろに持ってきます。

そして最後に（）をなくせば完成です。

逆ポーランド記法→普通の数式の方法

こちらも、動画でまとめてみました。

説明を手書きではなくしたので、少しは読みやすいですかね。。

数にまずは、スペース（空白）をいれて記述してから、そのスペースに演算子を代入していく感じです。

まとめ

普通の数式（中置記法ともいう）→逆ポーランド記法

の時は、計算の順番に、演算子を後ろへ移動させる。

逆ポーランド記法→普通の数式

の時は、数式にスペースを入れてみて、演算子が出てきたら1番近いスペースへ演算子を代入する。

そもそも、数式の記述方法に名前がついていること、記述方法がたくさんあること、を学びました。