Hilfe bei Auflösung eines mathematischen Ausdrucks...
-
Hallo erstmal, ich habe eine Aufgabe bekommen einen mathematischen Ausdruck welcher als string deklariert wird, so aufzulösen das am ende das Ergebnis stimmt.
Hier ein Beispiel string:"5x7+(8/2+(9*9)-7)+1"Nun habe ich mir schon einige Gedanken gemacht, wie man so einen string parsen sollte. Also zur Mathematik: Punk- vor Strichrechnung, Klammern werden zuerst abgearbeitet. Ich hatte vor nach dem tiefsten Klammerpaar zu suchen, diesen Ausdruck würde ich dann berechnen und dann immer weiter nach außen arbeiten.
1) (9*9) 2) (8/2+(9*9)-7) => (8/2+[b]81[/b]-7) 3) 5x7+(8/2+(9*9)-7)+1 => 5x7+[b]78[/b]+1Ich glaub mein Ansatz ist nicht falsch, aber wenn ich von innen nach außen arbeite, wie wo soll ich die ergebnisse platzieren, soll es Rekursiv durchlaufen usw.
Wie würde ihr das realisieren?
-
Du willst also einen Mathe-Parser schreiben? Für sowas sollte man sich mit dem Thema Compilerbau außeinandersetzen. Leider ist dieses Thema nicht ganz ohne... Mit der Rekursion liegst du übrigens sehr richtig. Fang erstmal mit einfachen Dingen an: "5+(5*3)/2-4*(6-5)"
Anschließend kannst du dann versuchen Variablen einzubauen...
int sum() { int res = factor(); while (zeichen == '+' || zeichen == '-') { switch (zeichen) { case '+': res += factor(); break; case '-': res -= factor(); break; } return res; }usw.... Bis zur Zahl...
-
Deine Problemstellung lässt sich in zwei "Unterprobleme" aufteilen, für die du eine Lösung finden musst:
1.) Parsen des eingegebenen Textes
2.) Berechnen des ErgebnissesIch denke hier ist das Parsen der Eingabe nicht das große Problem. Ich selbst habe einmal einen kleinen Taschenrechner programmiert, des die Grundrechenarten sowie Klammerausdrücke und Vorzeichenwechsel beherrscht.
Der Taschenrechner hat dabei mit einem Operator- und einem Operandenstapel gearbeitet. Die Wikipedia kann das allerdings besser erklären: http://de.wikipedia.org/wiki/Stapelspeicher#Postfixnotation
-
Ich hab vor nicht allzu langer Zeit mal sowas geschrieben, vllt. hifts dir, 'nen Blick auf den Code zu werfen. Sind weniger als 300 Zeilen, allerdings ist der Code ein bisschen lang geworden, seit ich Funktionen (log, sin, exp, ...) und Variablendeklarationen eingebaut hab: http://bluetiger.bauchlandung.org/download/bleeding_edge/calc.tar.bz2
Die eigentliche Funktionsweise sollte aber klar sein: du machst es genau so wie sadasdas es beschrieben hat.
Wenn du es wirklich korrekt machen willst, stellst du dir erstmal eine "Grammatik" auf, d.h. du ueberlegst dir, was fuer Ausdruecke es ueberhaupt gibt. Fuer einen einfachen Taschenrechner koennte die z. B. so aussehen (in http://de.wikipedia.org/wiki/Erweiterte_Backus-Naur-Form ) :
EXPRESSION = TERM { '-' Term | '+' Term} // ein Ausdruck ist ein Term und dann Beliebig oft entweder "+ TERM" oder "- TERM" TERM = FACTOR { '*' TERM | '/' FACTOR} // ein Term setzt sich aus Faktoren und dann beliebig oft "* FACTOR" oder "/ FACTOR" zusammen. FACTOR = number | '(' EXPRESSION ')' // ein FACTOR ist entweder eine nummer oder ein geklammerter Ausdruckdas ganze auszuprogrammieren ist dann auch ganz einfach, fuer die "Expression" z. B. so:
double Parser::expression(istringstream& s) { double val = term(s); while ('+' == s.peek() || '-' == s.peek()) { char c = s.get(); switch (c) { case '+': val += term(s); break; case '-': val -= term(s); break; default: throw runtime_error(string("invalid expression (unknown op") + c + ")"); } } return val; }
-
Hab was interessantes gefunden:
-
-
Mit Boost dann auch noch anders möglich, boost::spirit ist ein parser-Framework, nimmt dir ein wenig Arbeit ab...:
http://www.oreillynet.com/network/2003/05/06/examples/calculatorexample.html
(oder im examples/ Directory der sources von spirit...