式木、二項演算、括弧のネスト処理
をテンプレートにして作成
Unity学習帳2冊目
式木、二項演算、括弧のネスト処理 をテンプレートにして作成
[
トップ
] [
差分
|
バックアップ
|
リロード
] [
新規
|
一覧
|
検索
|
最新
|
ヘルプ
]
[ ]
開始行:
TITLE:式木、二項演算、括弧のネスト処理
#jsmath
**式木、二項演算、括弧のネスト処理
ネットをぶらぶら散策していると面白い問題を見つけた。25年...
[[MSX_Magazine_1991-12_ASCII_JP:https://archive.org/strea...
論理や算術演算を自動生成して目的に合わせ解く問題。非常に...
資料:[[MSXマガジン_バックナンバーアーカイブ:https://arch...
***問題
0000~9999までの4桁の数の間に四則演算を入れて10が作れな...
<ルール>
++-×÷の記号のみ使用できる事とする。ルートやべき乗は使用...
+計算は一般の式と同じ順序で行う(×÷が優先、左から右に計算...
+()は使用できる
+最初の数字の頭に-を付けて負の数にすることは出来る
+数字の並べ替えは出来ない
+二つ以上の連続する数字をまとめて2桁以上の数として扱うこ...
**問題解決の履歴
この問題をエレガントに解く方法があるかもしれないが、筆者...
なので一般的に[[ブルートフォース:https://ja.wikipedia.org...
この章では問題の各ルールに対して、どう対処するかの基本方...
***1.と2.について
-算術演算処理(calculate)には二項演算の二分木、式木の仕...
-四則演算、括弧のネストの優先順位に従って式木を組む
資料:
-[[二分木を使った数式の逆ポーランド記法化と計算:http://sm...
-[[C#のコード(内容を確認してみましたがCalculate関数内に...
***3.について
-括弧を使ったネストのある数式を文字列として受け取り解析処...
-全ての論理式は同じ個数の右括弧と左括弧を持つ。片方の括弧...
***4.5.6.ついて
-四則演算子+-×÷は算術演算子でもあり二項演算子である。A×...
-+-は単項演算子でもある。-xは単項で負符号を表す。x-y...
-+は省略できるが、-は省略できない
解決方法
\(a\cdot b\cdot c\cdot d\) の四則演算に対して \(-a\cdot b...
**掘り下げて考える
仕組みを掘り下げて考えてみる。まず4桁の四則演算を以下の...
\(a①b②c③d\)
\(a=\left\{ k|-9\le k\le -1,1\le k\le 9 \right\} \\ b,c,d...
つまり①②③は四則演算の二項結合子の集合。aは0を除いた-9~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.Expre...
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}", roo...
}
//自分自身のクラスの中に自分自身と同じクラス(型)を...
//再帰関数と絡めて型を運用するとシンプルにデーター設...
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...
Left.Parse();
// right-hand side
Right = new Node(RemoveBracket(this.Expressio...
Right.Parse();
// operator
this.Expression = this.Expression.Substring(p...
}
//文字列の式から外側の括弧を消す処理
//例:"((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("unbala...
//文字列、先頭と末尾文字を抜いて出力
str = str.Substring(1, str.Length - 2);
//先頭の括弧をチェックして二重以上の括弧を再...
if (str.StartsWith("("))
return RemoveBracket(str);
else
return str;
}
//一番、低い優先順位の演算結合子の文字列位置を返す
private static int GetOperatorPos(string expressi...
{
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"ならば一番優先順位が...
if (nest == 0 && priority <= lowestPriori...
{
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();
}
//自分自身を必要回複数呼び出す再帰関数
//ノードは結合子に、サブツリーの末端は左右の葉がn...
public double Calculate()
{
//両葉に何か入っているとき処理する
if (Left != null && Right != null)
{
//再帰先を受け取る
var leftOperand = Left.Calculate();
var rightOperand = Right.Calculate();
//ノードの演算結合子を処理
switch (this.Expression)
{
case "+": return leftOperand + rightO...
case "-": return leftOperand - rightO...
case "*": return leftOperand * rightO...
case "/": return leftOperand / rightO...
default: return 0.0d;
}
}
else {
return double.Parse(Expression); //両...
}
}
}
}
}}
次にルール3.の括弧の処理を考える。例えば&font(Red){二項結...
①が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で同値となっている。これはひ...
例:"5/(3+(2*4))"
①=/
②=+
③=*
a=5
b=3
c=2
d=4
一番優先順位が低い結合子は ①=/ になる。従って式木は
&ref(tree1.png);
この一番優先順位が低い結合子を選ぶアルゴリズムは資料のGet...
括弧もここでうまく処理されているので注目。もう一例
例:"(5/(3+2))*4"
一番優先順位が低い結合子は ③=* になる。従って式木は
&ref(tree2.png);
この要領で式木を生成すればいい。式木の末端程、計算優先順...
**式木から数式のパターンを眺めてみる
ここで視点を変えて式木から数式のパターンを眺めてみる。よ...
&ref(tree3.png);
この①~③の並びを順列と考えて置換すると
①②③
①③②
②①③ ×
②③① ×
③①②
③②①
の \(3!=3\times 2\times 1=6\) パターンで全てを網羅する事...
\(①,②,③=\left\{ \times ,\div ,+,- \right\} \\ \overline {...
//\(\bullet =\left\{ \times ,\div ,+,- \right\} \\ \overl...
//ここで使用している「\(\bullet \)」マークは匿名の二項結...
二項結合演算子(この場合①~③で「×÷+-」の集合)に上線が...
***式木123のパターン
\(a①\left( b②\left( c③d \right) \right) \quad \Leftright...
&ref(tree3.png);
***式木132のパターン
\(a\underline { ① } \left( b②c \right) \overline { ③ } d\...
&ref(tree4.png);
***式木312のパターン
\(a\overline { ① } \left( b②c \right) \underline { ③ } d\...
&ref(tree5.png);
***式木321のパターン
\(\left( a①b \right) \overline { ② } c\underline { ③ } d\...
&ref(tree6.png);
***式木亜種のパターン
\(\left( a①b \right) ②\left( c③d \right) \quad \Leftright...
&ref(tree8.png);
***式木から見て②から始まるパターンは使えない
式木から見て②から始まるパターンはありえない。そのことを以...
&ref(tree7.png);
これは項同士が隣り合っていない、間に邪魔な項があり演算で...
***括弧によるネストがない数式を式木として見てみる
次に括弧によるネストがない数式を式木として見てみると以下...
\(a\overline { ① } b\overline { ② } c\overline { ③ } d\qu...
***中間まとめ
&font(150%){以上の事から式木の5パターンで4項の括弧を含め...
この考えが正しいかどうか。まずブルートフォースの形式で力...
**群(group)の理論で、式木の置換処理を考える
資料:[[群 (数学):https://ja.wikipedia.org/wiki/%E7%BE%A4...
数学における「群」とは「似ているものをひっくるめる」理論...
終了行:
TITLE:式木、二項演算、括弧のネスト処理
#jsmath
**式木、二項演算、括弧のネスト処理
ネットをぶらぶら散策していると面白い問題を見つけた。25年...
[[MSX_Magazine_1991-12_ASCII_JP:https://archive.org/strea...
論理や算術演算を自動生成して目的に合わせ解く問題。非常に...
資料:[[MSXマガジン_バックナンバーアーカイブ:https://arch...
***問題
0000~9999までの4桁の数の間に四則演算を入れて10が作れな...
<ルール>
++-×÷の記号のみ使用できる事とする。ルートやべき乗は使用...
+計算は一般の式と同じ順序で行う(×÷が優先、左から右に計算...
+()は使用できる
+最初の数字の頭に-を付けて負の数にすることは出来る
+数字の並べ替えは出来ない
+二つ以上の連続する数字をまとめて2桁以上の数として扱うこ...
**問題解決の履歴
この問題をエレガントに解く方法があるかもしれないが、筆者...
なので一般的に[[ブルートフォース:https://ja.wikipedia.org...
この章では問題の各ルールに対して、どう対処するかの基本方...
***1.と2.について
-算術演算処理(calculate)には二項演算の二分木、式木の仕...
-四則演算、括弧のネストの優先順位に従って式木を組む
資料:
-[[二分木を使った数式の逆ポーランド記法化と計算:http://sm...
-[[C#のコード(内容を確認してみましたがCalculate関数内に...
***3.について
-括弧を使ったネストのある数式を文字列として受け取り解析処...
-全ての論理式は同じ個数の右括弧と左括弧を持つ。片方の括弧...
***4.5.6.ついて
-四則演算子+-×÷は算術演算子でもあり二項演算子である。A×...
-+-は単項演算子でもある。-xは単項で負符号を表す。x-y...
-+は省略できるが、-は省略できない
解決方法
\(a\cdot b\cdot c\cdot d\) の四則演算に対して \(-a\cdot b...
**掘り下げて考える
仕組みを掘り下げて考えてみる。まず4桁の四則演算を以下の...
\(a①b②c③d\)
\(a=\left\{ k|-9\le k\le -1,1\le k\le 9 \right\} \\ b,c,d...
つまり①②③は四則演算の二項結合子の集合。aは0を除いた-9~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.Expre...
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}", roo...
}
//自分自身のクラスの中に自分自身と同じクラス(型)を...
//再帰関数と絡めて型を運用するとシンプルにデーター設...
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...
Left.Parse();
// right-hand side
Right = new Node(RemoveBracket(this.Expressio...
Right.Parse();
// operator
this.Expression = this.Expression.Substring(p...
}
//文字列の式から外側の括弧を消す処理
//例:"((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("unbala...
//文字列、先頭と末尾文字を抜いて出力
str = str.Substring(1, str.Length - 2);
//先頭の括弧をチェックして二重以上の括弧を再...
if (str.StartsWith("("))
return RemoveBracket(str);
else
return str;
}
//一番、低い優先順位の演算結合子の文字列位置を返す
private static int GetOperatorPos(string expressi...
{
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"ならば一番優先順位が...
if (nest == 0 && priority <= lowestPriori...
{
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();
}
//自分自身を必要回複数呼び出す再帰関数
//ノードは結合子に、サブツリーの末端は左右の葉がn...
public double Calculate()
{
//両葉に何か入っているとき処理する
if (Left != null && Right != null)
{
//再帰先を受け取る
var leftOperand = Left.Calculate();
var rightOperand = Right.Calculate();
//ノードの演算結合子を処理
switch (this.Expression)
{
case "+": return leftOperand + rightO...
case "-": return leftOperand - rightO...
case "*": return leftOperand * rightO...
case "/": return leftOperand / rightO...
default: return 0.0d;
}
}
else {
return double.Parse(Expression); //両...
}
}
}
}
}}
次にルール3.の括弧の処理を考える。例えば&font(Red){二項結...
①が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で同値となっている。これはひ...
例:"5/(3+(2*4))"
①=/
②=+
③=*
a=5
b=3
c=2
d=4
一番優先順位が低い結合子は ①=/ になる。従って式木は
&ref(tree1.png);
この一番優先順位が低い結合子を選ぶアルゴリズムは資料のGet...
括弧もここでうまく処理されているので注目。もう一例
例:"(5/(3+2))*4"
一番優先順位が低い結合子は ③=* になる。従って式木は
&ref(tree2.png);
この要領で式木を生成すればいい。式木の末端程、計算優先順...
**式木から数式のパターンを眺めてみる
ここで視点を変えて式木から数式のパターンを眺めてみる。よ...
&ref(tree3.png);
この①~③の並びを順列と考えて置換すると
①②③
①③②
②①③ ×
②③① ×
③①②
③②①
の \(3!=3\times 2\times 1=6\) パターンで全てを網羅する事...
\(①,②,③=\left\{ \times ,\div ,+,- \right\} \\ \overline {...
//\(\bullet =\left\{ \times ,\div ,+,- \right\} \\ \overl...
//ここで使用している「\(\bullet \)」マークは匿名の二項結...
二項結合演算子(この場合①~③で「×÷+-」の集合)に上線が...
***式木123のパターン
\(a①\left( b②\left( c③d \right) \right) \quad \Leftright...
&ref(tree3.png);
***式木132のパターン
\(a\underline { ① } \left( b②c \right) \overline { ③ } d\...
&ref(tree4.png);
***式木312のパターン
\(a\overline { ① } \left( b②c \right) \underline { ③ } d\...
&ref(tree5.png);
***式木321のパターン
\(\left( a①b \right) \overline { ② } c\underline { ③ } d\...
&ref(tree6.png);
***式木亜種のパターン
\(\left( a①b \right) ②\left( c③d \right) \quad \Leftright...
&ref(tree8.png);
***式木から見て②から始まるパターンは使えない
式木から見て②から始まるパターンはありえない。そのことを以...
&ref(tree7.png);
これは項同士が隣り合っていない、間に邪魔な項があり演算で...
***括弧によるネストがない数式を式木として見てみる
次に括弧によるネストがない数式を式木として見てみると以下...
\(a\overline { ① } b\overline { ② } c\overline { ③ } d\qu...
***中間まとめ
&font(150%){以上の事から式木の5パターンで4項の括弧を含め...
この考えが正しいかどうか。まずブルートフォースの形式で力...
**群(group)の理論で、式木の置換処理を考える
資料:[[群 (数学):https://ja.wikipedia.org/wiki/%E7%BE%A4...
数学における「群」とは「似ているものをひっくるめる」理論...
ページ名: