Aritalab:Lecture/Algorithm/PolishNotation

ポーランド人論理学者ウカシェヴィチが考案したポーランド記法はLISPにおける演算の記述法に同じで、演算子を前置きします。ここでは逆ポーランド記法と呼ばれる、演算子を後置きする記述法を、サンプルプログラムを見ながら考えます。

演算子を後置する逆ポーランド記法

逆ポーランド記法とは、たとえば

2 3 +

2 log

のような、演算子を後置する書き方です。若い人には信じられないでしょうが、昔は逆ポーランド記法で数式を入力する電卓が存在しました。

なぜかというと、スタックを利用して簡単に演算処理をおこなえるからです。まず、入力文字列から数値を順番に切り出し（トークン token と呼びます）、スタックに積んでいきます。もし演算子トークンがきたら、スタックから演算を施す数値（オペランド operand と呼びます）を取り出して演算結果を再びスタックに積みます。長い数式の場合でも、できるところから順に計算を開始するため利用するメモリ量が少ないというメリットもあります。

　足し算しか許さない逆ポーランド記号計算機の処理

public double parseRPN(StringTokenizer st)
    throws Exception
{
　　Stack<String> tokenStack = new Stack<String>();
 　while (st.hasMoreTokens())
 　　 {
      String nextToken = st.nextToken();
　　　　　if (nextToken.equals("+"))
　　　　　　　{
　　　　　　　　　if (tokenStack.size() < 2)
 　　　　　　　　　 throw new Exception("オペランドが足りません");
          //必要数だけオペランドをpopします。
　　　　　　　　　double d1 = Double.parseDouble(tokenStack.pop());
　　　　　　　　　double d2 = Double.parseDouble(tokenStack.pop());
          //計算結果を積みます。
　　　　　　　　　tokenStack.push("" + (d2 + d1));
　　　　　　　}
      else 
        tokenStack.push(nextToken);
    }
  if (tokenStack.size() != 1)
    throw new Exception("オペレータが足りません");
  return Double.parseDouble(tokenStack.pop());
}

入力文字列が終わりにきたとき、最後の演算子を用いてスタックの中身を処理すると、スタックに は一つだけ数値が残されているはずです。これが計算の最終結果になります。

演算子を中置する通常の電卓

普通の数式を処理するには、演算子の優先度を考慮しなくてはなりません。 たとえば

2 + 3 * 5

と書かれたら、掛け算を先に処理して結果が30になります。

2 + log 3 * 5

と書かれたら、log を計算してから掛け算、足し算の順番になります。この式が左から順番 に読み込まれたと仮定しましょう。スタックには、

2, +, log, 3

が積まれます。次に * を読み込んだ時点で 3, log と pop し、 log 3 = 1.09 を push します。その後、入力トークンがないので掛け算を実施、最後に足し算を行います。演算子の優先度は、

log などの単項演算子 > 乗除算 > 加減算

です。この優先度を調べるため、関数 getPriority を用意します。

static final int NUMBER = 0;
int getPriority(String op)
{
  final String[] functions = { "+", "-", "/", "*", "log", "sqrt" };
  final int[] priority = { 1, 1, 2, 2, 3, 3 };
  for (int i = 0; i < functions.length; i++)
    if (op.equals(functions[i]))
      return priority[i];
  return NUMBER;
}

優先度は、「読み込んだ時にすぐにスタックからpopするかどうかを判断する値」です。数字の優先度は0と考えます。 常に、次の入力トークンの優先度とスタックのてっぺんにある式の優先度を比較し、スタック上のほうが高いうちはスタック上の数式を処理する部分です。

　通常の四則計算機の処理

int stackTopPrio =0;
while (st.hasMoreTokens())
  {
    //次のトークンを「先読み」します。
    String token = st.nextToken();
    nextPrio = getPriority(token);
    //tokenを積む前に処理すべき数式を実行。
    if ((nextPrio != NUMBER) && (nextPrio <= stackTopPrio))
      reduce(nextPrio, stackTopPrio, tokenStack);
    //ここでトークンを積みます。上の逆ポーランド記号計算機と比較してください。
    tokenStack.push(token);
    if (nextPrio != NUMBER)
      stackTopPrio = nextPrio;
   }
  }

スタックのてっぺんにある演算子の優先度がstackTopPrioで、次にくる演算子の優先度がnextPrioです。 関数reduceは、第三引数としてとるスタック上の数式を、nextPrio <= stackTopPrio が成立する間だけ処理する関数です。 コードは少し長くなるので、サンプルプログラムのページを見てください。

括弧つきの数式

1 / (2 + 3) * 5

と書かれたら、括弧の中身を先に計算せねばなりません。また括弧は入れ子状に書けます。 括弧つきの数式を処理するには、スタックに積んである情報をいったん退避させ、新しい数式が始まると考えなくてはいけません。例えば以下の式を考えてみましょう。

2 + log ( ( 2 + 3 ) * 5 + 2 ) + 1

括弧の外側にある log は、括弧の中身が全て計算された後に適用します。 プログラム中では、左括弧をみつけたらトークンを読み込む関数を再帰呼び出しし、右括弧が数式の最後であるかのように処理します。 最終プログラムは、上のコードに括弧の処理を付け足すだけで済みます。