小さなプロジェクトがかかりました。 プロジェクトの分析と数式の計算。
要件：ネストされた関数、無制限のネストの深さ、外部変数。
インターネットには多くの解決策がありますが、それはすべて間違っているか間違っています。 または、式なし、変数なし、または「1+（2-3）/ 4」などの最も単純な機能。 しかし、答えのほとんどは語彙分析と逆ポーランド記法の方向にありました。 そこで、私はそれらを適用し、異なるソースから例を取りました。
まず、字句解析を分析しましょう。 関数、演算子、変数、その他の要素を検索するシンボルによる数式の単純な分析は、非常に読みにくいためです。
アルゴリズムの実装は、インターネットで取得し、ニーズに合わせて編集できます。
字句解析のために小さな変更を加えました：
- 変数のリストをロードします。 コンストラクターでは、変数は値に置き換えられます。
- 数値の整数部の区切り文字をシステムで使用される区切り文字に置き換えます。
- 単項マイナスを追加しました。
- 余分なトークンを削除してくれました。
これが何が起こったのかです。 以下はソースへのリンクです。
利用可能なトークンのリスト
enum LexemType { Plus, Minus, Multiply, Divide, UnarMinus, Equals, NotEquals, Greater, Lower, GreaterEquals, LowerEquals, And, Or, LBracket, RBracket, Semicolon, Identifier, Number }
トークン定義
static class LexemDefinitions { public static StaticLexemDefinition[] Statics = new[] { new StaticLexemDefinition("+", LexemType.Plus), new StaticLexemDefinition("-", LexemType.Minus), new StaticLexemDefinition("*", LexemType.Multiply), new StaticLexemDefinition("/", LexemType.Divide), new StaticLexemDefinition("%", LexemType.UnarMinus), new StaticLexemDefinition("==", LexemType.Equals), new StaticLexemDefinition("!=", LexemType.NotEquals), new StaticLexemDefinition(">=", LexemType.GreaterEquals), new StaticLexemDefinition("<=", LexemType.LowerEquals), new StaticLexemDefinition(">", LexemType.Greater), new StaticLexemDefinition("<", LexemType.Lower), new StaticLexemDefinition("&&", LexemType.And), new StaticLexemDefinition("||", LexemType.Or), new StaticLexemDefinition("(", LexemType.LBracket), new StaticLexemDefinition(")", LexemType.RBracket), new StaticLexemDefinition(";", LexemType.Semicolon), }; public static DynamicLexemDefinition[] Dynamics = new[] { new DynamicLexemDefinition("[a-zA-Z_][a-zA-Z0-9_]*", LexemType.Identifier), new DynamicLexemDefinition(@"([0-9]*\.?[0-9]+)", LexemType.Number), }; }
単項マイナスとプラスを検索して置換
private string ReplaceUnarOperator(String src) { return Regex.Replace(Regex.Replace(Regex.Replace(Regex.Replace(src, @"(\(\+)", "("), @"(\A[\+]{1})", ""), @"(\(-)", "(%"), @"(\A[-]{1})", "%"); }
単項のプラスとマイナスの置き換えはより美しく実装できますが、正規表現を書くことは私の才能ではありません。 喜んであなたのオプションを使用します。
次に、wikiから取得した逆ポーランドエントリの実装を再編集しました。 文字列ではなくトークンのリストを入力に転送する必要がありました。 この事実により、アルゴリズムがわずかに簡素化されました。
SCFに変換
private static Lexem[] ConvertToPostfixNotation(List<Lexem> _lexems) { List<Lexem> outputSeparated = new List<Lexem>(); Stack<Lexem> stack = new Stack<Lexem>(); foreach (Lexem c in _lexems) { if (operators.Contains(c.Type)) { if ((stack.Count > 0) && (c.Type != LexemType.LBracket)) { if (c.Type == LexemType.RBracket) { Lexem s = stack.Pop(); while (s.Type != LexemType.LBracket) { outputSeparated.Add(s); s = stack.Pop(); } } else { if (GetPriority(c.Type) > GetPriority(stack.Peek().Type)) { stack.Push(c); } else { while (stack.Count > 0 && GetPriority(c.Type) <= GetPriority(stack.Peek().Type)) outputSeparated.Add(stack.Pop()); stack.Push(c); } } } else stack.Push(c); } else outputSeparated.Add(c); } if (stack.Count > 0) foreach (Lexem c in stack) outputSeparated.Add(c); return outputSeparated.ToArray(); }
SCR計算
private static String getResult(List<Lexem> _lexems) { Stack<Lexem> stack = new Stack<Lexem>(); Lexem[] postfix = ConvertToPostfixNotation(_lexems); Queue<Lexem> queue = new Queue<Lexem>(postfix); Lexem str = queue.Dequeue(); while (queue.Count >= 0) { if (operators.Contains(str.Type)) { Lexem result = new Lexem(); result.Type = LexemType.Number; try { switch (str.Type) { case LexemType.UnarMinus: { Double a = Convert.ToDouble(stack.Pop().Value); result.Value = (-a).ToString(); break; } case LexemType.Plus: { Double b = Convert.ToDouble(stack.Pop().Value); Double a = Convert.ToDouble(stack.Pop().Value); result.Value = (a + b).ToString(); break; } case LexemType.Minus: { Double b = Convert.ToDouble(stack.Pop().Value); Double a = Convert.ToDouble(stack.Pop().Value); result.Value = (a - b).ToString(); break; } case LexemType.Multiply: { Double b = Convert.ToDouble(stack.Pop().Value); Double a = Convert.ToDouble(stack.Pop().Value); result.Value = (a * b).ToString(); break; } case LexemType.Divide: { Double b = Convert.ToDouble(stack.Pop().Value); Double a = Convert.ToDouble(stack.Pop().Value); result.Value = (a / b).ToString(); break; } case LexemType.Equals: { Double b = Convert.ToDouble(stack.Pop().Value); Double a = Convert.ToDouble(stack.Pop().Value); Boolean r = (a == b); result.Value = (r ? 1 : 0).ToString(); break; } case LexemType.NotEquals: { Double b = Convert.ToDouble(stack.Pop().Value); Double a = Convert.ToDouble(stack.Pop().Value); Boolean r = (a != b); result.Value = (r ? 1 : 0).ToString(); break; } case LexemType.Greater: { Double b = Convert.ToDouble(stack.Pop().Value); Double a = Convert.ToDouble(stack.Pop().Value); Boolean r = (a > b); result.Value = (r ? 1 : 0).ToString(); break; } case LexemType.GreaterEquals: { Double b = Convert.ToDouble(stack.Pop().Value); Double a = Convert.ToDouble(stack.Pop().Value); Boolean r = (a >= b); result.Value = (r ? 1 : 0).ToString(); break; } case LexemType.Lower: { Double b = Convert.ToDouble(stack.Pop().Value); Double a = Convert.ToDouble(stack.Pop().Value); Boolean r = (a < b); result.Value = (r ? 1 : 0).ToString(); break; } case LexemType.LowerEquals: { Double b = Convert.ToDouble(stack.Pop().Value); Double a = Convert.ToDouble(stack.Pop().Value); Boolean r = (a <= b); result.Value = (r ? 1 : 0).ToString(); break; } case LexemType.Or: { Boolean b = Convert.ToBoolean(Convert.ToDouble(stack.Pop().Value) > 0 ? 1 : 0); Boolean a = Convert.ToBoolean(Convert.ToDouble(stack.Pop().Value) > 0 ? 1 : 0); Boolean r = (a || b); result.Value = (r ? 1 : 0).ToString(); break; } case LexemType.And: { Boolean b = Convert.ToBoolean(Convert.ToDouble(stack.Pop().Value) > 0 ? 1 : 0); Boolean a = Convert.ToBoolean(Convert.ToDouble(stack.Pop().Value) > 0 ? 1 : 0); Boolean r = (a && b); result.Value = (r ? 1 : 0).ToString(); break; } } } catch (Exception ex) { new InvalidOperationException(ex.Message); } stack.Push(result); if (queue.Count > 0) str = queue.Dequeue(); else break; } else { stack.Push(str); if (queue.Count > 0) { str = queue.Dequeue(); } else break; } } String rValue = stack.Pop().Value; return rValue; }
論理演算の特性は、数値がゼロより大きい場合はTrueになり、そうでない場合はFalseになることです。
実際、この段階では式は完全に考慮されます。 機能のサポートはありません。
最初は、別のトークンを使用して機能を実装したかった。 しかし、何かがうまくいかなかった...私は最も抵抗の少ない道を歩んだ。 数式の字句解析では、数値に置き換えられたすべての変数が数値になり、置き換えられなかった他のすべてが関数になります。 少し論理的ではありませんが、機能します。
さらに、アルゴリズムに従って、すべてのトークンを見つけて、新しく作成された関数とともに関数のリストに入れます。
関数クラスの実装
internal class Functions { public List<Functions> FunctionList = new List<Functions>(); public List<List<Lexem>> operands = new List<List<Lexem>>(); public Functions(Queue<Lexem> queue) { Queue<Lexem> lexems = new Queue<Lexem>(); Lexem currLextm = queue.Dequeue(); int brackets = 1; while (queue.Count > 0 && brackets > 0) { currLextm = queue.Dequeue(); if (currLextm.Type == LexemType.Identifier) { currLextm.Value = currLextm.Value + "{" + FunctionList.Count.ToString() + "}"; lexems.Enqueue(currLextm); FunctionList.Add(new Functions(queue)); } else { if (currLextm.Type == LexemType.LBracket) { brackets++; } if (currLextm.Type == LexemType.RBracket) { brackets--; } lexems.Enqueue(currLextm); } } List<Lexem> operand = new List<Lexem>(); while (lexems.Count > 0) { currLextm = lexems.Dequeue(); if (currLextm.Type == LexemType.LBracket) { brackets++; } if (currLextm.Type == LexemType.RBracket) { brackets--; } if ((currLextm.Type == LexemType.Semicolon)&&(brackets==0)) { operands.Add(operand); operand = new List<Lexem>(); } else { operand.Add(currLextm); } } operand.Remove(operand.Last()); operands.Add(operand); } }
関数には他の関数が含まれる場合があります。 すべてが関数のオペランドに入力され、そこに関数がある場合、新しい関数がそのリストに再帰的に追加されます。 もちろん、投資の深さは何によっても制限されません。
実際、関数値を計算して結果で置き換えるための再帰アルゴリズム：
計算結果を使用した関数のコンストラクターおよび再帰的置換
public static Dictionary<Int32, NTDClass> NTDs = new Dictionary<Int32, NTDClass>(); public static Dictionary<String, Double> variables = new Dictionary<string,double>(); private List<Functions> FunctionList = new List<Functions>(); private List<List<Lexem>> operands = new List<List<Lexem>>(); private static List<LexemType> operators = new List<LexemType>() { LexemType.Multiply, LexemType.Divide, LexemType.Plus, LexemType.Minus, LexemType.UnarMinus, LexemType.And, LexemType.Or, LexemType.Equals, LexemType.NotEquals, LexemType.Greater, LexemType.Lower, LexemType.GreaterEquals, LexemType.LowerEquals, LexemType.LBracket, LexemType.RBracket }; public PostfixNotationExpression(String formula) { Queue<Lexem> queue = new Queue<Lexem>(new Lexer(formula, variables).Lexems); Lexem currLextm = null; Queue<Lexem> lexems = new Queue<Lexem>(); while (queue.Count > 0) { currLextm = queue.Dequeue(); if (currLextm.Type == LexemType.Identifier) { currLextm.Value = currLextm.Value + "{" + FunctionList.Count.ToString() + "}"; lexems.Enqueue(currLextm); FunctionList.Add(new Functions(queue)); } else { lexems.Enqueue(currLextm); } } List<Lexem> operand = new List<Lexem>(); Int32 brackets = 0; while (lexems.Count > 0) { currLextm = lexems.Dequeue(); if (currLextm.Type == LexemType.LBracket) { brackets++; } if (currLextm.Type == LexemType.RBracket) { brackets--; } if ((currLextm.Type == LexemType.Semicolon) && (brackets == 0)) { operands.Add(operand); operand = new List<Lexem>(); } else { operand.Add(currLextm); } } operands.Add(operand); } public String Calc() { String sep = NumberFormatInfo.CurrentInfo.NumberDecimalSeparator; String res = Calc(FunctionList, operands).First(); res = res == null ? "0.0" : res; res = res.Replace(".", sep).Replace(",", sep); return res; } private static List<String> Calc(List<Functions> fList, List<List<Lexem>> lOps) { List<String> res = new List<String>(); if (fList.Count == 0) { foreach (List<Lexem> op in lOps) { String resOp = getResult(op); res.Add(resOp); } } else { foreach (List<Lexem> op in lOps) { for (int i = 0; i < op.Count; i++) { if (op[i].Type == LexemType.Identifier) { String fName = op[i].Value.Remove(op[i].Value.IndexOf("{")); String fNumStr = op[i].Value.Remove(0, op[i].Value.IndexOf("{") + 1); fNumStr = fNumStr.Remove(fNumStr.IndexOf("}")); Int32 fNum = Int32.Parse(fNumStr); Functions func = fList[fNum]; List<String> funcRes = Calc(func.FunctionList, func.operands); List<Double> rList = new List<double>(); for (int k = 0; k < funcRes.Count; k++) { rList.Add(Double.Parse(funcRes[k])); } switch (fName) { case "NTD": { String val = "0.0"; Int32 key = (Int32)rList[0]; if (NTDs.ContainsKey(key)) { val = NTDs[key].getValue(rList[1]).ToString(); } op[i] = new Lexem() { Type = LexemType.Number, Value = val }; break; } case "If": { op[i] = new Lexem() { Type = LexemType.Number, Value = (rList[0] == 1 ? rList[1] : rList[2]).ToString() }; break; } case "Sqr": { op[i] = new Lexem() { Type = LexemType.Number, Value = (rList[0] * rList[0]).ToString() }; break; } case "Sqrt": { op[i] = new Lexem() { Type = LexemType.Number, Value = (Math.Sqrt(rList[0])).ToString() }; break; } case "Min": { Double Min = Double.MaxValue; for (int k = 0; k < rList.Count; k++) { if (rList[k] < Min) { Min = rList[k]; } } op[i] = new Lexem() { Type = LexemType.Number, Value = Min.ToString() }; break; } case "Max": { Double Max = Double.MinValue; for (int k = 0; k < rList.Count; k++) { if (rList[k] > Max) { Max = rList[k]; } } op[i] = new Lexem() { Type = LexemType.Number, Value = Max.ToString() }; break; } } } } String resOp = getResult(op); res.Add(resOp); } } return res; }
使用されるすべての機能はここで実装されます。 独自の何かを追加することは難しくないようです。
たとえば、二次方程式の解を示します。
計算例
Dictionary<String, Double> variables = new Dictionary<string, double>(); variables.Add("a", 1); variables.Add("b", 2); variables.Add("c", -27); foreach (var ivar in variables) { textBox1.Text += ivar.Key + " = " + ivar.Value.ToString() + "\r\n"; } textBox1.Text += "--------------\r\n"; // a*x2 + bx + c = 0 String q1 = "(-b+Sqrt(Sqr(b)-4*a*c))/(2*a)"; String q2 = "(-b-Sqrt(Sqr(b)-4*a*c))/(2*a)"; String Formula = "If((b*b-4-ac)>0;" + q1 + "; If((b*b-4-ac)==0; " + q2 + "; 0))"; textBox1.Text += Formula + "\r\n"; textBox1.Text += new PostfixNotationExpression(Formula, variables).Calc() + "\r\n"; Formula = "If((b*b-4-ac)>0;" + q2 + "; If((b*b-4-ac)==0; " + q1 + "; 0))"; textBox1.Text += Formula + "\r\n"; textBox1.Text += new PostfixNotationExpression(Formula, variables).Calc() + "\r\n";
出力結果
a = 1 b = 2 c = -27 -------------- If((b*b-4-ac)>0;(-b+Sqrt(Sqr(b)-4*a*c))/(2*a); If((b*b-4-ac)==0; (-b-Sqrt(Sqr(b)-4*a*c))/(2*a); 0)) 4.2915026221292 If((b*b-4-ac)>0;(-b-Sqrt(Sqr(b)-4*a*c))/(2*a); If((b*b-4-ac)==0; (-b+Sqrt(Sqr(b)-4*a*c))/(2*a); 0)) -6.2915026221292
もちろん、二次方程式を解くことは良い例ではありません。 結果に複数の回答を取得する方法はありません。そして、根がない場合、この式はゼロを返します。 しかし、可能性を実証するために行います。
[ プロジェクトへのリンク ]
プロジェクトには最適化のための十分な場所があります。 たとえば、繰り返しコードがあり、条件のすべての分岐の結果が計算されます。 そして、何が最適化できるのか決してわかりません。 主なことは、時間通りに停止することです。
PS：執筆中に、グラフから値を取得する関数を追加しました。
グラフ関数
public class NTDClass { public String Name; public Dictionary<Double, Double> Graph; public NTDClass(String name, DataTable table) { Graph = new Dictionary<double, double>(); foreach(DataRow row in table.AsEnumerable()) { Double x = Double.Parse(row["Id"].ToString()); Double y = Double.Parse(row["VALUE"].ToString()); if (!Graph.ContainsKey(x)) { Graph.Add(x, y); } else { x += 0.00001; Graph.Add(x, y); } } } public Double getValue(Double b) { Double res = Double.NaN; var xScale = Graph.Keys.AsEnumerable(); Double minX = xScale.OrderBy(x => x).Where(x => x <= b).DefaultIfEmpty(xScale.OrderBy(x => x).First()).LastOrDefault(); Double maxX = xScale.OrderBy(x => x).Where(x => x >= b).DefaultIfEmpty(xScale.OrderBy(x => x).Last()).FirstOrDefault(); Double minY = Graph[minX]; Double maxY = Graph[maxX]; res = (((b - minX) * (maxY - minY)) / (maxX - minX) + minY); return res; } }
関数呼び出し
switch (fName) { case "NTD": { String val = "0.0"; Int32 key = (Int32)rList[0]; if (NTDs.ContainsKey(key)) { val = NTDs[key].getValue(rList[1]).ToString(); } op[i] = new Lexem() { Type = LexemType.Number, Value = val }; break; } ..... ..... .....