2018-01-21T20:37:34の更新内容

programming/tips/polish/index.wiki.txt

current previous
2,171 2,190
 
${smdncms:set-metadata,keywords,ポーランド記法,逆ポーランド記法,前置記法,後置記法,中置記法,二分木}
${smdncms:set-metadata,keywords,ポーランド記法,逆ポーランド記法,前置記法,後置記法,中置記法,二分木}
 
${smdncms:set-metadata,tags,lang/c,algo}
${smdncms:set-metadata,tags,lang/c,algo}
 

                

                
~
#style(source=polish-expressiontree.css)
[[逆ポーランド記法とは>#SummaryReversePolishNotation]]何か、[[数式を逆ポーランド記法化する>#ConversionDemo]]とどのようになるか、また[[二分木を使って数式を逆ポーランド記法化するアルゴリズム>#Algorithm]]と[[C言語による実装>#Implementation_C]]を紹介します。
~
#script(source=_source/polish.js)

                  
~
#script(source=polish-expressiontree.js)
*逆ポーランド記法とは [#SummaryReversePolishNotation]
~

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

                  
~
<svg xmlns="http://www.w3.org/2000/svg" id="svg-definitions">
逆ポーランド記法で記述された数式``x32*1+=``は、「``x``は``3``と``2``を掛けた(``*``)ものに``1``を足して(``+``)代入した(``=``)もの」と読むことができます。 より機械的な表現では「``x``は``3``と``2``を``*``したものに``1``を``+``して``=``したもの」と読むこともできます。 つまり、この表記においては、演算対象と演算処理が処理順に記述されることになります。 プログラミングなどでは``x = 3 * 2 + 1;``といった式を書きますが、実は実行時にはスタックというものを使って逆ポーランド記法的に計算しています。
~
  <defs>

                  
~
    <symbol class="expressiontree-traversalorder-path-marker" id="expressiontree-traversalorder-path-marker-arrow" viewBox="-5 -5 10 10">
このように、項の後ろに演算子記号を記述する方式を''逆ポーランド記法(後置記法)''と言います。 対して、最初に挙げた馴染み深い記法、つまり項の間に演算子を記述する方式を''中置記法''、項の前に演算子が来る記法を''ポーランド記法(前置記法)''と言います。
~
      <polygon points="+5,0 -5,-5, -2,0 -5,+5"/>

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

                  
-
#html{{
-
<form action="">
-
  <table>
-
    <caption>数式のポーランド記法化・逆ポーランド記法化と数式計算のデモ</caption>
-
    <tr>
-
      <th>変換する数式</th>
-
      <td>
-
        <div>
-
          <input type="text" id="polish_demo_input" value="" size="25" list="polish_demo_expressions" />
-
          <datalist id="polish_demo_expressions">
-
            <option value="x = 3 * 2 + 1" />
-
            <option value="x = a * (b + c)" />
-
            <option value="2+5*3-4" />
-
            <option value="1+4*2+(7-3)/2" />
-
            <option value="1 + 2 + X = Y + 3 + 4" />
-
          </datalist>
-
          <input type="button" value="変換" onclick="polish_demo_convert();"/>
-
          <input type="reset" value="クリア"/>
-
        </div>
-
        <div id="polish_demo_result_error"></div>
-
        <div>
-
          記入例
-
          <ul>
-
            <li><code class="inline">x = 3 * 2 + 1</code></li>
-
            <li><code class="inline">x = a * (b + c)</code></li>
-
            <li><code class="inline">2+5*3-4</code></li>
-
            <li><code class="inline">1+4*2+(7-3)/2</code></li>
-
            <li><code class="inline">1 + 2 + X = Y + 3 + 4</code></li>
-
          </ul>
-
        </div>
-
      </td>
-
    </tr>
-
    <tr>
-
      <th>ポーランド記法<br/>(前置記法化した数式)</th>
-
      <td>
-
        <input type="text" id="polish_demo_result_preorder" size="40" />
-
      </td>
-
    </tr>
-
    <tr>
-
      <th>逆ポーランド記法<br/>(後置記法化した数式)</th>
-
      <td>
-
        <input type="text" id="polish_demo_result_postorder" size="40" />
-
      </td>
-
    </tr>
-
    <tr>
-
      <th>元の数式から再構成した数式<br/>(中置記法の数式)</th>
-
      <td>
-
        <input type="text" id="polish_demo_result_inorder" size="40" />
-
      </td>
-
    </tr>
-
    <tr>
-
      <th>数式の計算結果</th>
-
      <td>
-
        <input type="text" id="polish_demo_result_calculate" size="40" />
-
      </td>
-
    </tr>
-
  </table>
-
</form>
 
}}
}}
 

                

                
~
#commentout(no-comment-node){{{
#javascript(polish_demo_implementation,source=_source/polish.js)
~
#script(source=polish-convert-svg-to-canvas.js)

                  
-
#javascript(polish_demo_runner,noscript=実行するにはJavaScriptを有効にしてください){{
-
"use strict"
 

                

                
~
#script{{
class PseudoStdOut {
~
$(function(){
  constructor()
~
  // convert svg animation to canvas frame
  {
~
  if (false) {
    this.buffer = "";
+
    const autoDownload = false;
+
    let svgDefs = document.getElementById("svg-definitions");
+

                  
+
    document.addEventListener("DOMContentLoaded", function(event) {
+
      /*
+
      Array.prototype.forEach.call(document.querySelectorAll("svg"), (svg) => {
+
        emitCanvasFramesFromSvg(svg, svgDefs, autoDownload);
+
      });
+
      */
+

                  
+
      emitCanvasFramesFromSvg(document.querySelector(".figure-content[data-filename='algorithm-traversebinarytree-preordertraversal.svg'] svg"),
+
                              svgDefs, autoDownload);
+
    });
 
  }
  }
 

                

                
~
  // display fallback content of <svg>
  write(val)
~
  if (false) {
  {
~
    Array.prototype.forEach.call(document.querySelectorAll(".figure-content-svg svg"), (svg) => {
    this.buffer += val;
~
      Array.prototype.forEach.call(svg.querySelectorAll(".figure-content-fallback"), (f) => {
  }
~
        svg.parentNode.appendChild(f);
}
+
      });
 

                

                
~
      svg.parentNode.removeChild(svg);
class DemoNode extends Node {
~
    });
  constructor(expression)
-
  {
-
    super(expression);
 
  }
  }
+
});
+
}}
+
}}}
 

                

                
~
[[逆ポーランド記法とは>#SummaryReversePolishNotation]]何か、[[数式を逆ポーランド記法化する>#ConversionDemo]]とどのようになるか、また[[二分木を使って数式を逆ポーランド記法化するアルゴリズム>#Algorithm]]と[[C言語による実装>#Implementation_C]]を紹介します。
  getPostorerNotation()
-
  {
-
    let stdout = new PseudoStdOut();
 

                

                
~
*逆ポーランド記法とは [#SummaryReversePolishNotation]
    this.traversePostorder(stdout);
+
一般に人が読むことを前提にした数式は``x = 1 - 2 + 3``の様な形式で表記されますが、演算の順序などを考えるとコンピュータにとってはこの表記は扱いにくいものです。 コンピュータとしてはこの式は``x 1 2 - 3 + =``と表記されていたほうが扱いやすくなります。 このような形式での表記が逆ポーランド記法です。
 

                

                
~
逆ポーランド記法で記述された数式``x 1 2 - 3 + =``は、「``x``に``1``から``2``を引いた(``-``)ものに``3``を足して(``+``)代入する(``=``)」と読むことができます。 より機械的な表現にすれば「``x``に、``1``に``2``を``-``して、それに``3``を``+``して、それを``=``する」と読むこともできます。 つまり、この表記においては、演算対象と演算処理が処理順に記述されることになります。 プログラミングなどでは``x = 1 - 2 + 3;``といった式を書きますが、実は実行時にはスタックというものを使って逆ポーランド記法的に計算しています。
    return stdout.buffer;
-
  }
 

                

                
~
このように、項の後ろに演算子記号を記述する方式を''逆ポーランド記法''(reverse Polish notation; RPN)あるいは''後置記法''と言います。 対して、最初に挙げた馴染み深い記法、つまり項の間に演算子を記述する方式を''中置記法''、項の前に演算子が来る記法を''ポーランド記法''(Polish notation; PN)あるいは''前置記法''と言います。
  getInorderNotation()
-
  {
-
    let stdout = new PseudoStdOut();
 

                

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

                

                
~
#remarks
    return stdout.buffer;
~
このデモを実行するにはEdge・Chrome・Firefox・Safariいずれかのブラウザをご利用ください。 なお、Edgeでは変換過程・計算過程のアニメーションは表示されません。
  }
 

                

                
~
このデモでできる変換処理と制限事項については[[Cでの実装の項>#Implementation_C]]をご覧ください。
  getPreorderNotation()
~
#remarks-end
  {
-
    let stdout = new PseudoStdOut();
 

                

                
~
#script(source=polish-demo.js,noscript=このデモを実行するにはJavaScriptを有効にしてください。)
    this.traversePreorder(stdout);
+
#html(source=polish-demo.xhtml)
 

                

                
~
#tabpage(ポーランド記法・前置記法)
    return stdout.buffer;
~
#figure-svg(title=二分木化した数式と記法の変換過程,title=ポーランド記法・前置記法,id-content=polish-demo-expressiontree-traverse-preorder){{
  }
~
<svg xmlns="http://www.w3.org/2000/svg" width="0" height="0"><title>placeholder</title><animate/></svg>
}
+
}}
 

                

                
~
#tabpage(逆ポーランド記法・後置記法)
function polish_demo_convert()
~
#figure-svg(title=二分木化した数式と記法の変換過程,title=逆ポーランド記法・後置記法,id-content=polish-demo-expressiontree-traverse-postorder){{
{
~
<svg xmlns="http://www.w3.org/2000/svg" width="0" height="0"><title>placeholder</title><animate/></svg>
  $('#polish_demo_result_postorder').val('');
~
}}
  $('#polish_demo_result_inorder').val('');
-
  $('#polish_demo_result_preorder').val('');
-
  $('#polish_demo_result_calculate').val('');
-
  $('#polish_demo_result_error').html('<pre></pre>');
-

                  
-
  try {
-
    let expression = $('#polish_demo_input').val();
-
    let root = new DemoNode(expression.replace(/\s+/g, ''));
-

                  
-
    root.parse();
-

                  
-
    $('#polish_demo_result_postorder').val(root.getPostorerNotation());
-
    $('#polish_demo_result_inorder').val(root.getInorderNotation());
-
    $('#polish_demo_result_preorder').val(root.getPreorderNotation());
-

                  
-
    if (root.calculate()) {
-
      $('#polish_demo_result_calculate').val(root.expression);
-
      $('#polish_demo_result_error').html('<pre style="color:green;">expression calculated</pre>');
-
    }
-
    else {
-
      $('#polish_demo_result_calculate').val(root.getInorderNotation());
-
      $('#polish_demo_result_error').html('<pre style="color:orange;">expression not calculated</pre>');
-
    }
-
  }
-
  catch (e) {
-
    $('#polish_demo_result_calculate').val('');
-
    $('#polish_demo_result_error').html('<pre style="color:red;">' + e + '</pre>');
-
  }
-
}
 

                

                
~
#tabpage(中置記法)
$(function(){
~
#figure-svg(title=二分木化した数式と記法の変換過程,title=中置記法,id-content=polish-demo-expressiontree-traverse-inorder){{
  // set default expression
~
<svg xmlns="http://www.w3.org/2000/svg" width="0" height="0"><title>placeholder</title><animate/></svg>
  $('#polish_demo_input').val('x = 3 * 2 + 1');
-
});
 
}}
}}
 

                

                
~
#tabpage(計算)
#adunit
+
#figure-svg(title=二分木化した数式と数式の計算過程,id-content=polish-demo-expressiontree-calculation){{
+
<svg xmlns="http://www.w3.org/2000/svg" width="0" height="0"><title>placeholder</title><animate/></svg>
+
}}
 

                

                
~
#tabpage-end
このデモでできる変換処理と制限事項については[[Cでの実装の項>#Implementation_C]]をご覧ください。
 

                

                
+
#adunit
 

                

                
 
*二分木を使った逆ポーランド記法化のアルゴリズム [#Algorithm]
*二分木を使った逆ポーランド記法化のアルゴリズム [#Algorithm]
~
逆ポーランド記法化を行うアルゴリズムには様々なものがあり、一例として[[スタック(stack)>programming/netfx/collections/2_generic_5_1_stack#Stack]]を使うものがありますが、ここではスタックではなく''二分木''を使って数式を逆ポーランド記法に変換する方法について解説します。 また、二分木に変換した数式を使って数式の計算を行う方法についても解説します。
逆ポーランド記法化を行うアルゴリズムには様々なものがあり、一例として[[スタック(stack)>programming/netfx/collections/2_generic_5_1_stack#Stack]]を使うものがありますが、ここではスタックではなく二分木を使って数式を逆ポーランド記法に変換する方法について解説します。 また、二分木に変換した数式を使って数式の計算を行う方法についても解説します。
 

                

                
 

                

                
 

                

                
 
**二分木とは [#Algorithm_BinaryTree]
**二分木とは [#Algorithm_BinaryTree]
 
''二分木(binary tree)''とは節から''二本に枝分かれ''した''木(tree)''のようなデータ構造です。 この木構造は二分探索などのアルゴリズムでよく用いられるデータ構造です。
''二分木(binary tree)''とは節から''二本に枝分かれ''した''木(tree)''のようなデータ構造です。 この木構造は二分探索などのアルゴリズムでよく用いられるデータ構造です。
 

                

                
~
二分木の構造として、まず''根(root)''があり、そこから二本に枝分かれします。 枝分かれする元を''節(node)''、枝分かれした先を''葉(leaf)''といいます。 ただ一般に、根・節・葉は特に強調する必要がある場合を除くと全てまとめて''ノード''と呼ばれることがほとんどで、根を表す場合に''ルートノード''と呼ばれることがある程度です。
二分木の構造として、まず''根(root)''があり、そこから二本に枝分かれします。 枝分かれする元を''節(node)''、枝分かれした先を''葉(leaf)''といいます。 根や葉を区別せずに全てまとめてノードと呼ぶこともあります。
+

                  
+
また、あるノードから見た根本側のノードを''親(parent)''または''親ノード''といい、あるノードから枝分かれした先のノードを''子(child)''または''子ノード''といいます。 二分木では常に二本に枝分かれするため、子ノードを持つ場合は''左の子ノード''と''右の子ノード''の2つを持つことになります。 ルートノードから枝分かれする二分木全体を''木''と呼ぶのに対して、あるノードをルートノードとみなし、その下位に枝分かれする部分を''部分木(subtree)''と呼びます。
 

                

                
~
二分木の一例と構造上の名称を図にすると次のようになります。
また、ある節から見た根本の節を''親(parent)''といい、節から見た''枝(branch)''の先を''子(child)''、同じ親をもつ子同士を''兄弟(sibling)''といい、親ノード・子ノードなどと呼びます。 さらに、ある節を根とみなし、それ以下の構造を''部分木(subtree)''とも言います。
+
#commentout(no-comment-node){{{
+
#html{{
+
<div>
+
  <div id="_binarytree-1"/>
+
  <div id="_binarytree-2"/>
+
<script>//<![CDATA[
+
let tree1 = new ExpressionTreeNode(
+
  "root",
+
  new ExpressionTreeNode(
+
    "node",
+
    new ExpressionTreeNode("leaf" /*"node\n(leaf)"*/),
+
    new ExpressionTreeNode("leaf" /*"node\n(leaf)"*/),
+
  ),
+
  new ExpressionTreeNode(
+
    "parent",
+
    new ExpressionTreeNode("child" /*"child\n(left)"*/),
+
    new ExpressionTreeNode("child" /*"child\n(right)"*/),
+
  ),
+
);
+

                  
+
let target1 = document.getElementById("_binarytree-1").appendChild(VisualTreeNode.createSvgElement());
+

                  
+
tree1.createVisualTree().render(target1);
+

                  
+
Svg.minimizeElement(target1, 5);
+

                  
+
let tree2 = new ExpressionTreeNode(
+
  "root",
+
  new ExpressionTreeNode(
+
    "node",
+
  ),
+
  new ExpressionTreeNode(
+
    "node",
+
    new ExpressionTreeNode("node"),
+
    new ExpressionTreeNode("node"),
+
  ),
+
);
+

                  
+
let target2 = document.getElementById("_binarytree-2").appendChild(VisualTreeNode.createSvgElement());
+

                  
+
tree2.createVisualTree().render(target2, true);
+

                  
+
Svg.minimizeElement(target2, 5);
+

                  
+
//]]></script>
+
</div>
+
}}
+
}}}
 

                

                
~
#column
二分岐の一例と構造上の名称を図にすると次のようになります。
~
#figure-svg(title=二分木の構造と名称,title=ルートノード・親ノード・子ノード,source=algorithm-binarytree-tree1.svg,fallback-image=algorithm-binarytree-tree1.png)
#image(0.png,nopopup,二分木)
+
#column
+
#figure-svg(title=二分木の構造と名称,title=木と部分木,source=algorithm-binarytree-tree2.svg,fallback-image=algorithm-binarytree-tree2.png)
+
#column-end
 

                

                
~
また、プログラミングによって二分木のデータ構造を表現する場合は、次のような構造体を用いることが多いです。
実際にプログラミングによって二分木のデータ構造を表現する場合は、次のような構造体を用いることが多いです。 この例では各々のノードが持ちうる値は``int``型であるとしています。
~
#code(c,二分木を表現するデータ構造の例,no-code-commands) {{
#code(c) {{
 
struct Node
struct Node
 
{
{
 
    int   data;
    int   data;
175,469 194,124
 
};
};
 
}}
}}
 

                

                
~
つまり、ノード自体が持つデータと、右と左の子ノードへのポインタを構造体のメンバとして持つわけです。 子を持たないノードを表すには``left``および``right``にヌル参照を設定するなどします。 また、この例では各々のノードが持ちうる値は``int``型であるとしていますが、扱うデータに応じて型を選択します。
つまり、右と左の子ノードへのポインタと、そのノード自体が持つデータを構造体のメンバとして持つわけです。 子を持たないノード、つまり葉のノードを表すには右と左の子ノードとしてヌル参照を設定します。
 

                

                
+
**数式を二分木に変換する [#Algorithm_ParseExpression]
+
数式を逆ポーランド記法化する前の下準備として、まずは式を二分木に変換します。 なぜ二分木にする必要があるのか、どのような利点があるのかという点については[[後述する>#Algorithm_TraverseBinaryTree]]として、まずは[[式を二分木に変換する手順>#Algorithm_ParseExpression_Definition]]について考え、例として式``x = 1 - 2 + 3``に[[手順を適用する場合>#Algorithm_ParseExpression_Application]]を見ていきます。
 

                

                
+
***変換手順の定義 [#Algorithm_ParseExpression_Definition]
+
#commentout(no-comment-node){{{
+
#html{{
+
<div>
+
  <div id="_tree"/>
+
<script>//<![CDATA[
+
// 1
+
/*
+
let root = new ExpressionTreeNode(
+
  "+",
+
  new Node("A"),
+
  new Node("B"),
+
);
+
*/
+

                  
+
// 2-1
+
/*
+
let root = new ExpressionTreeNode(
+
  "=",
+
  new Node("X"),
+
  new ExpressionTreeNode("A + B"),
+
);
+
*/
+

                  
+
// 2-2
+
/*
+
let root = new ExpressionTreeNode(
+
  "=",
+
  new Node("X"),
+
  new ExpressionTreeNode(
+
    "+",
+
    new Node("A"),
+
    new Node("B"),
+
  ),
+
);
+
*/
+

                  
+
// 3-0
+
/*
+
let root = new ExpressionTreeNode(
+
  "x = 1 - 2 + 3",
+
);
+
*/
 

                

                
~
// 3-1
**数式を二分木に変換する [#Algorithm_ParseExpression]
~
/*
数式を逆ポーランド記法化する前の下準備としてに、式を二分木に変換します。 なぜ二分木にする必要があるのか、どのような利点があるのかという点については後述するとして、まずは変換する式として``X=A*B+C``を例にとって二分木に変換する方法を考えていきます。 まずはじめに、式を二分木に変換する方法を次のように定義します。
+
let root = new ExpressionTreeNode(
+
  "=",
+
  new Node("x"),
+
  new Node("1 - 2 + 3"),
+
);
+
*/
+

                  
+
/*
+
// 3-2
+
let root = new ExpressionTreeNode(
+
  "=",
+
  new Node("x"),
+
  new ExpressionTreeNode(
+
    "+",
+
    new Node("1 - 2"),
+
    new Node("3"),
+
  ),
+
);
+
*/
+

                  
+
/*
+
// 3-3
+
let root = new ExpressionTreeNode(
+
  "=",
+
  new Node("x"),
+
  new ExpressionTreeNode(
+
    "+",
+
    new ExpressionTreeNode(
+
      "-",
+
      new Node("1"),
+
      new Node("2"),
+
    ),
+
    new Node("3"),
+
  ),
+
);
+
*/
+

                  
+
let target = document.getElementById("_tree").appendChild(VisualTreeNode.createSvgElement());
+

                  
+
root.createVisualTree().render(target);
+

                  
+
Svg.minimizeElement(target, 5);
+
//]]></script>
+
</div>
+
}}
+
}}}
+

                  
+
まずはじめに、式を二分木に変換する手順を次のように定義します。
+

                  
+
:ルール0(前提条件)|演算子は左右に1つずつ、計2つの''部分式または項''を持つものとする。
+
:ルール1|式を二分木に変換する場合、演算子をノード自身に、演算子の左側の部分式を左の子ノードに、演算子の右側の部分式を右の子ノードに、それぞれ分けて持つこととする。
 

                

                
~
式``A + B``の場合を考えると、演算子``+``・左側の部分式``A``・右側の部分式``B``からなるため、ルール1に従うと次のような二分木になります。
:ルール1|演算子は2つの部分式(項)を必要とする。 これを二分木で表す場合、演算子の左側の部分式を左の子ノード、演算子の右側の部分式を右の子ノード、演算子自体をノード自身に持つこととする。
+
#figure-svg(title=式「A + B」の二分木,source=algorithm-parseexpression-tree1.svg,fallback-image=algorithm-parseexpression-tree1.png)
 

                

                
~
つぎに、式``X = A + B``について考えてみると、演算子``=``・左側の部分式``X``・右側の部分式``A + B``からなるため、ルール1に従うと次のような二分木になります。
つまり、式``A+B``は次のような二分木になるものとします。
~
#figure-svg(title=式「X=A+B」の二分木(1),source=algorithm-parseexpression-tree2-1.svg,fallback-image=algorithm-parseexpression-tree2-1.png)
#image(1.png,nopopup,A+Bの二分木)
 

                

                
~
ここで、もうひとつ手順を定義します。
さらに、式``X=A+B``について考えてみると、演算子``=``の左の部分式を``X``、右の部分式を``A+B``と考えることができるので、このような二分木になるものとします。
-
#image(2.png,nopopup,X=A+Bの二分木)
 

                

                
~
:ルール2|左右の子ノードに分けた部分式に演算子が含まれる場合は、さらにルール1を適用して部分式が項のみとなるまで繰り返す。
しかし、単純に演算子の左側・右側で部分式に分けるというルールでは、式``X=A+B``は演算子``+``を中心として部分式``X=A``と部分式``B``に分けてしまうこともできてしまいます。 式``1+2*3``の場合も同様に、「部分式``1+2``演算子``*``部分式``3``」あるいは「部分式``1``演算子``+``部分式``2*3``」のどちらにも考えることができてしまいます。
 

                

                
~
この右側の子ノードの部分式``A + B``は演算子を含んでいるため、ルール2に従うことになります。 ルール2に従いこの部分式``A + B``にルール1を適用すると、先ほどの式``A + B``と同じ二分木となります。 したがって、式``X = A + B``全体では次のような二分木になります。
このままでは式に複数の演算子が含まれている場合にどの演算子で分けるかあいまいなので、次のルールを加えます。
~
#figure-svg(title=式「X=A+B」の二分木(2),source=algorithm-parseexpression-tree2-2.svg,fallback-image=algorithm-parseexpression-tree2-2.png)
:ルール2|式を二分木で表す場合、最も低い優先順位の演算子を選び出して、その演算子を中心に部分式に分けることとする。
-
:ルール3|分けた後の部分式に演算子が含まれる場合は、さらにその節について分割を続ける。
 

                

                
~
しかし、ここまでで定義したルールでは単に「演算子の左側・右側で部分式に分ける」としています。 そのため、式``X = A + B``は演算子``+``を中心として部分式``X = A``と部分式``B``に分けることもできてしまいます。
例えば式``X=A+B``の場合、``A+B``を先に計算し、その結果を``X``に代入せよと言う意味なので、``=``は``+``より優先順位が低いことになります。
 

                

                
~
つまり、先に定義したルール1とルール2だけでは、式に複数の演算子が含まれている場合どの演算子で分けるかがあいまいになります。 そこで、次のルールを加えることにします。
ここまでで定めてきたルールに従って、式``X=A*B+C``を二分木に変換する場合について1ステップずつ見ていきます。 まず、この式の中で最も優先順位が低いのは``=``なので、これを中心に、``X``と``A*B+C``に分割します。
~
:ルール3|ルール1で式を演算子と部分式に分ける際、式中で最も''右側''にあり、かつ最も''優先順位が低い''演算子を選び出して、その演算子を中心に部分式に分けることとする。
#image(3.png,nopopup,XとA*B+C)
+
演算子の優先順位は、高いものから順に 1:``*`` ``/`` 2:``+`` ``-`` 3:``=``とする。
 

                

                
~
このルールを、いくつかの式にあてはめて確認すると次のようになります。
つぎに、部分式``A*B+C``を二分木に変換します。 この式の中で最も優先順位が低いのは``+``なので、この式は``A*B``と``C``の部分式に分かれます。
-
#image(4.png,nopopup,XとA*BとC)
 

                

                
~
:式``1 + 2 * 3``の場合|``*``よりも''優先順位が低い''``+``を中心にして部分式に分ける。 (「部分式``1 + 2``演算子``*``部分式``3``」ではなく「部分式``1``演算子``+``部分式``2 * 3``」として分ける)
最後に、``A*B``は``*``を中心に``A``と``B``に分割されるので、
~
:式``1 - 2 + 3``の場合|``-``よりも''右側にある''``+``を中心にして部分式に分ける。 (「部分式``1``演算子``-``部分式``2 + 3``」ではなく「部分式``1 - 2``演算子``+``部分式``3``」として分ける)
#image(5.png,nopopup,A*BとC)
+

                  
+
以上3つのルールで式を二分木に変換する手順が定まりました。
+

                  
+
#remarks
+
演算子の''優先順位の高い''順に''左側''から計算するという''計算時のルール''とは逆になっているように見える点については、計算の優先順位を括弧で表した際、式``1 + 2 * 3``は``(1 + 2) * 3``ではなく``1 + (2 * 3)``であり、式``1 - 2 + 3``は``1 - (2 + 3)``ではなく``(1 - 2) + 3``であることを考えると、本質的には同義であることがわかると思います。 異なるのは、''先に''計算すべき''部分式''を選ぶか、''後で''計算すべき''演算子''を選ぶか、という違いです。
+
#remarks-end
+

                  
+

                  
+
#remarks
+
式中に括弧``(`` ``)``を含む場合については、ここでは簡単化のために省略しています。 括弧を含む場合を考慮するなら、「括弧の中にある演算子は、他の演算子よりも優先度が高いものとする」といったルールを加えることになります。 なお、[[#Implementation_C]]で掲載しているプログラムでは、こういった定義に従い括弧を含む式を扱うようにしています。
+
#remarks-end
 

                

                
~

                  
となり、これで式``X=A*B+C``は二分木へと変換されました。
+

                  
+
***変換手順の適用 [#Algorithm_ParseExpression_Application]
+

                  
+
ここまでで定めてきた[[ルール>#Algorithm_ParseExpression_Definition]]に従って、式``x = 1 - 2 + 3``を二分木に変換する場合について1ステップずつ見ていきます。
+
#figure-svg(title=式「x = 1 - 2 + 3」の二分木(1),title=式を分割する前の状態,source=algorithm-parseexpression-tree3-0.svg,fallback-image=algorithm-parseexpression-tree3-0.png)
+

                  
+
まず、この式において最も右側にあり優先順位が低い演算子は``=``です。 これを中心に、左の部分式``x``と右の部分式``1 - 2 + 3``に分け、左右の子ノードにします。 元になったノードは演算子``=``のみのノードにします。
+
#figure-svg(title=式「x = 1 - 2 + 3」の二分木(2),title=式全体を部分式「x」と部分式「1 - 2 + 3」に分割,source=algorithm-parseexpression-tree3-1.svg,fallback-image=algorithm-parseexpression-tree3-1.png)
+

                  
+
つぎに、右の子ノードに分けられた部分式``1 - 2 + 3``は演算子を含むため、これをさらに二分木に変換します。 この部分式において最も右側にあり優先順位が低い演算子は``+``です。 これを中心に、左の部分式``1 - 2``と右の部分式``3``に分け、左右の子ノードにします。 元になったノードは演算子``+``のみのノードにします。
+
#figure-svg(title=式「x = 1 - 2 + 3」の二分木(3),title=部分式「1 - 2 + 3」を「1 - 2」と「3」に分割,source=algorithm-parseexpression-tree3-2.svg,fallback-image=algorithm-parseexpression-tree3-2.png)
+

                  
+
最後に、左の子ノードに分けられた部分式``1 - 2``も同じように二分木に変換します。 元になったノードは演算子``-``のノードにし、左の部分式``1``と右の部分式``2``に分け、左右の子ノードにします。
+

                  
+
#figure-svg(title=式「x = 1 - 2 + 3」の二分木(4),title=部分式「1 - 2」を「1」と「2」に分割,source=algorithm-parseexpression-tree3-3.svg,fallback-image=algorithm-parseexpression-tree3-3.png)
+

                  
+
これですべての部分式は演算子を含まない''項''となったため、二分木への変換手順は完了となり、式``x = 1 - 2 + 3``全体が二分木へと変換されました。
 

                

                
 

                

                
 

                

                
 
**二分木から逆ポーランド記法化した数式を得る [#Algorithm_TraverseBinaryTree]
**二分木から逆ポーランド記法化した数式を得る [#Algorithm_TraverseBinaryTree]
~
ここまでの手順で式を二分木にすることができました。 しかし、なぜ二分木にするのかという点については理由を明らかにしていませんでした。 式を二分木にした理由は、二分木からデータを読み出す順序を定義すると簡単に逆ポーランド記法化した式が得られるためです。 ここではその点について詳しく見ていきます。
ここまでの手順で式を二分木にすることができました。 しかし、なぜ二分木にするのかという点については理由を明らかにしていませんでした。 式を二分木にした理由は、二分木からデータを読み出す順序を定義すると簡単に逆ポーランド記法化した式が得られるためです。
 

                

                
+
***二分木からデータを読み出す順序 [#Algorithm_TraverseBinaryTree_TraversalOrder]
 
まず、二分木からデータを読み出す方法には次の三種類があります。 ノードを巡回(''traverse'')してデータを読み出す順序によって、木から得られるデータの順番も変わってきます。 三種類の巡回順序はそれぞれ次のとおりです。
まず、二分木からデータを読み出す方法には次の三種類があります。 ノードを巡回(''traverse'')してデータを読み出す順序によって、木から得られるデータの順番も変わってきます。 三種類の巡回順序はそれぞれ次のとおりです。
 

                

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

                

                
~
言葉での表現では分かりにくいかと思いますが、上記の手順を擬似コードと図で表すと次のようになります。
言葉での表現では分かりにくいかと思いますが、上記の手順を図に表すと次のようになります。
+

                  
+
#commentout(no-comment-node){{{
+
#html{{
+
<div>
+
  <div id="_tree-preorder"/>
+
  <div id="_tree-inorder"/>
+
  <div id="_tree-postorder"/>
+
<script>//<![CDATA[
+
let root = new ExpressionTreeNode(
+
  "N",
+
  new Node("L"),
+
  new Node("R"),
+
);
+

                  
+
let tree = root.createVisualTree();
+

                  
+
let targetPreorder = document.getElementById("_tree-preorder").appendChild(VisualTreeNode.createSvgElement());
+
tree.render(targetPreorder);
+
tree.traversePathPreorder(new TraversalOrderRenderer(targetPreorder, null));
+
Svg.minimizeElement(targetPreorder, 5);
+

                  
+
let targetInorder = document.getElementById("_tree-inorder").appendChild(VisualTreeNode.createSvgElement());
+
tree.render(targetInorder);
+
tree.traversePathInorder(new TraversalOrderRenderer(targetInorder, null));
+
Svg.minimizeElement(targetInorder, 5);
+

                  
+
let targetPostorder = document.getElementById("_tree-postorder").appendChild(VisualTreeNode.createSvgElement());
+
tree.render(targetPostorder);
+
tree.traversePathPostorder(new TraversalOrderRenderer(targetPostorder, null));
+
Svg.minimizeElement(targetPostorder, 5);
+
//]]></script>
+
</div>
+
}}
+
}}}
+

                  
+
#column
+
#code(c,先行順序訪問の擬似コード,no-code-commands){{
+
traverse(N)
+
{
+
  read(N);
+

                  
+
  if (N.L)
+
    traverse(N.L);
+

                  
+
  if (N.R)
+
    traverse(N.R);
+

                  
+
  return;
+
}
+
}}
+
#figure-svg(title=先行順序訪問,title=行きがけ順でのノードの参照順序,source=algorithm-traversebinarytree-preordertraversal.svg,fallback-image=algorithm-traversebinarytree-preordertraversal.gif)
+

                  
+
#column
+
#code(c,中間順序訪問の擬似コード,no-code-commands){{
+
traverse(N)
+
{
+
  if (N.L)
+
    traverse(N.L);
+

                  
+
  read(N);
+

                  
+
  if (N.R)
+
    traverse(N.R);
+

                  
+
  return;
+
}
+
}}
+
#figure-svg(title=中間順序訪問,title=通りがけ順でのノードの参照順序,source=algorithm-traversebinarytree-inordertraversal.svg,fallback-image=algorithm-traversebinarytree-inordertraversal.gif)
+

                  
+
#column
+
#code(c,後行順序訪問の擬似コード,no-code-commands){{
+
traverse(N)
+
{
+
  if (N.L)
+
    traverse(N.L);
+

                  
+
  if (N.R)
+
    traverse(N.R);
+

                  
+
  read(N);
+

                  
+
  return;
+
}
+
}}
+
#figure-svg(title=後行順序訪問,title=帰りがけ順でのノードの参照順序,source=algorithm-traversebinarytree-postordertraversal.svg,fallback-image=algorithm-traversebinarytree-postordertraversal.gif)
 

                

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

                

                
-
どの巡回順序でも、''一筆書きの要領''で木を左からなぞって巡回するところは共通していますが、ノードのデータを読むタイミングは異なります。 行きがけ順では''ノードに到達したとき''、通りがけ順では左の子ノードの巡回が終わって''右の子ノードに移動するとき''、帰りがけ順では右の子ノードの''巡回が終わったとき''にノードのデータを読むようにします。
 

                

                
~
どの巡回順序でも、''一筆書きの要領''で木を左からなぞるようにすべてのノードを巡回するところは共通していますが、巡回したノードのデータを読むタイミングが異なります。 ノードから''データを読むタイミング''のみに着目して比較すると、それぞれ次のようになります。
つまり、行きがけ順ではN→L→R、通りがけ順ではL→N→R、帰りがけ順ではL→R→Nの順でデータが読み出されることになります。 個々のノードがさらに子ノードを持つ場合も、同じ手順で巡回します。
 

                

                
~
:行きがけ順|左右の子ノードの巡回を''始める前''
さて、先ほどの式``X=A*B+C``から作った二分木に対して、上記の3つの順序を当てはめて巡回しデータを読み出してみます。
+
:通りがけ順|左右の子ノードの巡回の''途中''(左の子ノードの巡回が終わった後、かつ、右の子ノードの巡回を始める前)
+
:帰りがけ順|左右の子ノードの巡回が''終わった後''
 

                

                
~
このような順序でそれぞれデータを読むと、上図のように異なった順序でデータが読み出されます。 つまり、行きがけ順では``N``→``L``→``R``、通りがけ順では``L``→``N``→``R``、帰りがけ順では``L``→``R``→``N``の順でデータが読み出されることになります。
#image(7.png,nopopup,X=A*B+C)
 

                

                
~
***式の二分木への適用 [#Algorithm_TraverseBinaryTree_Application]
行きがけ順では```=X+*ABC```、通りがけ順では```X=A*B+C```、帰りがけ順では```XAB*C+=```のように読み出されます。 帰りがけ順では、ここでの目的である逆ポーランド化された式が読み出されています。 また、通りがけ順では、我々が一般的に使っている中置記法での式が読み出されています。
+
では、これを式から変換した二分木にあてはめた場合を考えてみます。 ここでは式``A + B``を例にとってみていきます。 この式の二分木に対して[[先の3つの順序>#Algorithm_TraverseBinaryTree_TraversalOrder]]でノードのデータを読み出していくと次のようになります。
 

                

                
~
#commentout(no-comment-node){{{
このように、式を二分木に変換し、その二分木から帰りがけ順で読み出すことにより、逆ポーランド記法化した式を得ることができます。
+
#html{{
+
<div>
+
  <div id="_tree-preorder"/>
+
  <div id="_tree-inorder"/>
+
  <div id="_tree-postorder"/>
+
<script>//<![CDATA[
+
let root = new ExpressionTreeNode(
+
  "+",
+
  new Node("A"),
+
  new Node("B"),
+
);
+

                  
+
let tree = root.createVisualTree();
+

                  
+
let targetPreorder = document.getElementById("_tree-preorder").appendChild(VisualTreeNode.createSvgElement());
+
tree.render(targetPreorder);
+
tree.traversePathPreorder(new TraversalOrderRenderer(targetPreorder, null));
+
Svg.minimizeElement(targetPreorder, 5);
+

                  
+
let targetInorder = document.getElementById("_tree-inorder").appendChild(VisualTreeNode.createSvgElement());
+
tree.render(targetInorder);
+
tree.traversePathInorder(new TraversalOrderRenderer(targetInorder, null));
+
Svg.minimizeElement(targetInorder, 5);
+

                  
+
let targetPostorder = document.getElementById("_tree-postorder").appendChild(VisualTreeNode.createSvgElement());
+
tree.render(targetPostorder);
+
tree.traversePathPostorder(new TraversalOrderRenderer(targetPostorder, null));
+
Svg.minimizeElement(targetPostorder, 5);
+
//]]></script>
+
</div>
+
}}
+
}}}
+

                  
+
#figure-svg(title=行きがけ順での式の二分木の読み出し,source=algorithm-traversebinarytree-exp1-preordertraversal.svg,fallback-image=algorithm-traversebinarytree-exp1-preordertraversal.gif)
+
#figure-svg(title=通りがけ順での式の二分木の読み出し,source=algorithm-traversebinarytree-exp1-inordertraversal.svg,fallback-image=algorithm-traversebinarytree-exp1-inordertraversal.gif)
+
#figure-svg(title=帰りがけ順での式の二分木の読み出し,source=algorithm-traversebinarytree-exp1-postordertraversal.svg,fallback-image=algorithm-traversebinarytree-exp1-postordertraversal.gif)
+

                  
+
行きがけ順では``+``→``A``→``B``の順、つまり``+ A B``となりポーランド記法(前置記法)に、通りがけ順では``A``→``+``→``B``の順、つまり``A + B``となり中置記法に、帰りがけ順では``A``→``B``→``+``の順、つまり``A B +``となり逆ポーランド記法(後置記法)に、それぞれ読み出されることになります。
+

                  
+
このように、二分木化した式から''行きがけ/順通りがけ順/帰りがけ順''の各順序でノードを読み出していくと、それぞれ''ポーランド記法/中置記法/逆ポーランド記法''となった式が得られることになります。 逆ポーランド記法化した数式を得るために式を二分木に変換した目的は、これがその理由となります。
+

                  
+

                  
+

                  
+
さて、これで逆ポーランド記法化した数式を得る手順が整いました。 先ほどの式``x = 1 - 2 + 3``から[[変換した二分木>#Algorithm_ParseExpression_Application]]に対して、3つの順序を当てはめて巡回し、各記法に変換した数式を得てみます。
+

                  
+
#commentout(no-comment-node){{{
+
#html{{
+
<div>
+
  <div id="_tree-preorder"/>
+
  <div id="_tree-inorder"/>
+
  <div id="_tree-postorder"/>
+
<script>//<![CDATA[
+
let root = new ExpressionTreeNode(
+
  "=",
+
  new Node("x"),
+
  new ExpressionTreeNode(
+
    "+",
+
    new ExpressionTreeNode(
+
      "-",
+
      new Node("1"),
+
      new Node("2"),
+
    ),
+
    new Node("3"),
+
  ),
+
);
+

                  
+
let tree = root.createVisualTree();
+

                  
+
let targetPreorder = document.getElementById("_tree-preorder").appendChild(VisualTreeNode.createSvgElement());
+
tree.render(targetPreorder);
+
tree.traversePathPreorder(new TraversalOrderRenderer(targetPreorder, null));
+
Svg.minimizeElement(targetPreorder, 5);
+

                  
+
let targetInorder = document.getElementById("_tree-inorder").appendChild(VisualTreeNode.createSvgElement());
+
tree.render(targetInorder);
+
tree.traversePathInorder(new TraversalOrderRenderer(targetInorder, null));
+
Svg.minimizeElement(targetInorder, 5);
+

                  
+
let targetPostorder = document.getElementById("_tree-postorder").appendChild(VisualTreeNode.createSvgElement());
+
tree.render(targetPostorder);
+
tree.traversePathPostorder(new TraversalOrderRenderer(targetPostorder, null));
+
Svg.minimizeElement(targetPostorder, 5);
+
//]]></script>
+
</div>
+
}}
+
}}}
+

                  
+
#figure-svg(title=行きがけ順での式の二分木の読み出し,source=algorithm-traversebinarytree-exp2-preordertraversal.svg)
+
#figure-svg(title=通りがけ順での式の二分木の読み出し,source=algorithm-traversebinarytree-exp2-inordertraversal.svg)
+
#figure-svg(title=帰りがけ順での式の二分木の読み出し,source=algorithm-traversebinarytree-exp2-postordertraversal.svg)
+

                  
+
行きがけ順では```= x + - 1 2 3```、通りがけ順では```x = 1 - 2 + 3```、帰りがけ順では```x 1 2 - 3 + =```のように読み出されます。
+

                  
+
このように、式を''二分木に変換''し、その''二分木から帰りがけ順で読み出す''ことにより、''逆ポーランド記法化''した式を得ることができます。 また、ノードの巡回順序を変えるだけで異なる記法での式を得られることから、数式をポーランド記法⇆中置記法⇆逆ポーランド記法へと相互に''記法変換''するように応用することもできます。 さらにこの後で述べるように、与えられた[[数式を計算する>#Algorithm_CalculateExpressionTree]]ことにも応用することができます。
 

                

                
 

                

                
 

                

                
 
**二分木化した数式を使って計算を行う [#Algorithm_CalculateExpressionTree]
**二分木化した数式を使って計算を行う [#Algorithm_CalculateExpressionTree]
 
ここまででは、式から作成した二分木を巡回することで式を様々な記法に変換する方法について解説してきました。 ここからは作成した二分木を使って式の計算を行う方法を考えていきます。
ここまででは、式から作成した二分木を巡回することで式を様々な記法に変換する方法について解説してきました。 ここからは作成した二分木を使って式の計算を行う方法を考えていきます。
 

                

                
~
ここでは、等号``=``や変数(記号)を含む場合については考えず、簡単化のため定数(数字)と四則演算子のみを含む式の計算を行う方法を考えます。 以下、計算する式として``2 + 5 * 3 - 4``を例にとり、最終的な計算結果として```13```を得るための方法を考えていきます。
ここでは、等号``=``や変数(記号)を含む場合については考えず、簡単化のため定数(数字)と四則演算子のみを含む式の計算を行う方法を考えます。 以下、計算する式として``2+5*3-4``を例にとり、最終的な計算結果として```13```を得るための方法を考えていきます。
 

                

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

                

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

                

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

                

                
~
#commentout(no-comment-node){{{
#image(8-1.png,nopopup,二分木化した式「2+5*3-4」)
+
#html{{
+
<div>
+
  <div id="_tree-calculation-initial"/>
+
  <div id="_tree-calculation-step1"/>
+
  <div id="_tree-calculation-step2"/>
+
  <div id="_tree-calculation-step3"/>
+
  <div id="_tree-calculation-transition"/>
+
<script>//<![CDATA[
+
let root = new ExpressionTreeNode("2 + 5 * 3 - 4".replace(/\s+/g, ''));
+

                  
+
root.parse();
+

                  
+
let c0 = document.getElementById("_tree-calculation-initial");
+
root.createVisualTree().render(c0.appendChild(VisualTreeNode.createSvgElement()), true);
+
Svg.minimizeElement(c0.firstChild, 5);
+

                  
+
let c1 = document.getElementById("_tree-calculation-step1");
+
root.createVisualTree().calculate(new CalculationTransitionRenderer(c1.appendChild(VisualTreeNode.createSvgElement()), [0, 1]));
+
Svg.minimizeElement(c1.firstChild, 5);
+

                  
+
let c2 = document.getElementById("_tree-calculation-step2");
+
root.createVisualTree().calculate(new CalculationTransitionRenderer(c2.appendChild(VisualTreeNode.createSvgElement()), [1, 2]));
+
Svg.minimizeElement(c2.firstChild, 5);
+

                  
+
let c3 = document.getElementById("_tree-calculation-step3");
+
root.createVisualTree().calculate(new CalculationTransitionRenderer(c3.appendChild(VisualTreeNode.createSvgElement()), [2, 3]));
+
Svg.minimizeElement(c3.firstChild, 5);
+

                  
+
let ct = document.getElementById("_tree-calculation-transition");
+
root.createVisualTree().calculate(new CalculationTransitionRenderer(ct.appendChild(VisualTreeNode.createSvgElement())));
+
Svg.minimizeElement(ct.firstChild, 5);
+

                  
+
//]]></script>
+
</div>
+
}}
+
}}}
+

                  
+
#figure-svg(title=二分木化した式「2 + 5 * 3 - 4」,source=algorithm-calculateexpressiontree-initial.svg,fallback-image=algorithm-calculateexpressiontree-initial.png)
 

                

                
 
二分木化した式では、すでに左項・右項と演算子のみに分割された状態になっています。 この二分木の末端部分から順に値を求めていけば、最終的に木全体の値、すなわち式の計算結果を得ることができます。 つまり手順としては、
二分木化した式では、すでに左項・右項と演算子のみに分割された状態になっています。 この二分木の末端部分から順に値を求めていけば、最終的に木全体の値、すなわち式の計算結果を得ることができます。 つまり手順としては、
 

                

                
 
+二分木を根(root)から順に巡回し
+二分木を根(root)から順に巡回し
 
+ノードに設定されている演算子に従って左の子ノード(部分式の左項)と右の子ノード(部分式の右項)の値を演算する
+ノードに設定されている演算子に従って左の子ノード(部分式の左項)と右の子ノード(部分式の右項)の値を演算する
~
+このとき、左または右の子ノードがさらに部分木を持っている(子ノードがある)場合は、項が値そのものではなく未計算の部分式であるため、先に2の操作を繰り返して子ノードの値(部分式の演算結果)を求める
+このとき、左または右の子ノードがさらに子ノードを持っている場合(項が値そのものではなく未計算の部分式の場合)は、先に2の操作を繰り返して子ノードの値(部分式の演算結果)を求める
 

                

                
 
という操作を行うことにより、計算結果を得ることができます。
という操作を行うことにより、計算結果を得ることができます。
 

                

                
~
まず、二分木の根を見ると、演算子は``-``、左項は部分木を持っているため部分式、右項は値``4``となっています。 左の部分木(部分式``2 + 5 * 3``にあたる部分)も、さらに右側に部分木(部分式``5 * 3``にあたる部分)を持っているため、まずはこのノードの値を求めます。
この操作を、式``2+5*3-4``の二分木に対して行なっていくと次のようになります。
+

                  
+
#figure-svg(title=二分木化した式「2 + 5 * 3 - 4」の計算,title=計算開始前の状態,source=algorithm-calculateexpressiontree-initial.svg,fallback-image=algorithm-calculateexpressiontree-initial.png)
+

                  
+
このノードは左項が値``5``、右項が値``3``、演算子が``*``であるため、このノードは演算結果として値``15``を持つことになります。
+

                  
+
#figure-svg(title=二分木化した式「2 + 5 * 3 - 4」の計算,title=過程1,source=algorithm-calculateexpressiontree-step1.svg,fallback-image=algorithm-calculateexpressiontree-step1-1.png,fallback-image=algorithm-calculateexpressiontree-step1-2.png)
 

                

                
~
ノードの値が求まったことにより、上位の部分木の値を求めることができるようになったので、演算を続けます。 このノードは左項は値``2``、右項は先の演算によって得られた値``15``、演算子は``+``であるため、このノードは演算結果として値``17``を持つことになります。
#image(8-2.png,nopopup,二分木化した式の計算 step1)
 

                

                
~
#figure-svg(title=二分木化した式「2 + 5 * 3 - 4」の計算,title=過程2,source=algorithm-calculateexpressiontree-step2.svg,fallback-image=algorithm-calculateexpressiontree-step2-1.png,fallback-image=algorithm-calculateexpressiontree-step2-2.png)
まず、二分木の根を見ると、式は演算子が``+``で左項は値``2``、右項は子ノードを持っているため部分式となります。 この部分式``5*3-4``にあたる部分木も、左項に部分式``5*3``の子ノードを含んでいるため、まずは部分式``5*3``にあたるノードの値を求めます。 このノードは左項が値``5``、右項が値``3``、演算子が``*``であるため、このノードは演算結果として値``15``を持つことになります。
 

                

                
~
最終的に、根のノードの左項と右項の値が求まったため、このノードの値を演算した結果、すなわち値``13``が式``2 + 5 * 3 - 4``の計算結果となります。
#image(8-3.png,nopopup,二分木化した式の計算 step2)
 

                

                
~
#figure-svg(title=二分木化した式「2 + 5 * 3 - 4」の計算,title=過程3,source=algorithm-calculateexpressiontree-step3.svg,fallback-image=algorithm-calculateexpressiontree-step3-1.png,fallback-image=algorithm-calculateexpressiontree-step3-2.png)
部分式のノードの値が求まったことにより、上位の部分式の値を求めることができるようになったので、演算を続けます。 このノードは、左項が先の演算によって得られた値``15``、右項が値``4``、演算子は``-``であるため、このノードは演算結果として値``11``を持つことになります。
 

                

                
~
このように、式を演算子と項に分割した二分木へと変換し、個々のノードの値を再帰的に演算していくことにより、式の計算を行うことができます。
#image(8-4.png,nopopup,二分木化した式の計算 step3)
 

                

                
~
#figure-svg(title=二分木化した式「2 + 5 * 3 - 4」の計算過程,source=algorithm-calculateexpressiontree-transition.svg,fallback-image=algorithm-calculateexpressiontree-transition.gif)
最終的に、根のノードの左項と右項の値が求まったため、このノードの値を演算した結果、すなわち値``13``が式``2+5*3-4``の計算結果となります。 このように、式を演算子と項に分割した二分木へと変換し、個々のノードの値を再帰的に演算していくことにより、式の計算を行うことができます。
 

                

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

                

                
+

                  
+

                  
 
*Cでの実装 [#Implementation_C]
*Cでの実装 [#Implementation_C]
 
以下で紹介するのはC言語での実装です。 [[このプログラム>#Implementation_C_Complete]]は、ここまでで解説してきた[[アルゴリズム>#Algorithm]]を用いて数式の二分木化と各記法での表示、計算を行うものです。
以下で紹介するのはC言語での実装です。 [[このプログラム>#Implementation_C_Complete]]は、ここまでで解説してきた[[アルゴリズム>#Algorithm]]を用いて数式の二分木化と各記法での表示、計算を行うものです。
 

                

                
661,13 335,17
 

                

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

                

                
-
#remarks
-
このプログラムではアルゴリズムの理解を目的としたわかりやすさ・読みやすさを優先しているため、速度の面で劣る実装となっている部分があります。 また、実装が冗長となっている箇所もあります。 そういった部分について、[[http://smdn.jp/misc/forum/programming/#entry48]]にてご意見を頂いています。 プログラムを改良する場合にはご参照ください。
-
#remarks-end
-

                  
 
**データ構造とプログラムの概略 [#Implementation_C_Summary]
**データ構造とプログラムの概略 [#Implementation_C_Summary]
 
まずは二分木を表現するための``Node``型と、``main``関数でのプログラム全体の流れを見ていきます。 (プログラム全文は[[#Implementation_C_Complete]]を参照してください。)
まずは二分木を表現するための``Node``型と、``main``関数でのプログラム全体の流れを見ていきます。 (プログラム全文は[[#Implementation_C_Complete]]を参照してください。)
 

                

                
 
***データ構造 [#Implementation_C_Summary_Node]
***データ構造 [#Implementation_C_Summary_Node]
 
二分木を表現するためのデータ構造は、``Node``型として次のように実装します。
二分木を表現するためのデータ構造は、``Node``型として次のように実装します。
 

                

                
~
#code(source=_source/polish.c,source-line-from=7,source-line-to=30,title=Node型,license=mit,copyrightyear=2017)
#code(source=_source/polish.c,source-line-from=6,source-line-to=29,title=Node型,license=mit,copyrightyear=2017)
 

                

                
 
``Node``型は次の3つの値を保持します。
``Node``型は次の3つの値を保持します。
 
:``left``|左の子ノード(部分木)へのポインタ
:``left``|左の子ノード(部分木)へのポインタ
689,15 367,13
 
int calculate(Node* node);
int calculate(Node* node);
 
}}
}}
 

                

                
~
#code(source=_source/polish.c,source-line-from=309,title=main関数と前処理のための関数,license=mit,copyrightyear=2017)
#code(source=_source/polish.c,source-line-from=304,title=main関数,license=mit,copyrightyear=2017)
 

                

                
 
``main``関数の流れは、
``main``関数の流れは、
 
+分割前の式全体を格納しておくため二分木の根、``root``を作成
+分割前の式全体を格納しておくため二分木の根、``root``を作成
 
+入力された式を``root->exp``に格納
+入力された式を``root->exp``に格納
~
+二分木への変換の前準備として、
+二分木への変換の前準備として、邪魔になる空白を削除(``remove_space``)
~
++式中から邪魔になる空白を削除(``remove_space``)
+[[式を二分木に分割>#Implementation_C_ParseExpression]]する(``parse_expression``)
+
++式中の括弧が正しく対応しているかを検証(``validate_bracket_balance``)
+
+[[式を二分木に分割>#Implementation_C_ParseExpression]](``parse_expression``)
 
+分割した二分木を
+分割した二分木を
 
++帰りがけ順で[[巡回して表示する>#Implementation_C_TraverseBinaryTree]](``traverse_postorder``)
++帰りがけ順で[[巡回して表示する>#Implementation_C_TraverseBinaryTree]](``traverse_postorder``)
 
++通りがけ順で巡回して表示する(``traverse_inorder``)
++通りがけ順で巡回して表示する(``traverse_inorder``)
710,22 386,22
 
**二分木への分割 [#Implementation_C_ParseExpression]
**二分木への分割 [#Implementation_C_ParseExpression]
 
次に、入力された式から二分木への分割を行う部分の関数``parse_expression``を見ていきます。 この関数は、二分木への分割に際して、式の最も外側にある丸括弧を削除する関数``remove_outer_most_bracket``、および、式中の演算子の位置を取得する関数``get_pos_operator``を呼び出します。
次に、入力された式から二分木への分割を行う部分の関数``parse_expression``を見ていきます。 この関数は、二分木への分割に際して、式の最も外側にある丸括弧を削除する関数``remove_outer_most_bracket``、および、式中の演算子の位置を取得する関数``get_pos_operator``を呼び出します。
 

                

                
~
#code(source=_source/polish.c,source-line-from=32,source-line-to=201,title=二分木への分割を行う関数群,license=mit,copyrightyear=2017)
#code(source=_source/polish.c,source-line-from=31,source-line-to=206,title=二分木への分割を行う関数群,license=mit,copyrightyear=2017)
 

                

                
 
``parse_expression``の流れを簡単に説明すると、
``parse_expression``の流れを簡単に説明すると、
 
+まず、``remove_outer_most_bracket``で分割する部分式に含まれる、最も外側の丸括弧を削除する (例:``(1+2)``を``1+2``にする)
+まず、``remove_outer_most_bracket``で分割する部分式に含まれる、最も外側の丸括弧を削除する (例:``(1+2)``を``1+2``にする)
~
++空の括弧の場合は、不正な式と判断して処理を終える (例:``node->exp``が``()``の場合)
++丸括弧の数が一致しない場合などは、不正な式と判断して処理を終える (例:``node->exp``が``(1+2``などの場合)
~
+次に、``get_pos_operator``で最も右側にあり、かつ優先順位の低い演算子の位置を取得する
+次に、``get_pos_operator``で最も優先順位の低い演算子の位置を取得する
-
++演算子が式の先頭または末尾にあった場合は、不正な式と判断して処理を終える (例:``node->exp``が``1-``、``+1``などの場合)
 
++演算子がなかった場合は、二分木への分割が完了したとして処理を終える (例:``node->exp``が``1``、``2``などの場合)
++演算子がなかった場合は、二分木への分割が完了したとして処理を終える (例:``node->exp``が``1``、``2``などの場合)
+
++演算子が式の先頭または末尾にあった場合は、不正な式と判断して処理を終える (例:``node->exp``が``1-``、``+1``などの場合)
 
++演算子があった場合は、その演算子を中心として左右の部分式へ分割する
++演算子があった場合は、その演算子を中心として左右の部分式へ分割する
 
+++``node->left``および``node->right``に新しくノードを作成(``create_node``)して代入する
+++``node->left``および``node->right``に新しくノードを作成(``create_node``)して代入する
~
+++``node->exp``から、左右それぞれの部分式にあたる部分を``node->left->exp``および``node->right->exp``にコピーしたのち、``node->exp``に演算子のみを残す
+++``node->exp``から、左右それぞれの部分式にあたる部分を``node->left->exp``および``node->right->exp``にコピーする
 
+++``node->left``および``node->right``に対して``parse_expression``を呼び出すことで、左右それぞれの部分式を再帰的に分割していく
+++``node->left``および``node->right``に対して``parse_expression``を呼び出すことで、左右それぞれの部分式を再帰的に分割していく
 

                

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

                

                
~
ここで``get_pos_operator``は、部分式のうち、''丸括弧``( )``で括られていない部分''で、''最も右側''にあり、かつ''最も優先順位の低い''演算子の位置を返します。 例えば式``1*(2+3)``の場合は、``*``の位置が分割すべき位置として判断されます。 なお、演算子の優先順位は低い方から次の順で定義しています。
ここで``get_pos_operator``は、部分式のうち、''丸括弧``( )``で括られていない部分''で、かつ''最も優先順位の低い''演算子の位置を返します。 例えば式``1*(2+3)``の場合は、``*``の位置が分割すべき位置として判断されます。 なお、演算子の優先順位は次の順で定義しています。
 
+``=``
+``=``
 
+``+``および``-``
+``+``および``-``
 
+``*``および``/``
+``*``および``/``
735,16 411,14
 
**二分木の巡回 [#Implementation_C_TraverseBinaryTree]
**二分木の巡回 [#Implementation_C_TraverseBinaryTree]
 
続いて、二分木の巡回を行う関数``traverse_postorder``, ``traverse_inorder``, ``traverse_preorder``を見ていきます。
続いて、二分木の巡回を行う関数``traverse_postorder``, ``traverse_inorder``, ``traverse_preorder``を見ていきます。
 

                

                
~
#code(source=_source/polish.c,source-line-from=203,source-line-to=263,title=二分木の巡回を行う関数群,license=mit,copyrightyear=2017)
#code(source=_source/polish.c,source-line-from=208,source-line-to=258,title=二分木の巡回を行う関数群,license=mit,copyrightyear=2017)
+

                  
+
それぞれ``traverse_postorder``が帰りがけ順、``traverse_inorder``が通りがけ順、``traverse_preorder``が行きがけ順で巡回する関数です。 各関数とも、与えられたノード``node``に対して、ノードの持つ値(``node->exp``)の表示を行い、子ノード(``node->left``, ``node->right``)がある場合は再帰的に巡回します。 値の表示と再帰呼出しの順序を変えることで、ノードの巡回順序も変わることに注目してください。
 

                

                
~
なお、これらの関数では結果のわかりやすさのために、各ノードの値の間に空白を補って表示します。 また``traverse_inorder``では丸括弧も補って表示しています。
それぞれ``traverse_postorder``が帰りがけ順、``traverse_inorder``が通りがけ順、``traverse_preorder``が行きがけ順で巡回する関数です。 各関数とも、与えられたノード``node``に対して、ノードの持つ値(``node->exp``)の表示を行い、子ノード(``node->left``, ``node->right``)がある場合は再帰的に巡回します。 値の表示と再帰呼出しの順序を変えることで、ノードの巡回順序も変わることに注目してください。 なお、``traverse_inorder``では結果のわかりやすさのために丸括弧を補って表示しています。
 

                

                
 
**二分木からの値の演算 [#Implementation_C_CalculateExpressionTree]
**二分木からの値の演算 [#Implementation_C_CalculateExpressionTree]
 
続いて、二分木から値の演算を行う関数``calculate``を見ていきます。
続いて、二分木から値の演算を行う関数``calculate``を見ていきます。
 

                

                
~
#code(source=_source/polish.c,source-line-from=265,source-line-to=307,title=二分木から値の演算を行う関数,license=mit,copyrightyear=2017)
#code(source=_source/polish.c,source-line-from=260,source-line-to=302,title=二分木から値の演算を行う関数,license=mit,copyrightyear=2017)
 

                

                
 
``calculate``関数では、引数で与えられたノードについて、
``calculate``関数では、引数で与えられたノードについて、
 
+左右の両方に子ノードを持たない場合
+左右の両方に子ノードを持たない場合
776,39 450,30
 
}}
}}
 

                

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

                

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

                

                
 
#prompt(実行例3){{
#prompt(実行例3){{
~
input expression: 1.0+2/.3/(0-1)
input expression: x = 3 * 2 + 1
~
expression: 1.0+2/.3/(0-1)
expression: x=3*2+1
~
reverse polish notation: 1.0 2 .3 / 0 1 - / + 
reverse polish notation: x32*1+=
~
infix notation: (1.0 + ((2 / .3) / (0 - 1)))
infix notation: (x=((3*2)+1))
~
polish notation: + 1.0 / / 2 .3 - 0 1 
polish notation: =x+*321
~
calculated result: -5.66666666666667
calculated expression: (x=7)
+
}}
+

                  
+
#prompt(実行例4){{
+
input expression: 1 + 2 + X = Y + 3 + 4
+
expression: 1+2+X=Y+3+4
+
reverse polish notation: 1 2 + X + Y 3 + 4 + = 
+
infix notation: (((1 + 2) + X) = ((Y + 3) + 4))
+
polish notation: = + + 1 2 X + + Y 3 4 
+
calculated expression: ((3 + X) = ((Y + 3) + 4))
 
}}
}}
 

                

                
 
*他の言語での実装 [#Implementation_OtherLang]
*他の言語での実装 [#Implementation_OtherLang]
819,15 484,6
 
なお、[[最初に挙げたデモ>#ConversionDemo]]はJavaScriptで実装しています。 ソースコードについてはこのページのソースに含まれています。
なお、[[最初に挙げたデモ>#ConversionDemo]]はJavaScriptで実装しています。 ソースコードについてはこのページのソースに含まれています。
 

                

                
 
*文書情報 [#DocumentLog]
*文書情報 [#DocumentLog]
+
:2018-01-21|
+
::本文について|演算子の優先順位について「最も右側の」の記載が抜けていた点を修正し、補足説明を追記
+
図表について、[[#Implementation_C]]と差異があった箇所を修正
+
例示用の数式を同一のものに統一
+
各記法での表記において項の間に空白を入れるように変更
+
その他図表についてよりわかりやすいものとなるよう追加・変更
+
[[#ConversionDemo]]にて各記法への変換過程・数式の計算過程を確認できるようにした
+
::各言語での実装について|各記法での表記において項の間に空白を入れて出力するように変更
+
その他掲示板での指摘に基づいて改善・修正([[http://smdn.jp/misc/forum/programming/#entry48]], [[http://smdn.jp/misc/forum/programming/#entry50]])
 
:2017-12-22|
:2017-12-22|
 
::各言語での実装について|処理内容を記述したコメントを追記
::各言語での実装について|処理内容を記述したコメントを追記
 
ソースコードのライセンスを[[misc/license/MIT]]に設定
ソースコードのライセンスを[[misc/license/MIT]]に設定
852,4 508,3
 
C# 3.0, VB8, Rubyでの実装を追記
C# 3.0, VB8, Rubyでの実装を追記
 
:2009-03-21|new/deleteを用いない実装を追記
:2009-03-21|new/deleteを用いない実装を追記
 
:2003-02-08|初版公開
:2003-02-08|初版公開
+