Mathematische Funktionen berechnen

[Bgag]

Guten Abend!

Ich habe ein großes und nicht ganz triviales Problem. Ich muss für ein Projekt mathematische Funktionen, die ich als String übergeben bekomme, praktisch parsen und deren Ergebnisse für einen bestimmten Zahlenbereich mit einer bestimmten Schrittgröße je Achse ausrechnen. Dabei weiß ich nicht, wieviele Achsen (unbekannte Parameter bzw. Variablen) es gibt.

Es ist zum Beispiel möglich, dass ich die Formel für einen elliptischen Paraboloiden

(x^2 / 3) + (y^2 / 5) - z

bekomme. Offensichtlich haben wir es mit einer Funktion 3. Grades zu tun, die drei Variablen enthält. Diesen Variablen sollen nun äquidistante Schritte zugeordnet werden können (zum Beispiel 0.01) und es soll ein Bereich Angegeben werden können in dem die einzelnen Schritte berechnet werden. Am Ende soll man praktisch eine Schritttabelle erhalten, die alle Punkte aufeinanderfolgend als Zeilen enthält, sodass sie praktisch direkt nacheinander abgebar sind.

Das selbe Verfahren soll nun aber auch auf eine Funktion 2. Grades anwendbar sein.

Man kann das verfahren in soweit einschränken, dass die Anzahl der Variablen bzw. der Achsen angegeben werden kann, jedoch soll der Algorithmus in einem String alle Variablen erkennen, die Funktion selbst umsetzen und in dem gewünschten Bereich und der gewünschten Schrittgröße (kann zwischen allen Achsen unterschiedlich sein) die Werte berechnen.

Einigen wird in diesem Moment sicher die polnische oder die umgekehrte polnische Notation in den Sinn kommen. So auch mir. Jedoch sehe ich nicht, wie ich diese so erweitern, geschweige denn implementieren soll, dass sie zum einen die gängigen mathematischen Funktionen und Operationen unterstützt und zum anderen alle Variablen erkennt und diese in mehreren verschachtelten Schleifen unter vorgegebener äquidistanter Schrittgöße inkrementiert und das auch noch ab einem gewünschten Startwert.

Ihr seht das ganze ist etwas komplizierter. ich würde mich dennoch über Vorschläge bzw. Hinweise zu einer möglichen Lösung freuen.

Vielen Dank,

Andy

 

[vop]

Hi

Zunächst solltest du mal nach einem Funktionsparser suchen.
Z.B. by MyCSharp.

Dann denke ich, dass du soetwas wie eine Wertetabelle erstellen sollst. Etwa
x y z
0.01 0.01 12.2
0.02 0.01 12.3
...
Dazu mußt du in einer verschachtelten Schleife
für x und für y jeweils die Schrittweite erhöhen und den passenden Funktionswert mit Hilfe des Parsers errechnen
etwa so (keine c#-Syntax sondern Idee)
for ( x = startwertX; x< endwertX ; x+= schrittweiteX)
for ( y = startwertY; y < endwertY; y+= schrittweiteY)
z = BerechneFunktion();
SchreibeInWerteTabelle(x,y,z);
}
}
Hoffe, das hilft dir weiter

 

[Bgag]

Erstmal vielen vielen Dank für deine Antwort. Wie ich später die einzelnen Werte inkrementiere ist mit klar (Verschachtelung von Schleifen). Jedoch ist mir nicht klar, wie ich die Variablen in einem Funktionsstring von Operanden und Operatoren unterscheide bzw. dann durch C# Variablen ersetze.

Nach einem Funktionsparser habe ich auch bereits gesucht, jedoch nichts brauchbares gefunden. Die Seite MyCSharp war mir jedoch bisher unbekannt. Daher werde ich mich gleich mal dort umsehen.

Ich habe jedoch letzte Nacht noch einige Überlegungen zu diesem Problem angestellt.

Die umgekehrte Polnische Notation (engl. Reverse Polish Notation), die ich in meinen nachfolgenden Ausführungen mit RPN abkürzen werde, bringt einige tolle Vorteile mit sich. Die RPN ermöglicht es sich auf die eigentlichen Rechenoperationen zu konzentrieren, anstatt sich mit solch leidigen Themen, wie Punkt-Vor-Strich Rechnung oder Klammerregeln, zu beschäftigen. Daher meine Idee den eingegebenen Funktionsstring in die RPN umzuwandeln und dann damit die Ergebnisse zu errechnen. Ein Algorithmus zur Lösung einer Rechenaufgabe mit Hilfe der polnischen Notation ist mir bereits bekannt. Er basiert auf einfachen Stack-Operationen. Mein Problem liegt also vorerst in der Umwandlung eines Funktions-String in die RPN. Hat dazu irgendjemand eine Idee oder einen Ansatz?

Ein weiteres Problem wäre die Umwandlung der Variablen. Ich habe daran gedacht den Eingabe-String vor dem Umwandeln nach Buchstaben oder einer speziellen Escapesequenz zu durchsuchen. Dabei zähle ich die Vorkommen unterschiedlicher Variablen, sodass ich dann ein entsprechendes Array initiieren kann. Diese können dann später inkrementiert werden. Dies könnte zum Beispiel mit Hilfe einer Callback-Funktion geschehen.

Vielen Dank nochmals für deine Antwort.

Ich würde mich sehr über weitere Anregungen, Ansätze und Idee freuen.

MfG, Andy

 

[deepthroat]

Hi.

Erstmal vielen vielen Dank für deine Antwort. Wie ich später die einzelnen Werte inkrementiere ist mit klar (Verschachtelung von Schleifen). Jedoch ist mir nicht klar, wie ich die Variablen in einem Funktionsstring von Operanden und Operatoren unterscheide bzw. dann durch C# Variablen ersetze.

Am einfachsten wäre es, den String in einen Syntaxbaum umzuformen mit Variablen (als Blättern) und den Operationen als Verzweigungen. Dein Ausdruck vom Anfang könnte so wie in der angehängten Grafik umgeformt werden.

Dazu würde man Klassen definieren: IExpression, BinaryOperation{abstrakt}, Constant, Variable.

Alle Klassen besitzen eine compute() Methode.

Bsp:

public abstract class BinaryOperation : IExpression{
  protected IExpression lhs;
  protected IExpression rhs;
}

public class Plus : BinaryOperation {
  public override double compute() {
    return lhs.compute() + rhs.compute();
  }
}

Den Wert einer Variablen könntest du in einem Art "globalen" Speicher festlegen. Die compute Methode für Variablen könnte so aussehen, d.h. jede Variable holt sich wenn nötig ihren Wert aus dem globalen Speicher.

class Variable : IExpression {
  private String name;

  Variable(String name) { this.name = name; }
  override public double compute() {
    return GlobalerSpeicher[this.name];
  }
}

Gruß

 

[Bgag]

Danke für deine Antwort. Deine Grafik hat mich an eine meiner Vorlesungen erinnert. Daher habe ich mal mein altes Script herausgekramt und etwas herumgeblättert und bin auf das Kapitel Formale Sprachen gestoßen. Im Netz bin ich nun auf die folgende Grammatik bzw. kontextfreie Sprachegestoßen.

Expression = Term | Term ('+' | '-') Expression
Term = Factor | Factor ('*' | '/') Term
Factor = Terminal | Terminal '^' Factor
Terminal = ['+' | '-'] (Number | Variable | Constant | Function | '(' Expression ')')

Function = identifier '(' Expression ')'

Den theoretischen Hintergund habe ich verstanden, Ansätze der Implementierung auch, aber eben nicht ganz. Wie muss ich nun diese Grammatik in einen Parser umschreiben. Ein Ansatz müsste ja ungefähr wie folgt aussehen.

...

public void Expression(Token c)
{
   Term(c);

   c = getChar();

   if( c == "+"  || c == "-" )
   {
      Expression(getChar());
   }
}

public void Term(Token c)
{
   Factor(c);

   c = getChar();

   if( c == "*"  || c == "/" )
   {
      Term(getChar());
   }
}

public void Factor(Token c)
{
   Terminal(c);

   c = getChar();

   if( c == "^" )
   {
      Factor(getChar());
   }
}

...

Wie muss ich das nun aber weiterführen, sodass ich damit die komplette Expression parsen kann und fehlt da nicht auch noch etwas? Eine weitere Frage wäre, wie ich das nächste Zeichen ohne berücksichtigung von Spaces aus einem String lesen kann?!

Vielen Dank nochmals für deine Antwort.

Ich würde mich sehr über weitere Anregungen, Ansätze und Idee freuen.

MfG, Andy

 

[deepthroat]

Hi.

Schau mal hier: http://www.codeproject.com/KB/recipes/spart.aspx oder http://grammatica.percederberg.net/

Ist evlt. einfacher als das selbst nochmal zu schreiben.

Was du dort hast ist im Grunde ja nur ein Erkenner, du müßtest eben noch den Syntaxbaum entsprechend zusammenbauen.

Ansonsten teilt man den Kompilationsprozeß in Lexing und Parsing ein. Beim Lexing liest man die einzelnen Token /Terminalsymbole (nicht unbedingt chars) und überspringt eben Leerzeichen.

Gruß

PS: Oder schau mal hier: http://www.tutorials.de/forum/1138857-post5.html

 

[Bgag]

Zuerstmal danke für deine Antwort. Selber schreiben muss ich es auf jeden Fall, da ich dieses Wissen für die anstehende Informatik Klausur in den Bereichen Automaten und formale Sprachen, sowie Compilerbau benötige. Zudem soll dieses Programm im Rahmen eines Forschungsprojekts eingesetzt werden.

Wenn ich dich richtig verstanden habe stellt Lexing beim Kompilationsprozess das Zerlegen des Eingabestrings in Terminale dar. Das Parsen dieses Terminal-Strings (?) wird dann der Syntaxbaum erstellt. Dieser ermöglicht es dann wiederum die eigentlichen Rechenoperation auszuführen.

Wichtig ist mir ganz besonders, dass das gqanze einfach erweiterbar bleibt, sodass es später möglich ist zum Beispiel noch logische Operatoren hinzuzufügen.

Der Tipp den String direkt in Tokens anstatt in Charecters zu zerlegen ist definitiv sehr hilfreich. Dennoch weiß ich nicht, wie ich später möglichst effizient die einzelnen Tokens auseinanderklamüsern soll. Nicht jeder Eingabestring muss ja Whitespaces enthalten. Ich kann natürlich einfach etwas wildes zusammen basteln, das ist aber nicht Sinn der Sache.

Vielen Dank nochmals für deine Antwort.

Ich würde mich sehr über weitere Anregungen, Ansätze und Idee freuen.

MfG, Andy

 

[Bgag]

Shalom!

Es hat sich etwas in der Planung geändert. Ich werde das Programm in C implementieren, sodass ich es auch in der Uni für verschiedene Aufgaben nutzen kann und mir trotzdem die Möglichkeit offen halte es auf andere Systeme und in andere Projekte, die zum beispiel in C++ oder C# geschrieben sind zu portieren.

Zudem habe ich mir Gedanken darüber gemacht, wie ich die folgende Gramatik erweiteren muss um auch logische Operationen zu unterstützen. Die Frage ist auch, wie ich das Programm in C so gestalten kann, sodass es später ohne großen Aufwand erweitert werden kann. Gibt es zum Beispiel die Möglichkeit eine Struktur zu erschaffen, der sowohl ein Typ, ein Token, als auch eine Funktion übergeben werden, die im Falle, dass das entsprechende Token gefunden wird, ausgeführt bzw. aufgerufen wird.

Eine weitere Frage, wie ich je nach eingegebenen Ausdruck später den Rückgabewert ermittele. Rückgabewerte könnten in meiner einfachen Version boolean (muss als Enumeration definiert werden), integer und double sein.

Würde mich freuen, wenn mir jemand etwas bei der Planung helfen könnte. Kleinere Codebeispiele würden mich natürlich auch freuen.

Vielen Dank!

MfG, Andy