逆ポーランド記法
こんにちは。これまでデータ構造について書いてきたので、その中のスタックを使ったプログラムとして、「逆ポーランド記法」について書きたいと思います。
逆ポーランド記法とは
普段、私たちは計算式を書くときに、加減乗除の記号（演算子）（＋・－・×・÷）を計算する値と値の間に書いています。このような書き方を中置記法といいます。演算子を前に書く記法を前置記法（ポーランド記法）、演算子を後ろに書く記法を後置記法（逆ポーランド記法）といいます。
中置記法の問題点
小学校以来、乗法と除法（×と÷）は加法と減法（＋と－）よりも優先して計算すると習い、それに基づいて計算しています。例えば\(1+2\times3\)の場合\(2\times3\)を先に計算して、その結果の\(6\)を用いて、\(1+6\)を計算します。しかし、次の計算の場合には単純には書けません。\(1\)と\(2\)を先に足しておき、\(3\)と\(4\)も足しておいて、その結果どうしを足す\(3+7\)を1つの式で書くには、\((1+2)\times(3+4)\)と括弧を使わなければ表記できません。ここで括弧がない\(1+2\times3+4\)としてしまうと、最初に計算するのは\(2\times3\)になってしまいます。
同じ式を逆ポーランド記法で表現すると
逆ポーランド記法では、演算子を計算する２つの値の後ろに書きます。簡単な場合では、中置記法の\(2\times3\)の場合、\(2 3 \times\)となります。先ほどの\((1+2)\times(3+4)\)を逆ポーランド記法で書くには、\(1 2 + 3 4 + \times\)となり、括弧を用いなくても表現することができます。ちなみに前置記法は、演算子を前に置く記法です。\((1+2)\times(3+4)\)を前置記法で書くと、\(\times + 1 2 + 3 4 +\)となります。
逆ポーランド記法のメリット
数式を3つの方法で表記することができることが、ここまででわかりました。その中で逆ポーランド記法が多く扱われるのは、スタックを用いると簡単なアルゴリズムで計算できることが知られているからです。そのアルゴリズムは、\[\begin{cases} ２つの数値をｐｏｐして計算し、結果をスタックに積む & (演算子の場合 ) \\ スタックに積む & (数値の場合) \end{cases}\]
となり、単純なアルゴリズムで計算することができます。
スタックを使った計算
それでは上のアルゴリズムを実装してみましょう。
package data_structure;
import java.util.Scanner;
public class ReversePolishNotation {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
MyStack<Integer> stack = new MyStack();
String fomula = scan.nextLine();
String[] operand = fomula.split(" ");
for (int i = 0; i < operand.length; i++) {
switch (operand[i]) {
case "+":
case "-":
case "*":
case "/":
int a = stack.pop();
int b = stack.pop();
int result = 5;
if (operand[i].equals("+")) {
result = a + b;
} else if (operand[i].equals("-")) {
result = a - b;
} else if (operand[i].equals("*")) {
result = a * b;
} else if (operand[i].equals("/")) {
result = a / b;
}
stack.push(result);
break;
default:
stack.push(Integer.parseInt(operand[i]));
}
}
System.out.println(stack.peek());
}
}
実行結果は次のようになります。
1 2 + 3 4 + *
21
今回はこれまで。それではまた。