2013-07-02T23:22:22の更新内容

programming/tips/polish/index.wiki.txt

current previous
1,16 1,16
~
${smdncms:title,二分木を使った数式の逆ポーランド記法化と計算}
${smdncms:title,二分木を使った数式のポーランド記法・逆ポーランド記法化}
 
${smdncms:keywords,ポーランド記法,逆ポーランド記法,前置記法,後置記法,中置記法,二分木}
${smdncms:keywords,ポーランド記法,逆ポーランド記法,前置記法,後置記法,中置記法,二分木}
 
${smdncms:tags,lang/c,lang/c#,lang/vb,lang/ruby,lang/java,algo}
${smdncms:tags,lang/c,lang/c#,lang/vb,lang/ruby,lang/java,algo}
 
${smdncms:meta,toc-amazonlivelink-keyword,books-jp,アルゴリズム}
${smdncms:meta,toc-amazonlivelink-keyword,books-jp,アルゴリズム}
 

        

        
 
*逆ポーランド記法とは
*逆ポーランド記法とは
~
一般に人が読むことを前提にした数式は「x = 3 * 2 + 1」の様な形式で表記されますが、演算の順序などを考えるとコンピュータにとってはこの表記は扱いにくいものです。 コンピュータとしてはこの式は「x32*1+=」と表記されていたほうが扱いやすくなります。 このような形式での表記が逆ポーランド記法です。
一般に人が読むことを前提にした数式は「x = 3 * 2 + 1」の様な形式で表記されるわけですが、コンピュータにとってはこの表記が意外にわかりにくいのです。 コンピュータとしてはこの式を「x32*1+=」と表記してくれるとありがたいのです。
 

        

        
~
逆ポーランド記法で記述された数式「x32*1+=」は、「xは3と2を掛けたものに1を足して代入したもの」と読むことができます。 より機械的な表現では「xは3と2を*したものに1を+して=したもの」と読むこともできます。 つまり、この表記においては、演算対象と演算処理が処理順に記述されることになります。 プログラミングなどでは「x = 3 * 2 + 1;」といった式を書きますが、実は実行時にはスタックというものを使って逆ポーランド記法的に計算しています。
例えばこの数式を口に出して読んでみると、「xは3と2を掛けたものに1を足して代入したもの」と言うようになります。 さらに「xは3と2を*したものに1を+して=したもの」と言い換えればわかりやすいかもしれないですね。 プログラミングなどで「x = 3 * 2 + 1;」なんて式を書くと思いますが、実は実行時にはスタックというものを使って逆ポーランド記法的に計算しているわけです。
 

        

        
 
このように、項の後ろに演算子記号を記述する方式を''逆ポーランド記法(後置記法)''と言います。 対して、最初に挙げた馴染み深い記法、つまり項の間に演算子を記述する方式を''中置記法''、項の前に演算子が来る記法を''ポーランド記法(前置記法)''と言います。
このように、項の後ろに演算子記号を記述する方式を''逆ポーランド記法(後置記法)''と言います。 対して、最初に挙げた馴染み深い記法、つまり項の間に演算子を記述する方式を''中置記法''、項の前に演算子が来る記法を''ポーランド記法(前置記法)''と言います。
 

        

        
~
**ポーランド記法化・逆ポーランド記法化と数式計算のデモ [#ConversionDemo]
**ポーランド記法化・逆ポーランド記法化のデモ [#ConversionDemo]
 
記法を変換するアルゴリズムの解説に入る前に、実際にどのようになるのか見たほうが分かりやすいと思います。 これはこの文書で紹介するアルゴリズムを実装したポーランド記法化・逆ポーランド記法化のデモです。 変換したい数式を入力して、[変換]のボタンを押してください。 (Javascriptを有効にしないと動作しません)
記法を変換するアルゴリズムの解説に入る前に、実際にどのようになるのか見たほうが分かりやすいと思います。 これはこの文書で紹介するアルゴリズムを実装したポーランド記法化・逆ポーランド記法化のデモです。 変換したい数式を入力して、[変換]のボタンを押してください。 (Javascriptを有効にしないと動作しません)
 

        

        
 
#html{{
#html{{
23,14 23,6
 
        <input type="text" id="polish_demo_input" value="" size="25" />
        <input type="text" id="polish_demo_input" value="" size="25" />
 
        <input type="button" value="変換" onclick="polish_demo_convert();"/>
        <input type="button" value="変換" onclick="polish_demo_convert();"/>
 
        <input type="reset" value="クリア"/>
        <input type="reset" value="クリア"/>
+
        <div>
+
        記入例
+
        <ul>
+
          <li><code>x = a * (b + c)</code></li>
+
          <li><code>2+5*3-4</code></li>
+
          <li><code>1+4*2+(7-3)/2</code></li>
+
        </ul>
+
        </div>
 
      </td>
      </td>
 
    </tr>
    </tr>
 
    <tr>
    <tr>
51,12 43,6
 
        <input type="text" id="polish_demo_result_inorder" size="40" />
        <input type="text" id="polish_demo_result_inorder" size="40" />
 
      </td>
      </td>
 
    </tr>
    </tr>
+
    <tr>
+
      <th>数式の計算結果</th>
+
      <td>
+
        <input type="text" id="polish_demo_result_calculate" size="40" />
+
      </td>
+
    </tr>
 
  </table>
  </table>
 
</form>
</form>
 
}}
}}
193,25 179,6
 

        

        
 
    return ret;
    return ret;
 
  };
  };
+

          
+
  this.calculate = function()
+
  {
+
    if (this.left && this.right) {
+
      var left_operand  = this.left.calculate();
+
      var right_operand = this.right.calculate();
+

          
+
      switch (this.expression) {
+
        case "+": return left_operand + right_operand;
+
        case "-": return left_operand - right_operand;
+
        case "*": return left_operand * right_operand;
+
        case "/": return left_operand / right_operand;
+
        default:  return 0.0;
+
      }
+
    }
+
    else {
+
      return parseFloat(this.expression);
+
    }
+
  };
 
}
}
 

        

        
 
function polish_demo_convert()
function polish_demo_convert()
225,7 192,6
 
    $('#polish_demo_result_postorder').val(root.traversePostorder());
    $('#polish_demo_result_postorder').val(root.traversePostorder());
 
    $('#polish_demo_result_inorder').val(root.traverseInorder());
    $('#polish_demo_result_inorder').val(root.traverseInorder());
 
    $('#polish_demo_result_preorder').val(root.traversePreorder());
    $('#polish_demo_result_preorder').val(root.traversePreorder());
+
    $('#polish_demo_result_calculate').val(root.calculate());
 
  }
  }
 
  catch (e) {
  catch (e) {
 
    alert(e);
    alert(e);
244,15 210,15
 

        

        
 

        

        
 
*二分木を使った逆ポーランド記法化のアルゴリズム
*二分木を使った逆ポーランド記法化のアルゴリズム
~
逆ポーランド記法化を行うアルゴリズムには様々なものがあり、一例としてスタックを使うものがありますが、ここではスタックではなく二分木を使って数式を逆ポーランド記法に変換する方法について解説します。 また、二分木に変換した数式を使って数式の計算を行う方法についても解説します。
逆ポーランド記法化を行うアルゴリズムには様々なものがあり、一例としてスタックを使うものがありますが、ここではスタックではなく二分木を使って数式を逆ポーランド記法に変換してみようと思います。
+

          
 

        

        
-
なお、数式の逆ポーランド記法化からさらに進んで数式の計算も行わせることが出来るようになりますが、ここでは逆ポーランド記法化までを扱い、数式の計算については扱いません。
 

        

        
 
**二分木とは
**二分木とは
~
二分木とは節から二本に枝分かれした木のようなデータ構造です。 この木構造は二分探索などのアルゴリズムでよく用いられるデータ構造です。 二分木の構造として、まず''根(root)''があり、そこから二本に枝分かれします。 枝分かれする元を''節(node)''、枝分かれした先を''葉(leaf)''といいます。 根や葉を区別せずに全てまとめてノードと呼ぶこともあります。 また、ある節から見た根本の節を''親(parent)''といい、節から見た''枝(branch)''の先を''子(child)''、同じ親をもつ子同士を''兄弟(sibling)''といい、親ノード・子ノードなどと呼びます。 さらに、ある節を根とみなし、それ以下の構造を''部分木(subtree)''とも言います。 二分岐の一例と構造上の名称を図にすると次のようになります。
二分木とは節から二本に枝分かれした木のようなデータ構造です。 この木構造は二分探索などのアルゴリズムでよく用いられるデータ構造です。 二分木の構造として、まず''根(root)''があり、そこから二本に枝分かれします。 枝分かれする元を''節(node)''、枝分かれした先を''葉(leaf)''といいます。 また、葉から見た根本の節を''親(parent)''といい、節から見た''枝(branch)''の先を''子(child)''、同じレベルにある子同士を''兄弟(sibling)''といいます。 さらに、ある節を根としてそれ以下の構造を''部分木(subtree)''とも言います。 図にすると次のような感じです。
 
#image(0.png,nopopup,二分木)
#image(0.png,nopopup,二分木)
 

        

        
~
実際にプログラミングによって二分木を再現する場合は、次のような構造体を用いることが多いです。 この例では各々のノードが持ちうる値はint型であるとしています。
実際にプログラミングによって木構造を再現する場合は、次のような構造体を用いることが多いです。 この例では各々の節が持ちうる値はint型であるとしています。
 
#code(c) {{
#code(c) {{
 
struct Node
struct Node
 
{
{
262,105 228,64
 
};
};
 
}}
}}
 

        

        
~
つまり、右と左の子ノードへのポインタと、そのノード自体が持つデータを構造体のメンバとして持つわけです。 子を持たないノード、つまり葉のノードを表すには右と左の子ノードとしてヌル参照を設定します。
つまり、右と左の節へのポインタと、その節自体が持つデータを構造体のメンバとして持つわけです。 もちろんのことですが、葉も節として扱います。
+

          
 

        

        
-
**数式を木構造に変換する
-
さて、ここからが本題なのですが、変換する式として「X=A*B+C」を例にとって考えてみたいと思います。 参考までに、この式を逆ポーランド記法にすると「XAB*C+=」になります。 まずはじめに、式を木構造に変換する方法を定義します。
 

        

        
~
**数式を二分木に変換する
:定義1|演算子は2つの部分式(項)を必要とする。 これを木構造で表す場合、演算子の左側の部分式を左の葉、演算子の右側の部分式を右の葉、演算子自体を節に持つこととする。
+
数式を逆ポーランド記法化する前の下準備としてに、式を二分木に変換します。 なぜ二分木にする必要があるのかという点については後述するとして、まずは変換する式として「X=A*B+C」を例にとって二分木に変換する方法を考えてみたいと思います。 まずはじめに、式を二分木に変換する方法を次のように定義します。
 

        

        
~
:ルール1|演算子は2つの部分式(項)を必要とする。 これを二分木で表す場合、演算子の左側の部分式を左の子ノード、演算子の右側の部分式を右の子ノード、演算子自体をノード自身に持つこととする。
つまり、式A+Bは次のような木構造になるとします。
-
#image(1.png,nopopup,A+Bの木構造)
 

        

        
~
つまり、式「A+B」は次のような二分木になるものとします。
さらに、式X=A+Bについて考えてみると、演算子=の左の部分式をX、右の部分式をA+Bと考えることができるので、このような木構造になるとします。
~
#image(1.png,nopopup,A+Bの二分木)
#image(2.png,nopopup,X=A+Bの木構造)
 

        

        
~
さらに、式「X=A+B」について考えてみると、演算子=の左の部分式をX、右の部分式をA+Bと考えることができるので、このような二分木になるものとします。
しかし、ここで演算子+を中心として部分式X=Aと部分式Bに分けてしまうこともできます。 このままではどこで分けるかあいまいなので、次の定義を加えます。
~
#image(2.png,nopopup,X=A+Bの二分木)
:定義2|式を木構造で表す場合、最も低い優先順位の演算子を選び出して、その演算子を中心に部分式に分けることとする。
~

          
:定義3|分けた後の部分式に演算子が含まれる場合は、さらにその節について分割を続ける。
+
しかし、式「X=A+B」は演算子+を中心として部分式「X=A」と部分式「B」に分けてしまうこともできます。 このままでは式に複数の演算子が含まれている場合にどの演算子で分けるかあいまいなので、次のルールを加えます。
+
:ルール2|式を二分木で表す場合、最も低い優先順位の演算子を選び出して、その演算子を中心に部分式に分けることとする。
+
:ルール3|分けた後の部分式に演算子が含まれる場合は、さらにその節について分割を続ける。
 

        

        
 
例えば「X=A+B」の場合、A+Bを先に計算し、その結果をXに代入せよと言う意味なので、=は+より優先順位が低いことになります。
例えば「X=A+B」の場合、A+Bを先に計算し、その結果をXに代入せよと言う意味なので、=は+より優先順位が低いことになります。
 

        

        
~
ここまでで定めてきたルールに従って、式「X=A*B+C」を二分木に変換する場合について1ステップずつ見ていきます。 まず、この式の中で最も優先順位が低いのは「=」なので、これを中心に、「X」と「A*B+C」に分割します。
この要領で、「X=A*B+C」を1ステップずつ変換していくことにします。 まず、この式の中で最も優先順位が低いのは「=」なので、これを中心に、「X」と「A*B+C」に分割します。
 
#image(3.png,nopopup,XとA*B+C)
#image(3.png,nopopup,XとA*B+C)
 

        

        
~
つぎに、部分式「A*B+C」を二分木に変換します。 この式の中で最も優先順位が低いのは「+」なので、この式は「A*B」と「C」の部分式に分かれます。
つぎに、部分式「A*B+C」を木構造に変換します。 この式の中で最も優先順位が低いのは「+」なので、この式は「A*B」と「C」の部分式に分かれます。
 
#image(4.png,nopopup,XとA*BとC)
#image(4.png,nopopup,XとA*BとC)
 

        

        
 
最後に、「A*B」は「*」を中心に「A」と「B」に分割されるので、
最後に、「A*B」は「*」を中心に「A」と「B」に分割されるので、
 
#image(5.png,nopopup,A*BとC)
#image(5.png,nopopup,A*BとC)
 

        

        
~
となり、これで式「X=A*B+C」は二分木へと変換されました。
となり、これで式「X=A*B+C」は無事木構造へと変換されました。
+

          
+

          
 

        

        
~
**二分木から逆ポーランド記法化した数式を得る
**できあがった木構造から逆ポーランド記法の数式を得る
~
ここまでの手順で式を二分木にすることができました。 しかし、なぜ二分木にするのかという点については理由を明らかにしていませんでした。 式を二分木にした理由は、二分木からデータを読み出す順序を定義すると簡単に逆ポーランド記法化した式が得られるためです。
さて、ここまでで無事木構造が完成しました。 しかし、なぜ木構造にする必要があったかという疑問が生じているのではないでしょうか。 実は木構造からデータを読み出す順序を定義すると簡単に逆ポーランド記法化した式が得られるのです。
 

        

        
~
まず、二分木からデータを読み出す方法には三種類あります。 ここではその三種類の方法を示します。 木を探索することをトラバースすると言います。 トラバースする方法によって木から得られるデータの順番が変わってきます。
まず、木構造からデータを読み出す方法には三種類あります。 ここではその三種類の方法を示します。 木を探索することをトラバースすると言います。 トラバースする方法によって木から得られるデータの順番が変わってきます。
 

        

        
 
+''先行順序訪問 / 行きがけ順 (preorder traversal)''
+''先行順序訪問 / 行きがけ順 (preorder traversal)''
~
++あるノードNにたどり着いたら、そのノードNのデータを読む
++ある節にたどり着いたら、その節のデータを読む
~
++ノードNの左の子ノードLのデータを読む。 ノードLが部分木を持つのであれば1を繰り返す
++その節の左の節のデータを読む。 もし、その節が部分木を持つのであれば1を繰り返す
~
++ノードNの右の子ノードRのデータを読む。 ノードRが部分木を持つのであれば1を繰り返す
++その節の右の節のデータを読む。 もし、その節が部分木を持つのであれば1を繰り返す
~
++ノードNの親ノードへ戻る
++親の節へ戻る
 
+''中間順序訪問 / 通りがけ順 (inorder traversal)''
+''中間順序訪問 / 通りがけ順 (inorder traversal)''
~
++あるノードNにたどり着いたら、ノードNの左の子ノードLのデータを読む。 ノードLが部分木を持つのであれば1を繰り返す
++ある節にたどり着いたら、その節の左の節のデータを読む。 もし、その節が部分木を持つのであれば1を繰り返す
~
++ノードNのデータを読む
++その節のデータを読む
~
++ノードNの右の子ノードRのデータを読む。 ノードRが部分木を持つのであれば1を繰り返す
++その節の右の節のデータを読む。 もし、その節が部分木を持つのであれば1を繰り返す
~
++ノードNの親ノードへ戻る
++親の節へ戻る
 
+''後行順序訪問 / 帰りがけ順 (postorder traversal)''
+''後行順序訪問 / 帰りがけ順 (postorder traversal)''
~
++あるノードNにたどり着いたら、ノードNの左の子ノードLのデータを読む。 ノードLが部分木を持つのであれば1を繰り返す
++ある節にたどり着いたら、その節の左の節のデータを読む。 もし、その節が部分木を持つのであれば1を繰り返す
~
++ノードNの右の子ノードRのデータを読む。 ノードRが部分木を持つのであれば1を繰り返す
++その節の右の節のデータを読む。 もし、その節が部分木を持つのであれば1を繰り返す
~
++ノードNのデータを読む
++その節のデータを読む
~
++ノードNの親ノードへ戻る
++親の節へ戻る
+

          
+
ちょっと分かりにくいかと思いますが、上記の手順を端的に表すと次のようになります。 一筆書きの要領で木を左からなぞって巡回していき、行きがけ順では''ノードに到達したとき''、通りがけ順では左の子ノードの巡回が終わって''右の子ノードに移動するとき''、帰りがけ順では右の子ノードの''巡回が終わったとき''ノードのデータを読むようにします。 この方法通りにトラバースした場合、次のようになります。
+

          
+
&image(6-1.png,nopopup,先行順序訪問/行きがけ順でのノードの参照順序); &image(6-2.png,nopopup,中間順序訪問/通りがけ順でのノードの参照順序); &image(6-3.png,nopopup,後行順序訪問/帰りがけ順でのノードの参照順序);
+

          
+
つまり、行きがけ順では「N→L→R」、通りがけ順では「L→N→R」、帰りがけ順では「L→R→N」の順でデータが読み出されることになります。 ここで、先ほどの式「X=A*B+C」から作った木を各方法でトラバースしてみると、
+

          
+
#image(7.png,nopopup,X=A*B+C)
+

          
+
行きがけ順では「=X+*ABC」、通りがけ順では「X=A*B+C」、帰りがけ順では「XAB*C+=」のように読み出されます。 帰りがけ順では、ここでの目的である逆ポーランド化された式が読み出されています。 また、通りがけ順では、我々が一般的に使っている中置記法での式が読み出されています。
+

          
+
このように、式を二分木に変換し、その二分木から帰りがけ順で読み出すことにより、逆ポーランド記法化した式を得ることができます。
+

          
+

          
+

          
+
**二分木化した数式を使って計算を行う
+
ここまででは式から作成した二分木を探索(トラバース)することで式を様々な記法に変換する方法について解説してきましたが、ここからは作成した二分木を使って式の計算を行う方法をみていきます。 ここでは、等号や変数(記号)を含む場合については考えず、簡単化のため定数(数字)と四則演算子のみを含む式の計算を行う方法を考えます。 以下、計算する式として「2+5*3-4」を例にとり、最終的な計算結果として 13 を得るための方法をみていきます。
+

          
+
まず、式「2+5*3-4」を計算する場合、どのような手順をとれば正しい答えが得られるかを考えます。 式「2+5*3-4」は、値「2」と部分式「5*3-4」の演算結果を足したもの(+)と見ることができます。 式全体を計算するには、先に部分式「5*3-4」がどのような値となるかを計算する必要があります。 同様に、式「5*3-4」は部分式「5*3」の演算結果から値「4」を引いたもの(-)と見ることができます。 この部分式「5*3」の結果を求めれば式「5*3-4」の値も求まり、式「2+5*3-4」を計算できることになります。
+

          
+
つまり、まず式を左項・右項と演算子のみの部分式になるまで分割したのち、それぞれの部分式の演算結果を求めていくことにより最終的に式全体の計算結果を得ることができます。 部分式に分割する手順は、先に式を二分木に変換する際に使った手順をそのまま適用することができます。 そこで、この計算手順を二分木にあてはめて考えてみます。
+

          
+
まず、先に使った手順に従って式「2+5*3-4」を二分木に変換すると次の図のようになります。 演算子ノードの子ノードに演算の対象となる部分式または値(オペランド)が位置している点、また演算子の優先順位に従って式の分割を行ったため優先度の高い式が二分木の先端部分に位置している点に着目してください。
+

          
+
#image(8-1.png,nopopup,二分木化した式「2+5*3-4」)
+

          
+
二分木化した式では、すでに左項・右項と演算子のみに分割された状態になっています。 従って、この二分木に対して、
 

        

        
~
+二分木を根(root)から順に見ていき
ちょっと分かりにくいかと思いますが、簡単に説明すると、一筆書きの要領で木を左からなぞり、行きがけ順では最初に到達したとき、通りがけ順では通り過ぎるとき、帰りがけ順では巡回が終わった後にデータを読むわけです。 この方法通りにトラバースした場合、次のようになります。
~
+ノードに設定されている演算子に従って左項(左の子ノード)と右項(右の子ノード)の値を演算する
#image(6.png,nopopup,三種類のトラバース方法)
+
+このとき、項が部分式の場合(左または右の子ノードがさらに子ノードを持っている場合)は、先に2の操作を繰り返して部分式の演算結果を求める
 

        

        
~
という操作を行うことにより、最終的に式全体の値、すなわち式の計算結果を得ることができます。 この操作を、式「2+5*3-4」の二分木に対して行なっていくと次のようになります。
つまり、行きがけ順では「A→B→C」、通りがけ順では「B→A→C」、帰りがけ順では「B→C→A」の順でデータが読み出されます。 ここで、先ほどの式「X=A*B+C」から作った木を各方法でトラバースしてみると、
-
#image(5.png,nopopup,X=A*B+C)
 

        

        
~
#image(8-2.png,nopopup,二分木化した式の計算 step1)
行きがけ順では「=X+*ABC」、通りがけ順では「X=A*B+C」、帰りがけ順では「XAB*C+=」のように読み出されます。 帰りがけ順では、ここでの目的である逆ポーランド化された式が読み出されています。 また、トラバース方法を変えて通りがけ順で読み出すと、我々が一般的に使っている中置記法で取得できました。
+

          
+
まず、二分木の根を見ると、式は演算子が「+」で左項は値「2」、右項は子ノードを持っているため部分式となります。 部分式「5*3-4」にあたる部分木も左項に部分式「5*3」の子ノードを含んでいるため、まず部分式「5*3」にあたるノードの値を求めます。 このノードは左項が値「5」、右項が値「3」、演算子が「*」であるため、このノードは演算結果として値「15」を持つことになります。
+

          
+
#image(8-3.png,nopopup,二分木化した式の計算 step2)
+

          
+
部分式のノードの値が求まったことにより、上位の部分式の値を求めることができるようになったので、演算を続けます。 このノードは左項が先の演算によって得られた値「15」、右項が値「4」、演算子は「-」であるため、このノードは演算結果として値「11」を持つことになります。
+

          
+
#image(8-4.png,nopopup,二分木化した式の計算 step3)
+

          
+
最終的に、根のノードの左項と右項の値が求まったため、このノードの値を演算した結果、即ち「13」が式「2+5*3-4」の結果となります。 このように、式を演算子と項に分割した二分木に変換し、個々のノードの値を再帰的に演算していくことにより、式の計算を行うことができます。
 

        

        
 
さて、ここまででアルゴリズムの説明は終わりました。 次は実際にプログラムをみてみましょう。
さて、ここまででアルゴリズムの説明は終わりました。 次は実際にプログラムをみてみましょう。
 

        

        
370,14 295,13
 
-2項演算子のうち、四則演算子(+,-,*,/)、代入演算子(=)が使用可能
-2項演算子のうち、四則演算子(+,-,*,/)、代入演算子(=)が使用可能
 
-演算優先順位の指定に丸括弧()が使用可能
-演算優先順位の指定に丸括弧()が使用可能
 
-式の途中に空白を含むことも可能
-式の途中に空白を含むことも可能
+
-式が四則演算子と数値のみの場合は、式の計算を行うことが可能
 

        

        
 
となっています。
となっています。
 

        

        
~
まずは部分毎に説明していきます。 プログラム全文は最後に掲載しますので、必要に応じて参照してください。 [[C以外の言語での実装>#Implementation_OtherLang]]も用意しています。
まずは部分毎に説明していきます。 プログラム全文は最後に掲載しますので、必要に応じて参照してください。
 

        

        
 
**mainとNode構造体
**mainとNode構造体
~
まずは二分木を表現するためのNode型とmain関数でのプログラム全体の流れを見ていきます。
まずは木構造を表現するためのNode型とmain関数でのプログラム全体の流れを見ていきます。
 

        

        
 
#code(c){{
#code(c){{
 
typedef struct Node Node;
typedef struct Node Node;
424,7 348,6
 
void traverse_tree_postorder(Node* node);
void traverse_tree_postorder(Node* node);
 
void traverse_tree_inorder(Node* node);
void traverse_tree_inorder(Node* node);
 
void traverse_tree_preorder(Node* node);
void traverse_tree_preorder(Node* node);
+
double calculate(Node* node);
 

        

        
 
int main()
int main()
 
{
{
454,34 377,31
 
    traverse_tree_preorder(root);
    traverse_tree_preorder(root);
 
    printf("\n");
    printf("\n");
 

        

        
+
    printf("calculated result: %f\n", calculate(root));
+

          
 
    return 0;
    return 0;
 
}
}
 
}}
}}
 

        

        
 
Node型は、
Node型は、
~
:left|左の子ノード(部分木)へのポインタ
:left|左の節(部分木)へのポインタ
~
:right|右の子ノード(部分木)へのポインタ
:right|右の節(部分木)へのポインタ
~
:exp|そのノードの持つ部分式(項または演算子)
:exp|その節の持つ部分式(項)
 

        

        
 
を保持します。 最大MAX_NODES個(この例では80としました)のNodeをあらかじめ用意しておき、必要になったらcreate_node()関数で取得することにします。 また一つのNodeに格納できる部分式は終端文字を含めて最大MAX_EXP_LEN文字までとします。
を保持します。 最大MAX_NODES個(この例では80としました)のNodeをあらかじめ用意しておき、必要になったらcreate_node()関数で取得することにします。 また一つのNodeに格納できる部分式は終端文字を含めて最大MAX_EXP_LEN文字までとします。
 

        

        
 
main関数の流れは、
main関数の流れは、
~
+分解前の式全体を格納しておくため二分木の根、rootを作成
+分解前の式全体を格納しておくため木構造の根、rootを作成
 
+入力された式をrootにコピー
+入力された式をrootにコピー
 
+変換の前準備として、邪魔になる空白を削除(remove_space)
+変換の前準備として、邪魔になる空白を削除(remove_space)
~
+式を二分木に分割(parse_expression)
+式を木構造に分割(parse_expression)
~
+分割した二分木を
+分割した木構造を
 
++帰りがけ順でトラバースして表示(traverse_tree_postorder)
++帰りがけ順でトラバースして表示(traverse_tree_postorder)
 
++通りがけ順でトラバースして表示(traverse_tree_inorder)
++通りがけ順でトラバースして表示(traverse_tree_inorder)
 
++行きがけ順でトラバースして表示(traverse_tree_preorder)
++行きがけ順でトラバースして表示(traverse_tree_preorder)
+
++計算してその値を取得・表示(calculate)
 

        

        
 
となります。
となります。
 

        

        
~
**二分木への分割
**木構造への分割
~
次に、入力された式を二分木への分割を行う部分の関数を見てみます。
次に、木構造への分割を行う部分の関数を見てみます。
 

        

        
 
#code(cs){{
#code(cs){{
 
int remove_bracket(char *exp)
int remove_bracket(char *exp)
612,15 532,15
 

        

        
 
parse_expressionの流れを簡単に説明すると、
parse_expressionの流れを簡単に説明すると、
 
+まずget_pos_operatorで最も優先順位の低い演算子の位置を取得する
+まずget_pos_operatorで最も優先順位の低い演算子の位置を取得する
~
++演算子がなかった場合は、二分木への分割が完了したとして処理を終える
++演算子がなかった場合は、木構造への分割が完了したとして処理を終える
 
+演算子があった場合は、その演算子を中心に左右の部分式へ分割する
+演算子があった場合は、その演算子を中心に左右の部分式へ分割する
 
++ここで、remove_bracketで分割した部分式に含まれる、最も外側の括弧を削除する
++ここで、remove_bracketで分割した部分式に含まれる、最も外側の括弧を削除する
 
++分割した部分式について、parse_expressionでさらに分割する
++分割した部分式について、parse_expressionでさらに分割する
 

        

        
 
となっています。 parse_expressionは分割した部分式に演算子が含まれる限り、再帰的に呼び出され分割を繰り返します。 get_pos_operatorは、部分式のうち、括弧で括られていない部分で、かつ最も優先順位の低い演算子の位置を返します。
となっています。 parse_expressionは分割した部分式に演算子が含まれる限り、再帰的に呼び出され分割を繰り返します。 get_pos_operatorは、部分式のうち、括弧で括られていない部分で、かつ最も優先順位の低い演算子の位置を返します。
 

        

        
~
**二分木のトラバース
**木構造のトラバース
~
続いて、二分木のトラバースを行う関数を見てみます。
続いて、木構造のトラバースを行う関数を見てみます。
 

        

        
 
#code(c){{
#code(c){{
 
void traverse_tree_postorder(Node* node)
void traverse_tree_postorder(Node* node)
662,45 582,7
 
}
}
 
}}
}}
 

        

        
~
順に、帰りがけ順、通りがけ順、行きがけ順でトラバースする関数です。 与えられたノードに対してノードの持つ値の表示を行い、子ノードがある場合は再帰的にトラバースします。 なお、通りがけ順では見やすさのために括弧を付けて表示します。
順に、帰りがけ順、通りがけ順、行きがけ順でトラバースする関数です。 通りがけ順では見やすさのために括弧を付けて表示します。
+

          
+
**二分木からの値の演算
+
続いて、二分木から値の演算を行う関数を見てみます。
+

          
+
#code(c){{
+
double calculate(Node* node)
+
{
+
    double left_operand, right_operand;
+

          
+
    if (node->left && node->right) {
+
        left_operand  = calculate(node->left);
+
        right_operand = calculate(node->right);
+

          
+
        if (0 == strcmp(node->exp, "+"))
+
            return left_operand + right_operand;
+
        else if (0 == strcmp(node->exp, "-"))
+
            return left_operand - right_operand;
+
        else if (0 == strcmp(node->exp, "*"))
+
            return left_operand * right_operand;
+
        else if (0 == strcmp(node->exp, "/"))
+
            return left_operand / right_operand;
+
        else
+
            return 0.0;
+
    }
+
    else {
+
        return atof(node->exp);
+
    }
+
}
+
}}
+

          
+
calculate関数では、与えられたノードについて、
+
+左と右の両方に子ノードを持つ場合
+
++再帰的にcalculate関数を呼び出すことで左と右の部分木の計算結果を求め
+
++求めた左項・右項の値を使い、ノード自体の持つ演算子に従って演算結果を返す
+
+子ノードを持たない場合
+
++atof関数により文字列からdoubleに変換することでノード自身の持つ値を返す
+

          
+
という処理を行います。 再帰呼び出しを行うことにより、末端の部分木から順次値が定まって行きます。 この関数では0除算や、値を数値に変換できない場合などは考慮していません。
 

        

        
 
**プログラム全文
**プログラム全文
 
最後に、プログラム全文と実行例です。
最後に、プログラム全文と実行例です。
708,7 590,6
 
#code(c){{
#code(c){{
 
// gcc polish.c -o polish
// gcc polish.c -o polish
 
#include <stdio.h>
#include <stdio.h>
+
#include <stdlib.h>
 
#include <string.h>
#include <string.h>
 

        

        
 
typedef struct Node Node;
typedef struct Node Node;
911,30 792,6
 
        traverse_tree_preorder(node->right);
        traverse_tree_preorder(node->right);
 
}
}
 

        

        
+
double calculate(Node* node)
+
{
+
    double left_operand, right_operand;
+

          
+
    if (node->left && node->right) {
+
        left_operand  = calculate(node->left);
+
        right_operand = calculate(node->right);
+

          
+
        if (0 == strcmp(node->exp, "+"))
+
            return left_operand + right_operand;
+
        else if (0 == strcmp(node->exp, "-"))
+
            return left_operand - right_operand;
+
        else if (0 == strcmp(node->exp, "*"))
+
            return left_operand * right_operand;
+
        else if (0 == strcmp(node->exp, "/"))
+
            return left_operand / right_operand;
+
        else
+
            return 0.0;
+
    }
+
    else {
+
        return atof(node->exp);
+
    }
+
}
+

          
 
int main()
int main()
 
{
{
 
    Node* root = create_node();
    Node* root = create_node();
963,31 820,19
 
    traverse_tree_preorder(root);
    traverse_tree_preorder(root);
 
    printf("\n");
    printf("\n");
 

        

        
+
    printf("calculated result: %f\n", calculate(root));
+

          
 
    return 0;
    return 0;
 
}
}
 
}}
}}
 

        

        
~
#prompt(実行例1){{
#prompt(実行例){{
 
input expression: x = y * 4 + (2-z) /3
input expression: x = y * 4 + (2-z) /3
 
expression: x=y*4+(2-z)/3
expression: x=y*4+(2-z)/3
 
reverse polish notation: xy4*2z-3/+=
reverse polish notation: xy4*2z-3/+=
 
infix notation: (x=((y*4)+((2-z)/3)))
infix notation: (x=((y*4)+((2-z)/3)))
 
polish notation: =x+*y4/-2z3
polish notation: =x+*y4/-2z3
+
calculated result: 0.000000
+
}}
+

          
+
#prompt(実行例2){{
+
input expression: 1+4*2+(7-3)/2
+
expression: 1+4*2+(7-3)/2
+
reverse polish notation: 142*+73-2/+
+
infix notation: ((1+(4*2))+((7-3)/2))
+
polish notation: ++1*42/-732
+
calculated result: 11.000000
 
}}
}}
 

        

        
~
*他の言語での実装 [#Implementation_OtherLang]
*他の言語での実装
 
ここまでで紹介したアルゴリズムをC以外の言語で実装したものを以下のページに掲載しておきます。 比較して読めるように、いずれもCでの実装に近い記述にしてあります。
ここまでで紹介したアルゴリズムをC以外の言語で実装したものを以下のページに掲載しておきます。 比較して読めるように、いずれもCでの実装に近い記述にしてあります。
 

        

        
 
-[[programming/tips/polish/impl_cs]]
-[[programming/tips/polish/impl_cs]]
998,9 843,6
 
なお、[[最初に挙げたデモ>#ConversionDemo]]はJavascriptで実装しています。 ソースコードについてはこのページのソースに含まれています。
なお、[[最初に挙げたデモ>#ConversionDemo]]はJavascriptで実装しています。 ソースコードについてはこのページのソースに含まれています。
 

        

        
 
*文書情報
*文書情報
+
:2013-07-02|二分木に変換した数式の計算を行うアルゴリズムについてを加筆
+
用語の不統一を修正
+
VB8での実装のバグを修正
 
:2012-07-09|変換のデモを追加
:2012-07-09|変換のデモを追加
 
Javascriptでの実装を追記
Javascriptでの実装を追記
 
Javaでの実装を追記
Javaでの実装を追記

programming/tips/polish/impl_vb/index.wiki.txt

current previous
46,7 46,7
 

        

        
 
    Dim nest As Integer = 1
    Dim nest As Integer = 1
 

        

        
~
    For i As Integer = 1 To str.Length - 2
    For i As Integer = 1 To str.Length - 1
 
      If str(i) = "(" Then
      If str(i) = "(" Then
 
        nest += 1
        nest += 1
 
      Else If str(i) = ")" Then
      Else If str(i) = ")" Then
121,23 121,6
 
    If Left  IsNot Nothing Then Left .TraversePreorder()
    If Left  IsNot Nothing Then Left .TraversePreorder()
 
    If Right IsNot Nothing Then Right.TraversePreorder()
    If Right IsNot Nothing Then Right.TraversePreorder()
 
  End Sub
  End Sub
+

          
+
  Public Function Calculate() As Double
+
    If Left IsNot Nothing AndAlso Right IsNot Nothing Then
+
      Dim leftOperand  As Double = Left.Calculate()
+
      Dim rightOperand As Double = Right.Calculate()
+

          
+
      Select Case Expression
+
        Case "+": Return leftOperand + rightOperand
+
        Case "-": Return leftOperand - rightOperand
+
        Case "*": Return leftOperand * rightOperand
+
        Case "/": Return leftOperand / rightOperand
+
        Case Else: Return 0.0
+
      End Select
+
    Else
+
      Return Double.Parse(Expression)
+
    End If
+
  End Function
 
End Class
End Class
 

        

        
 
Class Polish
Class Polish
161,8 144,6
 
    Console.Write("polish notation: ")
    Console.Write("polish notation: ")
 
    root.TraversePreorder()
    root.TraversePreorder()
 
    Console.WriteLine()
    Console.WriteLine()
+

          
+
    Console.WriteLine("calculated result: {0}", root.Calculate())
 
  End Sub
  End Sub
 
End Class
End Class
 
}}
}}

programming/tips/polish/impl_java/index.wiki.txt

current previous
129,27 129,6
 
    if (right != null)
    if (right != null)
 
      right.traversePreorder();
      right.traversePreorder();
 
  }
  }
+

          
+
  public double calculate() {
+
    if (left != null && right != null) {
+
      double leftOperand  = left.calculate();
+
      double rightOperand = right.calculate();
+

          
+
      if (expression.equals("+"))
+
        return leftOperand + rightOperand;
+
      else if (expression.equals("-"))
+
        return leftOperand - rightOperand;
+
      else if (expression.equals("*"))
+
        return leftOperand * rightOperand;
+
      else if (expression.equals("/"))
+
        return leftOperand / rightOperand;
+
      else
+
        return 0.0;
+
    }
+
    else {
+
      return Double.parseDouble(expression);
+
    }
+
  }
 
}
}
 

        

        
 
public class Polish {
public class Polish {
175,8 154,6
 
    System.out.print("polish notation: ");
    System.out.print("polish notation: ");
 
    root.traversePreorder();
    root.traversePreorder();
 
    System.out.println();
    System.out.println();
+

          
+
    System.out.println("calculated result: " + root.calculate());
 
  }
  }
 
}
}
 
}}
}}

programming/tips/polish/impl_ruby/index.wiki.txt

current previous
120,23 120,6
 
    @left .traverse_preorder if @left
    @left .traverse_preorder if @left
 
    @right.traverse_preorder if @right
    @right.traverse_preorder if @right
 
  end
  end
+

          
+
  def calculate
+
    if @left and @right
+
      left_operand  = @left.calculate()
+
      right_operand = @right.calculate()
+

          
+
      case @expression
+
        when '+' then return left_operand + right_operand
+
        when '-' then return left_operand - right_operand
+
        when '*' then return left_operand * right_operand
+
        when '/' then return left_operand / right_operand
+
        else return 0.0
+
      end
+
    else
+
      return @expression.to_f
+
    end
+
  end
 
end
end
 

        

        
 
print 'input expression: '
print 'input expression: '
158,10 141,6
 
print "polish notation: "
print "polish notation: "
 
root.traverse_preorder
root.traverse_preorder
 
print "\n"
print "\n"
+

          
+
print "calculated result: "
+
print root.calculate
+
print "\n"
 
}}
}}
 

        

        
 

        

        

programming/tips/polish/impl_cs/index.wiki.txt

current previous
6,7 6,7
 
#googleadunit
#googleadunit
 

        

        
 
#code(cs){{
#code(cs){{
~
// mcs polish.cs && mono polish.exe
// gmcs polish.cs && mono polish.exe
 
using System;
using System;
 

        

        
 
class Node {
class Node {
136,25 136,6
 
    if (Right != null)
    if (Right != null)
 
      Right.TraversePreorder();
      Right.TraversePreorder();
 
  }
  }
+

          
+
  public void Calculate()
+
  {
+
    if (Left != null && Right != null) {
+
      var leftOperand  = Left.calculate();
+
      var rightOperand = Right.calculate();
+

          
+
      switch (this.expression) {
+
        case "+": return leftOperand + rightOperand;
+
        case "-": return leftOperand - rightOperand;
+
        case "*": return leftOperand * rightOperand;
+
        case "/": return leftOperand / rightOperand;
+
        default:  return 0.0;
+
      }
+
    }
+
    else {
+
      return double.Parse(Expression);
+
    }
+
  }
 
}
}
 

        

        
 
class Polish {
class Polish {
179,8 160,6
 
    Console.Write("polish notation: ");
    Console.Write("polish notation: ");
 
    root.TraversePreorder();
    root.TraversePreorder();
 
    Console.WriteLine();
    Console.WriteLine();
+

          
+
    Console.WriteLine("calculated result: {0}", root.Calculate());
 
  }
  }
 
}
}
 
}}
}}