[C++] Auswertung algebraischer Ausdrücke

[dabu]

Folgendes Problem habe ich:

In einem String speichere ich einen algebraischen Ausdruck ab, z. B.:
5+7*(3+4)

Jetzt habe ich das Problem, dass ich nicht weiß, wie ich es hinbekomme, dass es mir das Ergebnis dieser Rechnung anzeigt. Ich kann zwar Zeichen für Zeichen durchgehen, aber irgendwie bekomme ich kein Programm zusammen, das mir das Ergebnis berechnet. Vor allem müssen ja die Klammern und Punkt vor Strich beachtet werden .

Hat jemand eine Ahnung, wie man dieses Problem lösen könnte? Über Hilfe wäre ich sehr dankbar !

 

[Johnson]

Hi,

nach allem, was ich eben über Google gefunden habe gibt es bei nicht-Interpreter-Sprachen wie z.B. c++ und java kein eval() Equivalent.

Was ich eventuell Interessantes dazu gefunden habe (über das gleiche Problem in Java):

https://www.chip.de/c1_forum/thread.html?bwthreadid=874995

Gruß

 

[dabu]

Das mit dem StringTokenizer ist eine klasse Idee, allerdings kann ich damit nicht wirklich etwas anfangen, weil ich bei Google kaum Infos dazu finde. Zumindest nicht für C++, für Java gibt es jede Menge. Mir fehlen nämlich die Infos, was ich dazu alles includen mus etc .

 

[BFabian]

Wenn du es von Hand machen willst, ist die Idee folgende:
5+7*(3+4) als Baum darstellen:

                     +
                    / \
                  5   *
                      / \
                     7   +
                        / \
                       3   4

Um das zu erreichen, musst du einen primitiven Parser schreiben, der dir den String in die einzelnen Tokens zerlegt und anschließend die Operatoren der Reihe nach im Baum anordnet. Die Zahlen sind am Ende Blätter. Die Auswertung geht dann vom tiefsten Knoten nach oben.

Wenn du es so machen willst, kann ich dir zumindest für das Zerlegen Code geben (den ich gerade nicht greifbar habe). Die Alternative wäre, eine passende Bibliothek zu wählen, da dürfte google aber mehr drüber wissen.

 

[SvenF311]

Rekursive Programmierung! Schreibe dir 'ne Funktion

double solveEquation(char *szEquation, int iNumChars)

In dieser Funktion durchsuchst du den String zunächst nach der ersten öffnenden Klammer. Wenn du dann auch die entsprechenden schließende Klammer gefunden hast, kannst du den String zwischen den Klammern erneut an die Funktion "solveEquation" übergeben. Mit dem Wert, den die Funktion zurückliefert kannst du dann einen neuen "vereinfachten" String aufbauen. Das wiederholst du, bis der String keine Klammern mehr enthält.

Wenn der String keine Klammern enthält, suchst du nach dem ersten Zeichen für die Punktrechnung '*' oder '/' und bestimmst die beiden Zahlen davor und dahinter. Aus diesen berechnest du das Ergebnis und baust wieder 'nen neuen String auf. Das wiederholst du, bis der String keine Punktrechnungen mehr enthält.

Für die Strichrechnung folg das gleiche Spiel. Den ersten '+' oder '-' Operator suchen, aus den Zahlen davor und danach das Ergebnis berechnen, es in den String einsetzen und nach dem nächsten Operator suchen.

solveEq( "5+7*(3+4)" )
-> Klammern suchen: true
-> solveEq( "3+4" )
---> Klammern suchen: false
---> Punktrechnung suchen: false
---> Strichrechnung suchen: true
---> Ergebnis berechnen 3 + 4 => 7
-> Ergebnis einsetzen, neuer String "5+7*7"
-> Klammern suchen: false
-> Punktrechnung suchen: true
-> Ergebnis berechnen und einsetzen, neuer String "5+49"
-> Strichrechnung suchen: true
-> Ergebnis berechnen und einsetzen, neuer String "54"
54

Ist vielleicht ein wenig ekelig, mit dem dauernden Suchen, Konvertieren und Einsetzen. ABER du kannst nachher sehr anschaulich die Zwischenschritte darstellen; Halt, wie du's auf dem Papier rechnen würdest ...

MfG
Sven