Analysieren von Formeln mit Funktionen

Guten Tag!

Es dauerte ein kleines Projekt. In der Projektanalyse und Berechnung mathematischer Formeln.
Anforderungen: verschachtelte Funktionen, unbegrenzte Verschachtelungstiefe und externe Variablen.

Es gibt viele Lösungen im Internet, aber alles ist falsch oder falsch. Oder ohne Formeln oder ohne Variablen oder die einfachsten Funktionen wie „1+ (2-3) / 4“. Die meisten Antworten gingen jedoch in Richtung lexikalischer Analyse und umgekehrter polnischer Notation. Also habe ich sie angewendet und Beispiele aus verschiedenen Quellen genommen.

Lassen Sie uns zunächst die lexikalische Analyse analysieren. Denn eine einfache Analyse der Formel durch Symbole mit einer Suche nach Funktionen, Operatoren, Variablen und anderen darin enthaltenen Dingen wäre äußerst unlesbar.

Die Implementierung der Algorithmen kann im Internet vorgenommen und Ihren Anforderungen entsprechend bearbeitet werden.

Für die lexikalische Analyse wurden kleine Änderungen vorgenommen:
  • Laden einer Liste von Variablen. Im Konstruktor werden Variablen durch ihre Werte ersetzt.
  • Ersetzen von Trennzeichen des ganzzahligen Bruchteils der Zahl durch das im System verwendete;
  • fügte ein unäres Minus hinzu;
  • überflüssige Token für mich gelöscht.

Folgendes ist passiert. Unten ist ein Link zur Quelle.

Liste der verfügbaren Token
enum LexemType
    {
        Plus,
        Minus,
        Multiply,
        Divide,
        UnarMinus,
        Equals,
        NotEquals,
        Greater,
        Lower,
        GreaterEquals,
        LowerEquals,
        And,
        Or,
        LBracket,
        RBracket,
        Semicolon,
        Identifier,
        Number
    }


Token-Definition
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),
        };
    }


Suchen und ersetzen Sie unäre Minus- und Pluszeichen
private string ReplaceUnarOperator(String src)
        {
            return Regex.Replace(Regex.Replace(Regex.Replace(Regex.Replace(src, @"(\(\+)", "("), @"(\A[\+]{1})", ""), @"(\(-)", "(%"), @"(\A[-]{1})", "%");
        }


Das Ersetzen des unären Plus und Minus könnte schöner implementiert werden, aber das Schreiben regulärer Ausdrücke ist nicht mein Talent. Mit Vergnügen werde ich Ihre Option nutzen.

Als nächstes habe ich die Implementierung des umgekehrten polnischen Eintrags aus dem Wiki überarbeitet. Es war notwendig, nicht mehr eine Zeichenfolge, sondern eine Liste von Token an die Eingabe zu übertragen. Diese Tatsache vereinfachte den Algorithmus geringfügig.

In SCF konvertieren
private static Lexem[] ConvertToPostfixNotation(List _lexems)
        {
            List outputSeparated = new List();
            Stack stack = new Stack();
            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-Berechnung
private static String getResult(List _lexems)
        {
            Stack stack = new Stack();
            Lexem[] postfix = ConvertToPostfixNotation(_lexems);
            Queue queue = new Queue(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;
        }


Die Besonderheit logischer Operationen besteht darin, dass wenn die Zahl größer als Null ist, sie wahr wird , andernfalls falsch .
Tatsächlich werden zu diesem Zeitpunkt die Formeln vollständig berücksichtigt. Es gibt keine Funktionsunterstützung.

Zuerst wollte ich Funktionen über ein separates Token implementieren. Aber etwas ist schief gelaufen ... Ich bin den Weg des geringsten Widerstands gegangen. Bei der lexikalischen Analyse der Formel werden alle Variablen, die durch numerische Werte ersetzt wurden, zu Zahlen, und alles andere, was nicht ersetzt wurde, wird zu Funktionen. Ein bisschen nicht logisch, aber es funktioniert.

Ferner finden und platzieren wir gemäß dem Algorithmus alle unsere Token mit neu geprägten Funktionen in der Liste der Funktionen.
Implementierung der Funktionsklasse
internal class Functions
    {
        public List FunctionList = new List();
        public List> operands = new List>();
        public Functions(Queue queue)
        {
            Queue lexems = new Queue();
            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 operand = new List();
            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();
                }
                else
                {
                    operand.Add(currLextm);
                }
            }
            operand.Remove(operand.Last());
            operands.Add(operand);
        }
    }



Eine Funktion kann andere Funktionen enthalten. Alles wird in die Operanden der Funktion eingegeben, und wenn dort eine Funktion vorhanden ist, wird eine neue Funktion rekursiv zu ihrer Liste hinzugefügt. Natürlich ist die Tiefe der Investitionen durch nichts begrenzt.

Eigentlich ein rekursiver Algorithmus, um Funktionswerte zu berechnen und durch das Ergebnis zu ersetzen:
Konstruktor und rekursives Ersetzen einer Funktion durch Berechnungsergebnisse
public static Dictionary NTDs = new Dictionary();
        public static Dictionary variables = new Dictionary();
        private List FunctionList = new List();
        private List> operands = new List>();
        private static List operators = new List()
        { 
            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 queue = new Queue(new Lexer(formula, variables).Lexems);
            Lexem currLextm = null;
            Queue lexems = new Queue();
            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 operand = new List();
            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();
                }
                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 Calc(List fList, List> lOps)
        {
            List res = new List();
            if (fList.Count == 0)
            {
                foreach (List op in lOps)
                {
                    String resOp = getResult(op);
                    res.Add(resOp);
                }
            }
            else
            {
                foreach (List 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 funcRes = Calc(func.FunctionList, func.operands);
                            List rList = new List();
                            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;
        }


Alle verwendeten Funktionen sind hier implementiert. Etwas Eigenes hinzuzufügen scheint nicht schwierig zu sein.

Zum Beispiel werde ich eine Lösung für die quadratische Gleichung geben:
Berechnungsbeispiel
Dictionary variables = new Dictionary();
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-a-c)>0;" + q1 + "; If((b*b-4-a-c)==0; " + q2 + "; 0))";
textBox1.Text += Formula + "\r\n";
textBox1.Text += new PostfixNotationExpression(Formula, variables).Calc() + "\r\n";
Formula = "If((b*b-4-a-c)>0;" + q2 + "; If((b*b-4-a-c)==0; " + q1 + "; 0))";
textBox1.Text += Formula + "\r\n";
textBox1.Text += new PostfixNotationExpression(Formula, variables).Calc() + "\r\n";


Ausgabeergebnis
a = 1
b = 2
c = -27
--------------
If((b*b-4-a-c)>0;(-b+Sqrt(Sqr(b)-4*a*c))/(2*a); If((b*b-4-a-c)==0; (-b-Sqrt(Sqr(b)-4*a*c))/(2*a); 0))
4.2915026221292
If((b*b-4-a-c)>0;(-b-Sqrt(Sqr(b)-4*a*c))/(2*a); If((b*b-4-a-c)==0; (-b+Sqrt(Sqr(b)-4*a*c))/(2*a); 0))
-6.2915026221292



Das Lösen quadratischer Gleichungen ist natürlich kein gutes Beispiel. Es gibt keine Möglichkeit, mehrere Antworten in den Ergebnissen zu erhalten. Wenn dann keine Wurzeln vorhanden sind, gibt diese Formel Null zurück. Aber die Möglichkeiten zu demonstrieren wird genügen.

[ Link zum Projekt ]

Es gibt genügend Stellen im Projekt für die Optimierung. Beispielsweise gibt es einen sich wiederholenden Code und die Ergebnisse aller Zweige der Bedingung werden berechnet. Und Sie wissen nie, was optimiert werden kann. Die Hauptsache ist, pünktlich anzuhalten.

PS: Beim Schreiben habe ich eine Funktion hinzugefügt, um Werte aus dem Diagramm abzurufen.

Grafikfunktion
public class NTDClass
    {
        public String Name;
        public Dictionary Graph;
        public NTDClass(String name, DataTable table)
        {
            Graph = new Dictionary();
            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;
        }
    }


Funktionsaufruf
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;
                                    }
.....
.....
.....


Jetzt auch beliebt: