スタックの操作と逆ポーランド記法による数式処理

コンピュータで数式を処理する時、良く「逆ポーランド記法」という表記とアルゴリズムが使われます。逆ポーランド記法とは、演算子（+-*/など）を被演算子（数値や変数）の後ろに書くことで数式を表現する記法で、「1+2」という式を逆ポーランド記法で書くと、「12+」となるわけです。ちょうど「１と２を足す」という日本語の表現と同じですね。また、この記法は結果的に数学的な演算を具体的な「操作」として順番に書き下した、という面もあるので、逆ポーランド記法の数式は計算アルゴリズムを単純化しやすく計算処理のプログラミング時に非常に扱いやすくなります。
最も、コンピュータにとっては理解しやすくても、人間にとっては慣れないとややわかりにくい、という面もあるのですが。

さらに、逆ポーランド記法だとカッコをなくす事ができます。例えば「(1+2)*3」という式は「12+3*」と表現でき実際に計算する時は、まず最初の12+を計算して次にその結果3を当てはめ33*とすれば計算できるため、カッコを使う必要がありません（ちなみに、これは「１と２を足してそれに３をかける」と言っている事になります）。カッコがない事も、計算処理を簡略化できる大きな（あるいは最大の）要素です。
逆に言えば、カッコを使った複雑な数式も、逆ポーランド記法で表現してしまえば、簡単なアルゴリズムで計算できる事になりますね。「((1+2)*3+4)*5」という式を、そのままプログラムで計算するのは大変ですが、「12+3*4+5*」と逆ポーランド記法に書き換えれば今回のプログラムで計算できます。式を逆ポーランド記法に書き換えるルゴリズムも、そのうち考える事にしましょう。

プログラムソース表示

操作方法

左のテキストフィールドに逆ポーランド記法の式を入力して、Goボタンをクリックしてください。右のテキストフィールドに結果が表示されます。ただし、数値は一桁で演算子は+-*/ のみを使用してください。

スタック

逆ポーランド記法の計算アルゴリズムは、スタックを使うものが一般的です。スタックとは、ＬＩＦＯ（後入れ先出し）式のデータ形式で、データは最初から積み重ねられていき、取り出す時は一番最後に入れられたデータから順に取り出されるようになっています。スタックにデータを入れる事をpush、データを取り出す事をpopと呼び現在どれだけデータが積まれているかを表す変数は、スタックポインタと呼ばれます。
スタックは、配列を使えば簡単に実現できます。まず、適当な大きさの配列st[]とスタックポインタspを定義しておいてspを0 にします。データがpushされたら配列のst[sp]にデータを入れてspを1 増やす。データがpopされたらspを１減らした後のst[sp]のデータを使う。関数で書けば、

  void push(int w) {

      st[sp++]=w;

  }

  int pop() {

      return st[--sp];

  }

という感じになります。

逆ポーランド記法の計算アルゴリズム

さて、逆ポーランド法の計算は上で見たように「数式を前からひたすら計算していく」だけです。計算したら、その結果を数値として次の計算に使います。スタックが有効なのも、計算結果を次々にスタックに積んでおけば、そのまま取り出すだけで直前の計算結果が得られるからです。

以上の事から、式を文字列の形で与え数値を一桁（０ー９）、演算子を+-*/のみとすれば、

1. 文字列から１字取り出してそれが数値ならスタックに積む。
2. 演算子なら、スッタクから２つ値をpop して演算する。
3. １，２を文字列の終わりまで繰り返せば、スタックに残った値が答え。

というアルゴリズムが得られます。関数で書くと、

  private int res(String st) { /* 逆ポーランド記法の式を計算 */

      int a,b,i,w;
      String s;

      sp=0; /* スタックポインタ初期化 */

      for (i=0;i<st.length();i++) { /* １文字目から最後まで */

          switch (st.charAt(i)) { /* １字づつ取り出す */

              case '+':
                  a=pop();
                  b=pop();
                  push(b+a);
                  break;

              case '-':
                  a=pop();
                  b=pop();
                  push(b-a);
                  break;

              case '*':
                  a=pop();
                  b=pop();
                  push(b*a);
                  break;

              case '/':
                  a=pop();
                  b=pop();

                  if (a==0)
                      break;

                  push(b/a);
                  break;

              default: /* 演算子でなければ数値として処理 */

                  s=st.substring(i,i+1);
                  w=Integer.parseInt(s); /* 数値に変換 */
                  push(w); /* スタックに積む */

          }

      }

      return pop(); /* 結果を返す */

  }

という感じでしょうか。substring(a,b)は文字列のa文字目からb文字目の前までを取り出す関数で、substring(a,a+1)とするとa文字目の文字をString型で取り出す事ができます。スタックでは後の方に入れたデータから先に取り出されるため、計算する時の順序が逆になる点にも注意してください。