逆ポーランド記法

逆ポーランド記法は優先順位を考慮した数式の計算を行うのに適した方法です。
逆ポーランドを使う場合、普通の数式を逆ポーランドに変換する過程と、それを使って計算する過程に分かれます。

普通の数式と逆ポーランド記法の具体例

普通の数式	逆ポーランド記法
9+8-3*4	98+34*-
a+b*c-d	abc*+d-
a-b*c+e/d	abc*-ed/+

逆ポーランド記法の計算

最初に逆ポーランド記法の計算が便利なことを実感していただきましょう。

普通の数式	逆ポーランド記法
9+8-3*4=5	98+34*-

スタック、演算、ソース領域を使って説明します。

スタック演算ソース 98+34*-
先頭から順に取り出してスタックに PUSH します。

8,9 　　 +34*-
演算記号(+)が現れたらスタックから二個のデータを取り出して演算記号に従い計算をしてその結果を再びスタックに PUSH します。

17 9+8=17 34*-
次のデータをスタックに PUSH します。

4,3,17 　　 *-
演算記号(*)が現れたらスタックから二個のデータを取り出して演算記号に従い計算をしてその結果を再びスタックに PUSH します。

12,17 3*4=12 -
演算記号(-)が現れたらスタックから二個のデータを取り出して演算記号に従い計算をしてその結果を再びスタックに PUSH します。

5 17-12=5 　　
全ての処理が終わったとき、スタックに残っているのが計算結果です。

逆ポーランド記法への変換

それでは次に、普通の数式を逆ポーランドに変換する方法を説明します。

普通の数式	逆ポーランド記法
9+8-3*4=5	98+34*-

出力、スタック、入力領域を使って説明します。
演算記号の優先順位に従って重みをつけます。
例えば「+ と -」は１で、「* と /」は２とします。
かっこの中は優先順位が上がるので、同じ演算記号でも重みを増します。
例えば一重の括弧の中は +10 を、二重括弧の中は +20 を加えます。
スタック領域と入力の最後には一番優先順位の低い値(\0)を設定しておきます。

出力スタック \0 入力 9+8-3*4\0
入力のデータと演算記号を順番に取り出します。データはそのまま出力します。

9 \0 +8-3*4\0
演算記号(+)がくると、スタックの値と比較してスタックの方が優先順位が低いときはその上に PUSH します。

9 \0,+ 8-3*4\0
データ(8)はそのまま出力します。

9,8 \0,+ -3*4\0
演算記号(-)がくると、スタックの値と比較してスタックの方が優先順位が高いか等しい演算記号を全て POP して出力します。
そしてそのあとに(-)を PUSH します。

9,8,+ \0,- 3*4\0
データ(3)はそのまま出力します。

9,8,+,3 \0,- *4\0
演算記号(*)は(-)より優先順位が高いのでその上に PUSH します。

9,8,+,3 \0,-,* 4\0
データ(4)はそのまま出力します。

9,8,+,3,4 \0,-,* \0
入力の最後には最も優先順位が低い値を設定しておいて、スタックに残っている全ての記号を POP して出力します。

9,8,+,3,4,*,- \0 \0

プログラミング・アドバイス

最初は逆ポーランド記法で書かれた形式を入力して計算結果を表示するプログラムから作成するのが良いでしょう。
次に一般的な計算式をタイプ入力して、逆ポーランドに変換して計算します。

逆ポーランドに変換するとき、演算記号と重みを格納するスタックは構造体もしくは独立した配列で定義します。

      char    opr[100];        //+-*/ など演算記号を PUSH します
      int     wait[100];       //opr と対で演算記号の重みを PUSH します

      typedef struct
      {   char    opr;
          int     wait;
      } CELL;
      CELL    stack[100];

超初心者のプログラム入門(C/C++)