式木、二項演算、括弧のネスト処理
のバックアップソース(No.9)
Unity学習帳2冊目
式木、二項演算、括弧のネスト処理
のバックアップソース(No.9)
[
トップ
] [
差分
|
バックアップ
|
リロード
] [
新規
|
一覧
|
検索
|
最新
|
ヘルプ
]
[ ]
差分
を表示
現在との差分
を表示
式木、二項演算、括弧のネスト処理
へ行く。
« Prev
Next »
TITLE:式木、二項演算、括弧のネスト処理 #jsmath **式木、二項演算、括弧のネスト処理 [#a7139d8b] ネットをぶらぶら散策していると面白い問題を見つけた。25年前に活躍していた低価格パーソナルコンピュータMSXを扱った雑誌で、その標準機能だったBASICを使って問題を解くというクイズ記事。以下のリンクにそのページが公開されている [[MSX_Magazine_1991-12_ASCII_JP:https://archive.org/stream/MSX_Magazine_1991-12_ASCII_JP#page/n93/mode/2up]] 論理や算術演算を自動生成して目的に合わせ解く問題。非常に興味深いのでこの問題を解いてみる 資料:[[MSXマガジン_バックナンバーアーカイブ:https://archive.org/details/msxmagazinejp]] ***問題 [#cf6bd2ed] 0000~9999までの4桁の数の間に四則演算を入れて10が作れないものはいくつあるか?プログラムで求めよ <ルール> ++-×÷の記号のみ使用できる事とする。ルートやべき乗は使用不可 +計算は一般の式と同じ順序で行う(×÷が優先、左から右に計算する) +()は使用できる +最初の数字の頭に-を付けて負の数にすることは出来る +数字の並べ替えは出来ない +二つ以上の連続する数字をまとめて2桁以上の数として扱うことは出来ない **問題解決の履歴 [#p24e82e6] この問題をエレガントに解く方法があるかもしれないが、筆者には全く思いつかない なので一般的に[[ブルートフォース:https://ja.wikipedia.org/wiki/%E7%B7%8F%E5%BD%93%E3%81%9F%E3%82%8A%E6%94%BB%E6%92%83]]と呼ばれる総当たり、力技で強引に問題を解決する手法を選択する この章では問題の各ルールに対して、どう対処するかの基本方針を固める ***1.と2.について [#f61c996d] -算術演算処理(calculate)には二項演算の二分木、式木の仕組みを利用してプログラム処理する -四則演算、括弧のネストの優先順位に従って式木を組む 資料: -[[二分木を使った数式の逆ポーランド記法化と計算:http://smdn.jp/programming/tips/polish/]] -[[C#のコード(内容を確認してみましたがCalculate関数内に誤植、動かないコードがあります。簡単な修正が必要です):http://smdn.jp/programming/tips/polish/impl_cs/]] ***3.について [#uc05ee4d] -括弧を使ったネストのある数式を文字列として受け取り解析処理(Parse)する必要がある。処理のサンプルは上記の資料内にある。資料では括弧の処理に関し詳しい説明は省かれている。この辺りはコードを読む必要があった。問題に合わせ4桁の数字に対する括弧の作り方を適切に出力制御させる必要がある。文字列でなく式木の形で渡しても良いかもしれない。この辺りは組みながら考えることにする -全ての論理式は同じ個数の右括弧と左括弧を持つ。片方の括弧が多いと式は成立しないので、それらはエラー処理する ***4.5.6.ついて [#sf2a74f5] -四則演算子+-×÷は算術演算子でもあり二項演算子である。A×BやA+Bのように二項の演算を扱う -+-は単項演算子でもある。-xは単項で負符号を表す。x-yは二項演算。-x-yはこれら機能が複合していると考える -+は省略できるが、-は省略できない 解決方法 \(a\cdot b\cdot c\cdot d\) の四則演算に対して \(-a\cdot b\cdot c\cdot d\) のケースの為に最初の数字を整数\(\mathbb{Z}\)。2番目以降を自然数\(\mathbb{N}\)として扱い処理することで解決する **掘り下げて考える [#d975c324] 仕組みを掘り下げて考えてみる。まず4桁の四則演算を以下のように考えるとする \(a①b②c③d\) \(a=\left\{ k|-9\le k\le -1,1\le k\le 9 \right\} \\ b,c,d=\left\{ k|1\le k\le 9 \right\} \\ ①,②,③=\left\{ +,-,\times ,\div \right\} \) つまり①②③は四則演算の二項結合子の集合。aは0を除いた-9~9までの数。b,c,dは1~9までの数となる ルール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) \) となる。このことから、二項結合子を挟んだ2項に対して左右に括弧で囲めば式を生成できる。そこで①をtrue,falseを持つフラグだと考える ①がfalseの時は \(a①b②c③d\) ①がtrueの時は \((a①b)②c③d\) このルールに従って表を作ると以下のようになる |①②③| | | |000|a①b②c③d| | |001|a①b②(c③d)| | |010|a①(b②c)③d| | |100|(a①b)②c③d| | |101|(a①b)②(c③d)| | |011|a①(b②(c③d))|a①((b②c)③d)| |110|((a①b)②c)③d|(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\) パターンで全てを網羅する事ができる。そこで、この式木を実際に組んで性質をまとめてみる。まず、以下の約束事を定義する \(\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パターンにまでシンプル化した式木を利用したコードのふたつで検証を行い、どちらの答えも同一であれば、まず間違いはないだろうとする。では、コーディングを始める
« Prev
Next »
式木、二項演算、括弧のネスト処理 のバックアップ一覧
式木、二項演算、括弧のネスト処理 のバックアップソース(No. All)
1: 2016-07-26 (火) 21:14:22
osinko
2: 2016-07-27 (水) 00:11:21
osinko
3: 2016-07-27 (水) 00:56:03
osinko
4: 2016-07-27 (水) 10:19:56
osinko
5: 2016-07-27 (水) 23:38:31
osinko
6: 2016-07-28 (木) 23:15:24
osinko
7: 2016-07-29 (金) 09:12:30
osinko
8: 2016-08-03 (水) 21:36:13
osinko
9: 2016-08-04 (木) 01:03:53
osinko
現: 2016-08-04 (木) 11:20:26
osinko