こんばんは。きわさです。
プログラムで演算を扱う際に役に立ちそうなのでメモ
逆ポーランド記法
数式の記法の一つで、演算子を被演算子の後に書くものです。
例えば、2+5であれば、
2 5 +
となります。
少し複雑にして、(4 + 2) * (5 – 1)であれば、
4 2 + 5 1 – *
となります。
逆ポーランド記法の数式の計算
プログラムの演算で役に立ちそうとはどういうことかというと、
計算する際、式を順番に読んでいき、被演算子であればスタックに積み、演算子であればスタックから被演算子を取り出し演算してスタックに積むという処理の繰り返しだからです。
4 2 + 5 1 – *で見てみます。
手順としては、
1. まず 4 は被演算子のため、スタックに積みます。
スタック: 4
2. 次に 2 も被演算子のため、スタックに積みます。
スタック: 4, 2
3. そして + は演算子なのでスタックから 2 を取り出します。
スタック: 4
4. 取り出した 2 をスタックトップの 4 に + します。
4 + 2 の演算結果の 6 がスタックに積まれます。
スタック: 6
5. 続いて、5 と 1 は被演算子なのでスタックに積みます。
スタック: 6, 5, 1
6. 次の – は演算子なのでスタックから 1 を取り出し、5 から – します。
スタック: 6, 4
7. 最後に * で、4 を取り出し、6 に * で 24 となります。
電卓アプリなどで入力した式を計算したいときに使えそうです。
ただ、その場合は入力された式を逆ポーランド記法に変換する必要もありますが。。
数式を逆ポーランド記法に変換
次は数式を逆ポーランド記法に変換する方法です。
2 + 5 が 2 5 + になることは上述の通りですが、具体的な方法についてです。
今回は演算子であればスタックに積んでいきます。優先度の高い演算子はスタックに積み、スタックの演算子以下の優先度の場合は書き出します。
1 + 2 * 3 – 4でやってみます。
手順は、
1. まず 1 は被演算子なので書き出します。
変換後: 1
スタック:
2. 次の + は演算子なのでスタックに積みます。
変換後: 1
スタック: +
3. そして 2 は被演算子なので書き出します。
変換後: 1 2
スタック: +
4. 次の * はスタックの + より優先度が高いのでスタックに積みます。
変換後: 1 2
スタック: +, *
5. 被演算子の 3 は書き出します。
変換後: 1 2 3
スタック: +, *
6. そして演算子 – はスタックの * の優先度以下なので、ここで * を書き出します。
変換後: 1 2 3 *
スタック: +
7. さらに、スタックの + の優先度以下(+と-は同じ優先度)なので、+ も書き出します。
変換後: 1 2 3 * +
スタック:
8. そしてやっと – をスタックに積むことができます。
変換後: 1 2 3 * +
スタック: –
9. 次の被演算子の 4 を書き出します。
変換後: 1 2 3 * + 4
スタック: –
10. 最後はスタックの被演算子を書き出します。
変換後: 1 2 3 * + 4 –
スタック:
これで完了です。
1 + 2 * 3 – 4 は逆ポーランド記法では、
1 2 3 * + 4 –
となります。