Löse Gleichung aus Zeichenfolge Ergebnis in C

StackOverflow https://stackoverflow.com/questions/2844947

Frage

Ich möchte wissen, ob jemand Informationen oder Erfahrung hat, wie etwas zu tun, was einfach klingt, aber ich mag es nicht sehen, wenn sie versuchen, es zu programmieren. Die Idee dahinter ist: Gib einen String eine Gleichung enthält, wie zum Beispiel: „2 * x = 10“, zum Beispiel (dies ist einfach, aber es kann sehr komplex, wie sqrt erhalten (54) * 35 = x ^ 2, und so auf ....) und zurückkehren würde das Programm x = 5 und möglicherweise ein Protokoll geben, wie er dort ankam.

Ist das machbar? Wenn ja, hat jemand einen Vorsprung? Für Informationen gibt es diese Seite ( http://www.numberempire.com/equationsolver.php ), die die gleiche Sache in PHP tut, ist aber nicht Open Source.

Vielen Dank für jede Hilfe!

War es hilfreich?

Lösung

Dies wird als „Parsen“ genannt, und obwohl Informatik hat dieses Problem bereits gelöst ist es überhaupt nicht einfach, bis Sie sie gründlich verstehen. Es gibt eine ganze Computer-Wissenschaft Disziplin, die beschreibt, wie dieses Problem zu lösen. In C müssen Sie die Grammatik Ihrer Eingabe definieren (eventuell mit Vorrangregeln drin), dann führen Sie lexikalische Analyse auf Ihre Eingabe, dann Parse das Ergebnis und schließlich bewerten Sie Ihre Parse Baum.

In Sprachen wie Ruby, aber, weil Sie eine solche gründliche Unterstützung für String-Manipulation und weil Sie eine solche enorme Laufzeit Macht haben, können Sie Ihr Problem mit einer einzigen Code-Zeile wie so lösen: 

puts(eval($_)) while gets

Ja, das deckt mehr als das, was man sich wünschen.

Andere Tipps

Zum einen müssen Sie richtig definieren, welche Arten von Gleichungen Sie als Eingabe haben. Dann sollten Sie eine gute Abstraktion schaffen die Gleichung darstellen, z.B. eine Polynom-Klasse. Wenn Sie komplexere Ausdruck verwenden möchten, gehen Sie für einen Baum für numerische Ausdrücke. Parsen kann sehr einfach sein, wenn Sie gute Regeln haben den Ausdruck in Präfixnotation zu konvertieren, wird mit Auswertung dann einfach Stacks. Sobald Sie artithmetic Bäume oder Polynome haben, können Sie Transformationen implementieren, um die Variable (n) zu berechnen.

Wenn Gleichungen Komplex bekommen, wird es sicherlich nicht wenige Zeilen Code C ++ / C sein.

Für lineare Gleichungen, würden Sie eine der Methoden in Lineare Algebra Büchern beschrieben zu simulieren haben. Der Code dafür ist klein genug.

Sie könnte versuchen, in SymPy zu Ihrem C Verknüpfung (oder C ++) Code und deren Verwendung Ihrer Gleichungen zu lösen.

IIRC, hat SymPy diese Art von Funktionalität. Außerdem soll es einfacher sein, die Eingabezeichenfolge in einer verwendbaren Gleichung innerhalb von Python zu manipulieren und es dann für die Lösung zu SymPy vorübergehen.

Es geht um zwei Teile, um Ihr Problem zu sein: die Gleichung (n) Parsen, und sie symbolisch zu lösen. Ich werde nicht viel über die ersten sagen, da andere Antworten bereits, dass Thema gut abgedeckt sind; meine persönliche Empfehlung wäre ein einfachen Rekursiver Abstieg für Ausdrücke in Präfixnotation schreiben zu können.

Der zweite Teil, Lösen von Gleichungen analytisch, wird schwierig sein. Generell gibt es spezielle Klassen von Gleichungen für die Standardmethoden existieren eine analytische Lösung zu finden:

  • Lineare Gleichungssysteme: jede direkte lineare Löser. Wenn Sie die Schritte ausdrücklich und die Anzahl der Gleichungen / Unbekannte ist klein zeigen wollen, würde ich etwas Einfaches wie verschwenkten Gauß-Elimination oder Cramer-Regel empfehlen.
  • System Polynomgleichungssysteme: Entspricht nach Variablensubstitution, zu den Wurzeln von einzelnen Polynome finden. Wenn diese Grad haben <= 4 gibt es Formeln für exakte Lösungen. NB: Grad 3 und 4 sind diese Formeln sind nicht angenehm
    • .
  • Rational-Lösungen auf ein System von Polynom Gleichungen mit rationalen Koeffizienten: Do Variablensubstitution wie oben. Dann Brute-Force mit dem rationalen Nulltest.
  • Andere Arten von Gleichungen: Viel Glück. Für kompliziertere [Systeme] nichtlinearen Gleichungen, wenn Sie (nicht-analytische) Lösungen für die numerische absetzen können, Blick in Newton-Verfahren.

Eine Korrektur: Dies ist keine lineare Algebra, die in der Regel Matrizes von mehreren Gleichungen und Unbekannten bedeuten

.

Ihr Beispiel ist sicherlich nicht komplex.

Was Sie brauchen, ist ein einfacher Ausdruck Grammatik und Parser. Analysieren Sie die Gleichung in einen abstrakten Syntaxbaum und zu Fuß den Baumes um sie zu bewerten.

Wenn Sie Java geschrieben haben, es könnte wie folgt aussehen diese . Ein weiteres Beispiel ist symja . Vielleicht wird es genug Inspiration für Sie, mit Ihrer eigenen für C zu kommen ++.

Sie können auch in Mathematica und Wolfram Alpha zu suchen. Stephen Wolfram ist eines der weltweit besten Mathematiker und Informatiker. Er hat eine Menge Sachen bekommt, dass Sie eher für einen guten Vorteil wieder verwenden könnten, als es selbst zu schreiben.

Sie müssen definieren, was Sie mit „lösen“ bedeuten und was Sie zurückgeschickt haben erwarten.

Es gibt symbolische Lösungen und numerische Lösungen. Welches meinst du? Beide sind gleichermaßen gültig, aber sie sind anders. Sie werden verschiedene Techniken anwenden, je nach Antwort.

Ein weiterer Punkt: Es gibt viele Techniken für die „Lösung“ Gleichungen, die viel von der Art der Gleichung abhängen. Wenn Sie mich so etwas wie f(x) = 0 geben denke ich an Wurzelfindungsalgorithmen wie Newton-Verfahren. Wenn Sie geben mir eine gewöhnliche Differentialgleichung ich eine Substitutionsmethode oder numerische Integration könnte versuchen, mit Runge-Kutta. Wenn Sie mir eine partielle Differentialgleichung geben kann ich Finite Differenzen, Finite-Elemente-oder Randelementverfahren anzuwenden. (Hören Sie mich nicht auf elliptischen, parabolischen erhalten begonnen, und hyperbolischen PDEs).

Der Punkt ist, dass Ihre Frage sehr allgemein gehalten ist, und die Antwort hängt sehr viel ab, was Sie zu tun versuchen. Weitere Einzelheiten könnten helfen.

In der Regel werden Sie den Ausdruck in eine interne Darstellung analysieren müssen. Viele lineare Algebra Bücher empfehlen die Verwendung von Matrizen (oder std::vector) die Koeffizienten zu repräsentieren. Der Exponent des Begriffs wird durch seine Position in dem Vektor definiert.

So zum Beispiel, der Ausdruck: 

 2 + 3x + 5x^2

Kann als Array oder std::vector dargestellt werden: 

std::vector<int> expression;
expression[0] = 2; // 2 * x ^ 0
expression[1] = 3;
expression[2] = 5;

Das Schreiben einer Auswertungsfunktion wird trivial, und für den Leser als Übung.

mehr Gleichungen lösen wird komplexer. Es gibt bestehende Bibliotheken und Algorithmen für diese. Eine Google-Suche sollte mit etwas Gutes kommen. : -)

Ich schlage vor, beginnend mit einfachen Begriffen und den Aufbau eines Parser dafür. Sobald das funktioniert, können Sie den Parser ändern Funktionsnamen als auch zu akzeptieren.

Wenn Sie einen Ausdruck zu vereinfachen, versuchen, die Bedingungen auf beiden Seiten des = hat, nur die Schritte aufschreiben Sie normalerweise nehmen würde, wenn sie von Hand zu lösen. Versuchen Sie, einige andere Gleichungen einige Regeln runter. Nun implementieren diese Regeln in C ++.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top