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



 逆ポーランド記法で計算するようにするとコンピュータで処理しやすいということは分かりました。
 では、どうやって普通の計算式を逆ポーランド記法に直せばいいのでしょうか? これはすでにアルゴリズムがあります。ちょっとしたアルゴリズムの本やコンパイラ関係の本を見たりすれば大体載っていると思います。
 
 ではそのアルゴリズムを簡単に説明してみます。
 
 まず例に出した3つの式をみてみましょう
 
    5 + 4 - 3       ;通常
    5 4 3 - +       ;逆ポーランド記法
 
    5 + 4 * 3 + 2 / 6   ;通常
    5 4 3 * 2 6 / + +   ;逆ポーランド記法
 
    (1 + 4) * (3 + 7) / 5 ;通常
   1 4 + 3 7 + 5 * /    ;逆ポーランド記法

 この3つの式を見てみるとあることに気がつきませんか? なんと数字の並んでいる順番は同じです。違うのは演算子の位置と順番です。ということは演算子をどうにかすればいいという気がします。
 
 最初の式(5 + 4 - 3)を例に取って考えてみます。
 
 まずは 5 を持ってきます。数字の並び順は変わらないのでそのまま手元に並べます。
 次は + です。が、+ は数字が2つ無いとどうにもならないので脇においておきます。
 その次は 4。数字なので 5 の次に並べます。
 その次は −。手元を見ると数字が2つあります。これで計算できそうですが、この後に演算の優先度の高い ×÷ が来るかもしれません(算数の基本、+− よりも ×÷ を先に計算するというやつです)
 その次は 3。数字なのでそのまま並べます。
 もう持ってくるものはありません。脇に + と − が余っているのでそれを並べます。順番は最後に入れた物から並べます。並んでいる数字は最後に入れたものが手前にありますからね。
 するといつの間にか手元には 5 4 3 - + という並びが出来ています。
 
 5 + 4 * 3 + 2 / 6
 
 これではどうでしょうか。同じように進めると、最初に5を手元並べて、次に脇に + を置きます。次に4を並べてその次に × が来ます。
 ここでちょっと考えましょう。
 +よりも×の方が優先度が高いので並べたくなりますが、本当に並べていいでしょうか? もしかすると×よりも優先度の高いものがあるかもしれません。なのでちょっと我慢して次の数字に行きます。
 数字の3が来て+が来ます。このとき、脇にある演算子は +×+という順番になります。+は×よりも優先度が低いので×を数字の後に並べます。
 では変換の様子を簡単に表してみましょう
 
 手元               5 + 4 * 3 + 2 / 6
 脇                                  ;スタート
 
 手元 5             + 4 * 3 + 2 / 6
 脇                                  ;まずは数字5
 
 手元 5             4 * 3 + 2 / 6
 脇  +                               ;+演算子
 
 手元 5 4           * 3 + 2 / 6
 脇  +                               ;数字4
 
 手元 5 4           3 + 2 / 6
 脇  + *                             ;×演算子。+より優先度が高いのでそのまま。
 
 手元 5 4 3         + 2 / 6
 脇  + *                             ;数字3
 
 手元 5 4 3         2 / 6
 脇  + * +                           ;×より+の方が優先度が低い。
 
 手元 5 4 3 *       2 / 6
 脇  + +                             ;×を脇から手元へ
 
 手元 5 4 3 * 2     / 6
 脇  + +                             ;
 
 手元 5 4 3 * 2     6
 脇  + + /                           ;
 
 手元 5 4 3 * 2 6
 脇  + + /                           ;もう式から持ってくるものは無い
 
 手元 5 4 3 * 2 6 /
 脇  + +                             ;脇に残った演算子を移動
 
 手元 5 4 3 * 2 6 / +
 脇  +                               ;
 
 手元 5 4 3 * 2 6 / + +
 脇                                  ;終了
 

 あと残るは  (1 + 4) * (3 + 7) / 5 ですが、これはちょっと厄介です。カッコがあります。
 カッコは演算子では無いので、どうしたらいいのでしょうか?
矢印前ページ トップ
次ページ矢印