5: 2016-07-27 (水) 23:38:31 osinko  |
現: 2016-08-04 (木) 11:20:26 osinko |
| | ***1.と2.について [#f61c996d] | | ***1.と2.について [#f61c996d] |
| | -算術演算処理（calculate）には二項演算の二分木、式木の仕組みを利用してプログラム処理する | | -算術演算処理（calculate）には二項演算の二分木、式木の仕組みを利用してプログラム処理する |
| - | -四則演算の優先順位に従って式木を組むコードを作る | + | -四則演算、括弧のネストの優先順位に従って式木を組む |
| | | | |
| | 資料： | | 資料： |
| | | | |
| | つまり①②③は四則演算の二項結合子の集合。aは0を除いた-9～9までの数。b,c,dは1～9までの数となる | | つまり①②③は四則演算の二項結合子の集合。aは0を除いた-9～9までの数。b,c,dは1～9までの数となる |
| - | ルール1.2.の処理に関しては式木で対応する事で解決する。具体例を書くと・・・ | + | ルール1.2.の処理に関しては式木で対応する事で解決する。これに関しては資料で扱ったコードを改造して利用する |
| | | | |
| | + | #code(csharp){{ |
| | + | //当コードの著作：総武ソフトウェア推進所 http://smdn.jp/ |
| | + | //ソース元 http://smdn.jp/programming/tips/polish/ |
| | + | //著作は元ソースの権利者に帰属 |
| | + | // |
| | + | //ソース元のコードで一部動かない間違いがあったので修正しています |
| | + | //理解しやすいように注釈の追加とunity用の改編を行っています |
| | | | |
| | + | using UnityEngine; |
| | + | using System.Collections; |
| | + | using System; |
| | + | |
| | + | public class Tree3 : MonoBehaviour |
| | + | { |
| | + | |
| | + | void Start() |
| | + | { |
| | + | |
| | + | //両端を括弧で閉じるのはNG（最下層の括弧は必ず省略する必要がある） |
| | + | var root = new Node("5/(3+(2*4))-3"); |
| | + | |
| | + | print(string.Format("expression: {0}", root.Expression)); |
| | + | |
| | + | root.Parse(); |
| | + | |
| | + | print("reverse polish notation: "); |
| | + | root.TraversePostorder(); |
| | + | print(""); |
| | + | |
| | + | print("infix notation: "); |
| | + | root.TraverseInorder(); |
| | + | print(""); |
| | + | |
| | + | print("polish notation: "); |
| | + | root.TraversePreorder(); |
| | + | print(""); |
| | + | |
| | + | print(string.Format("calculated result: {0}", root.Calculate())); |
| | + | } |
| | + | |
| | + | |
| | + | //自分自身のクラスの中に自分自身と同じクラス（型）を収める面白い構造をしている |
| | + | //再帰関数と絡めて型を運用するとシンプルにデーター設計できる好例となっている |
| | + | public class Node |
| | + | { |
| | + | public string Expression; |
| | + | public Node Left = null; |
| | + | public Node Right = null; |
| | + | |
| | + | public Node(string expression) |
| | + | { |
| | + | this.Expression = expression; |
| | + | } |
| | + | |
| | + | //文字列の式をNode型に式木で分解する |
| | + | public void Parse() |
| | + | { |
| | + | //分解は一番優先順位の低い演算子の位置から始まる |
| | + | var posOperator = GetOperatorPos(Expression); |
| | + | |
| | + | if (posOperator < 0) |
| | + | { |
| | + | Left = null; |
| | + | Right = null; |
| | + | return; |
| | + | } |
| | + | |
| | + | //Nodeクラスのルートと左右の葉に適切にデーターを収納する |
| | + | //左右の葉では、それぞれ解析実行して再帰処理し文字列の式を分解していく |
| | + | |
| | + | // left-hand side |
| | + | Left = new Node(RemoveBracket(this.Expression.Substring(0, posOperator))); |
| | + | Left.Parse(); |
| | + | |
| | + | // right-hand side |
| | + | Right = new Node(RemoveBracket(this.Expression.Substring(posOperator + 1))); |
| | + | Right.Parse(); |
| | + | |
| | + | // operator |
| | + | this.Expression = this.Expression.Substring(posOperator, 1); |
| | + | } |
| | + | |
| | + | //文字列の式から外側の括弧を消す処理 |
| | + | //例："((2*4)+3)"→"(2*4)+3" |
| | + | private static string RemoveBracket(string str) |
| | + | { |
| | + | //両端に括弧が無い場合、そのまま文字列を返す |
| | + | if (!(str.StartsWith("(") && str.EndsWith(")"))) |
| | + | return str; |
| | + | |
| | + | |
| | + | //括弧が組になって存在しているかエラーチェック |
| | + | var nest = 1; |
| | + | for (var i = 1; i < str.Length - 1; i++) |
| | + | { |
| | + | if (str[i] == '(') |
| | + | nest++; |
| | + | else if (str[i] == ')') |
| | + | nest--; |
| | + | |
| | + | if (nest == 0) |
| | + | return str; |
| | + | } |
| | + | if (nest != 1) |
| | + | throw new Exception(string.Format("unbalanced bracket: {0}", str)); //数が揃っていなければエラー出力 |
| | + | |
| | + | |
| | + | //文字列、先頭と末尾文字を抜いて出力 |
| | + | str = str.Substring(1, str.Length - 2); |
| | + | |
| | + | //先頭の括弧をチェックして二重以上の括弧を再帰処理する |
| | + | if (str.StartsWith("(")) |
| | + | return RemoveBracket(str); |
| | + | else |
| | + | return str; |
| | + | } |
| | + | |
| | + | //一番、低い優先順位の演算結合子の文字列位置を返す |
| | + | private static int GetOperatorPos(string expression) |
| | + | { |
| | + | if (string.IsNullOrEmpty(expression)) |
| | + | return -1; |
| | + | |
| | + | var pos = -1; |
| | + | var nest = 0; |
| | + | var priority = 0; |
| | + | var lowestPriority = 4; |
| | + | |
| | + | //文字列の左側から順に処理される |
| | + | for (var i = 0; i < expression.Length; i++) |
| | + | { |
| | + | switch (expression[i]) |
| | + | { |
| | + | case '=': priority = 1; break; |
| | + | case '+': priority = 2; break; |
| | + | case '-': priority = 2; break; |
| | + | case '*': priority = 3; break; |
| | + | case '/': priority = 3; break; |
| | + | case '(': nest++; continue; |
| | + | case ')': nest--; continue; |
| | + | default: continue; |
| | + | } |
| | + | |
| | + | //nestが0は括弧が閉じ切っている。ネストの底に位置している事を意味する |
| | + | //nestが0以上は括弧内なので記録しない。0以下はエラーを意味するのでこれも記録しない |
| | + | //左から順に右に向かって優先順位の低い結合子の位置を探す。同じ優先順位の結合子なら右にあるものほど低い |
| | + | //例："5/(3+(2*4))-3"ならば一番優先順位が低い結合子は"-"となる。左項は"5/(3+(2*4))"、右項は"3"となる |
| | + | if (nest == 0 && priority <= lowestPriority) |
| | + | { |
| | + | lowestPriority = priority; |
| | + | pos = i; |
| | + | } |
| | + | } |
| | + | |
| | + | return pos; |
| | + | } |
| | + | |
| | + | public void TraversePostorder() |
| | + | { |
| | + | if (Left != null) |
| | + | Left.TraversePostorder(); |
| | + | if (Right != null) |
| | + | Right.TraversePostorder(); |
| | + | |
| | + | print(Expression); |
| | + | } |
| | + | |
| | + | public void TraverseInorder() |
| | + | { |
| | + | if (Left != null && Right != null) |
| | + | print("("); |
| | + | |
| | + | if (Left != null) |
| | + | Left.TraverseInorder(); |
| | + | |
| | + | print(Expression); |
| | + | |
| | + | if (Right != null) |
| | + | Right.TraverseInorder(); |
| | + | |
| | + | if (Left != null && Right != null) |
| | + | print(")"); |
| | + | } |
| | + | |
| | + | public void TraversePreorder() |
| | + | { |
| | + | print(Expression); |
| | + | |
| | + | if (Left != null) |
| | + | Left.TraversePreorder(); |
| | + | if (Right != null) |
| | + | Right.TraversePreorder(); |
| | + | } |
| | + | |
| | + | //自分自身を必要回複数呼び出す再帰関数 |
| | + | //ノードは結合子に、サブツリーの末端は左右の葉がnullになることを利用して計算処理している |
| | + | public double 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.0d; |
| | + | } |
| | + | } |
| | + | else { |
| | + | return double.Parse(Expression); //両葉に何も入ってない時、ここで文字列を数字にしている |
| | + | } |
| | + | } |
| | + | } |
| | + | } |
| | + | }} |
| | | | |
| | 次にルール3.の括弧の処理を考える。例えば&font(Red){二項結合子と左右の二項を一ブロックに考え};て \(a①b\) という式があった場合、これに括弧を付けると \((a①b)\) になる。\(a①b②c\) の場合に括弧を付ける場合、 \(\left( a①\left( b②c \right) \right) \) か \(\left( \left( a①b \right) ②c \right) \) となる。このことから、二項結合子を挟んだ２項に対して左右に括弧で囲めば式を生成できる。そこで①をtrue,falseを持つフラグだと考える | | 次にルール3.の括弧の処理を考える。例えば&font(Red){二項結合子と左右の二項を一ブロックに考え};て \(a①b\) という式があった場合、これに括弧を付けると \((a①b)\) になる。\(a①b②c\) の場合に括弧を付ける場合、 \(\left( a①\left( b②c \right) \right) \) か \(\left( \left( a①b \right) ②c \right) \) となる。このことから、二項結合子を挟んだ２項に対して左右に括弧で囲めば式を生成できる。そこで①をtrue,falseを持つフラグだと考える |
| | |110|((a①b)②c)③d|(a①(b②c))③d| | | |110|((a①b)②c)③d|(a①(b②c))③d| |
| | |111|(a①(b)②(c)③d)| | | | |111|(a①(b)②(c)③d)| | |
| | + | |
| | + | 括弧の処理順を考えると000⇔111で同値となっている。これはひとつにする。従ってabcdと①②③の中身を変化させず全部で9パターンの式を作れば括弧ありの式の状態を網羅したことになる。ここで011の括弧の生成をすると |
| | + | |
| | + | 例："5/(3+(2*4))" |
| | + | |
| | + | ①=/ |
| | + | ②=+ |
| | + | ③=* |
| | + | a=5 |
| | + | b=3 |
| | + | c=2 |
| | + | d=4 |
| | + | |
| | + | 一番優先順位が低い結合子は ①=/ になる。従って式木は |
| | + | &ref(tree1.png); |
| | + | |
| | + | この一番優先順位が低い結合子を選ぶアルゴリズムは資料のGetOperatorPos関数にある |
| | + | 括弧もここでうまく処理されているので注目。もう一例 |
| | + | |
| | + | 例："(5/(3+2))*4" |
| | + | |
| | + | 一番優先順位が低い結合子は ③=* になる。従って式木は |
| | + | &ref(tree2.png); |
| | + | |
| | + | この要領で式木を生成すればいい。式木の末端程、計算優先順位は高くなるのでcalculate時は末端からトラバースして計算する |
| | + | |
| | + | **式木から数式のパターンを眺めてみる [#bafcc66b] |
| | + | |
| | + | ここで視点を変えて式木から数式のパターンを眺めてみる。よくある式の一つを眺めてみると以下のような構成となっている（見やすさを優先して横倒しにしています） |
| | + | &ref(tree3.png); |
| | + | この①～③の並びを順列と考えて置換すると |
| | + | |
| | + | ①②③ |
| | + | ①③② |
| | + | ②①③ × |
| | + | ②③① × |
| | + | ③①② |
| | + | ③②① |
| | + | |
| | + | の \(3!=3\times 2\times 1=6\) パターンで全てを網羅する事ができる。そこで、この式木を実際に組んで性質をまとめてみる。まず、以下の約束事を定義する |
| | + | |
| | + | \(①,②,③=\left\{ \times ,\div ,+,- \right\} \\ \overline { ① } ,\overline { ② } ,\overline { ③ } =\left\{ \times ,\div \right\} \\ \underline { ① } ,\underline { ② } ,\underline { ③ } =\left\{ +,- \right\} \) |
| | + | |
| | + | //\(\bullet =\left\{ \times ,\div ,+,- \right\} \\ \overline { \bullet } =\left\{ \times ,\div \right\} \\ \underline { \bullet } =\left\{ +,- \right\} \) |
| | + | |
| | + | //ここで使用している「\(\bullet \)」マークは匿名の二項結合演算子（この場合①～③）を表している。記号に上線があるものは優先順位の高い演算子の集合「×÷」。下線のあるものは優先順位の低い演算子の「＋－」。マークのみは「×÷＋－」の集合になっている。このルールに従い式木から数式を見ると以下のような分類が可能となる |
| | + | |
| | + | 二項結合演算子（この場合①～③で「×÷＋－」の集合）に上線があるものは優先順位の高い演算子の集合「×÷」。下線のあるものは優先順位の低い演算子の「＋－」の集合になっている。このルールに従い式木から数式を見ると以下のような分類が可能となる |
| | + | |
| | + | ***式木123のパターン [#n73fa719] |
| | + | \(a①\left( b②\left( c③d \right) \right) \quad \Leftrightarrow \quad 例:\quad 1\times \left( 2\times \left( 3\times 4 \right) \right) \quad \\ a\underline { ① } b\overline { ② } \left( c③d \right) \quad \Leftrightarrow \quad 例:\quad 1+2\times \left( 3\times 4 \right) \) |
| | + | &ref(tree3.png); |
| | + | ***式木132のパターン [#i00c1bc4] |
| | + | \(a\underline { ① } \left( b②c \right) \overline { ③ } d\quad \Leftrightarrow \quad 例:\quad 1+\left( 2\times 3 \right) \times 4\quad \\ a①\left( \left( b②c \right) ③d \right) \quad \Leftrightarrow \quad 例:\quad 1\times \left( \left( 2+3 \right) +4 \right) \quad \) |
| | + | &ref(tree4.png); |
| | + | ***式木312のパターン [#m65ca0f9] |
| | + | \(a\overline { ① } \left( b②c \right) \underline { ③ } d\quad \Leftrightarrow \quad 例:\quad 1\times \left( 2\times 3 \right) +4\quad \\ \left( a①\left( b②c \right) \right) ③d\quad \Leftrightarrow \quad 例:\quad \left( 1+\left( 2+3 \right) \right) \times 4\) |
| | + | &ref(tree5.png); |
| | + | ***式木321のパターン [#c8ed4a45] |
| | + | \(\left( a①b \right) \overline { ② } c\underline { ③ } d\quad \Leftrightarrow \quad 例:\quad \left( 1\times 2 \right) \times 3+4\quad \\ \left( \left( a①b \right) ②c \right) ③d\quad \Leftrightarrow \quad 例:\quad \left( \left( 1+2 \right) +3 \right) \times 4\) |
| | + | &ref(tree6.png); |
| | + | ***式木亜種のパターン [#u5b5b75a] |
| | + | \(\left( a①b \right) ②\left( c③d \right) \quad \Leftrightarrow \quad 例:\quad \left( 1+2 \right) \times \left( 3+4 \right) \\ a\overline { ① } b\underline { ② } \left( c③d \right) \quad \Leftrightarrow \quad 例:\quad 1\times 2+\left( 3\times 4 \right) \\ \left( a①b \right) \underline { ② } c\overline { ③ } d\quad \Leftrightarrow \quad 例:\quad \left( 1\times 2 \right) +3\times 4\) |
| | + | &ref(tree8.png); |
| | + | ***式木から見て②から始まるパターンは使えない [#wcd465a3] |
| | + | 式木から見て②から始まるパターンはありえない。そのことを以下で確認してみる |
| | + | &ref(tree7.png); |
| | + | これは項同士が隣り合っていない、間に邪魔な項があり演算できない。従って式木が成立しない。231のパターンも同様である |
| | + | ***括弧によるネストがない数式を式木として見てみる [#c2efe7cd] |
| | + | 次に括弧によるネストがない数式を式木として見てみると以下のように上記で紹介した各パターンに重複することがわかる |
| | + | |
| | + | \(a\overline { ① } b\overline { ② } c\overline { ③ } d\quad \Leftrightarrow \quad a\times b\times c\times d\quad \Leftrightarrow \quad 123のパターン\\ a\underline { ① } b\overline { ② } c\overline { ③ } d\quad \Leftrightarrow \quad a+b\times c\times d\quad \Leftrightarrow \quad 132のパターン\\ a\underline { ① } b\overline { ② } c\underline { ③ } d\quad \Leftrightarrow \quad a+b\times c+d\quad \Leftrightarrow \quad 312のパターン\\ a\overline { ① } b\overline { ② } c\underline { ③ } d\quad \Leftrightarrow \quad a\times b\times c+d\quad \Leftrightarrow \quad 321のパターン\\ a\overline { ① } b\underline { ② } c\underline { ③ } d\quad \Leftrightarrow \quad a\times b+c+d\quad \Leftrightarrow \quad 321のパターン\\ a\underline { ① } b\underline { ② } c\underline { ③ } d\quad \Leftrightarrow \quad a+b+c+d\quad \Leftrightarrow \quad 321のパターン\\ a\underline { ① } b\underline { ② } c\overline { ③ } d\quad \Leftrightarrow \quad a+b+c\times d\quad \Leftrightarrow \quad 亜種のパターン\\ a\overline { ① } b\underline { ② } c\overline { ③ } d\quad \Leftrightarrow \quad a\times b+c\times d\quad \Leftrightarrow \quad 亜種のパターン\) |
| | + | ***中間まとめ [#h0fc7fad] |
| | + | &font(150%){以上の事から式木の5パターンで4項の括弧を含めた四則演算の優先順位が網羅できることが確認できる&br;}; |
| | + | |
| | + | この考えが正しいかどうか。まずブルートフォースの形式で力技で率直にアプローチしたコードと、5パターンにまでシンプル化した式木を利用したコードのふたつで検証を行い、どちらの答えも同一であれば、まず間違いはないだろうと考える。コーディングはまだ早い。もう少し考えを進めてみる |
| | + | |
| | + | **群(group)の理論で、式木の置換処理を考える [#c9f619a3] |
| | + | |
| | + | 資料：[[群 (数学):https://ja.wikipedia.org/wiki/%E7%BE%A4_(%E6%95%B0%E5%AD%A6)]] |
| | + | 数学における「群」とは「似ているものをひっくるめる」理論といえる。似ているもの同士がどこが似ているかを人に説明するのは難しい。その対象が抽象的な物であればある程難しいものだと考えられる。 |
![[PukiWiki]](http://unitylabo.s601.xrea.com/xoops/modules/xpwiki/image/pukiwiki.png "[PukiWiki]")
