6: 2016-07-28 (木) 23:15:24 osinko  |
現: 2016-08-04 (木) 11:20:26 osinko |
| | ***1.と2.について [#f61c996d] | | ***1.と2.について [#f61c996d] |
| | -算術演算処理（calculate）には二項演算の二分木、式木の仕組みを利用してプログラム処理する | | -算術演算処理（calculate）には二項演算の二分木、式木の仕組みを利用してプログラム処理する |
| - | -四則演算の優先順位に従って式木を組むコードを作る | + | -四則演算、括弧のネストの優先順位に従って式木を組む |
| | | | |
| | 資料： | | 資料： |
| | //Nodeクラスのルートと左右の葉に適切にデーターを収納する | | //Nodeクラスのルートと左右の葉に適切にデーターを収納する |
| | //左右の葉では、それぞれ解析実行して再帰処理し文字列の式を分解していく | | //左右の葉では、それぞれ解析実行して再帰処理し文字列の式を分解していく |
| | + | |
| | // left-hand side | | // left-hand side |
| | Left = new Node(RemoveBracket(this.Expression.Substring(0, posOperator))); | | Left = new Node(RemoveBracket(this.Expression.Substring(0, posOperator))); |
| | d=4 | | d=4 |
| | | | |
| - | 一番優先順位が低い結合子は ①=/ になる従って式木は | + | 一番優先順位が低い結合子は ①=/ になる。従って式木は |
| | &ref(tree1.png); | | &ref(tree1.png); |
| | | | |
| | 例："(5/(3+2))*4" | | 例："(5/(3+2))*4" |
| | | | |
| - | 一番優先順位が低い結合子は ③=* になる従って式木は | + | 一番優先順位が低い結合子は ③=* になる。従って式木は |
| | &ref(tree2.png); | | &ref(tree2.png); |
| | | | |
| - | この要領で式木を生成すればいい。式木の末端程、計算優先順位は高くなるのでcalculate時は末端から計算する。ではコーディングする | + | この要領で式木を生成すればいい。式木の末端程、計算優先順位は高くなるので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]")
