Hallo, hat jemand von Euch einen Tip, wie man mathematische Ausdrücke die als String vorliegen "12+3*(5-3)" auswertet und am Ende als int(C++) vorliege hat. Danke, Bernd
Vorgefertigte Funktionen gibt es meines Wissen nach nicht. Aber zunächst hast du den String ja in einem Array vorliegen. Ich würde jetzt das Array an den mathematischen Symbolen (+,-,*,/,(,)) zerteilen und erstmal die Zahlen in int umwandeln (atoi oder so) und dann der Reihe nach die entsprechenden Berechnungen durchführen. Wichtig ist hier natürlich dass du auch die Reihenfolge der Berechnungen einhälst. Ganz einfach ist das glaub ich nicht.
Das Stichwort hier heisst "Auswertung von Infix-Ausdrücken" Konkret wandelt man den gegebenen Infix-Ausdruck in einen Postfix-Ausdruck um und wertet diesen dann aus. Anhand von deinem Beispiel: "12+3*(5-3)" -> 12 3 5 3 - * + => 18 cheers Literatur: http://www.igi.tugraz.at/lehre/D&A/WS05/Folien/ElementareDatenstrukturen.pdf http://www.vs.inf.ethz.ch/edu/SS2000/I2/folien/Vorl_Info2_SS00_3.pdf http://www.vs.inf.ethz.ch/edu/SS2000/I2/folien/Vorl_Info2_SS00_4.pdf
Hi, danke, ich werde mir die Links mal ansehen. @manu: So wie Du es im Beispeil hast, habe sich schon eine Routine, aber: Wenn ich z.B. 2*3+4 nehme folgt: 2 3 4 + * => 14 anstatt 10 Hier der Code: Find(n) liefert einen NULL terminierten String. cs ist ein STL stack<int> cs Klammern werden ja berücksichtigt, aber die Reihenfolge der Verknüpfungen + * werden nicht berücksichtigt. int x; char c; char* s=Find(n); char* v=s; int len=strlen(s); while (!cs.empty()) cs.pop(); char a[1024]; char* b=a; for (;*s!=0; ) { c=*s++; if ( c==')' ) {*b++=(char)cs.top();cs.pop();} else if ( c=='+' ) cs.push ((int) c); else if ( c=='*' ) cs.push ((int) c); else if ( c>='0' && c<='9') { *b++=c; if ( c!='(' ) *b++=' '; } } while (!cs.empty()) {*b++=cs.top(); cs.pop();} *b++=0; len = strlen (a); s=a; for (;s<a+len;) { x=0; c=*s++; if (c=='+') { int x1, x2; x1=cs.top(); cs.pop(); x2=cs.top(); cs.pop(); cs.push(x1+x2); } else if (c=='*') { int x1, x2; x1=cs.top(); cs.pop(); x2=cs.top(); cs.pop(); cs.push(x1*x2); } else if (c>='0' && c<='9') { while (c>='0' && c<='9') { x= 10*x + (c-'0'); c=*s++; } cs.push(x); } } x= cs.top(); cs.pop();
@ manu Auf der ersten Folie steht: 3. Operator Alle Operatoren mit gleicher oder höherer Priorität vom Stapel ausgeben, bis ( erreicht oder Stapel leer. Wie kann ich den alle operatoren mit gleicher oder höherer Priorität verarbeiten, wenn oben auf dem Stack ein Operator mit niedrieger Prio liegt?
alles overkill ... ich würde mich erstmal fragen ob das in C++ sein muss? Wenn ja, würde ich nach einer Bibliothek suchen (es muss was geben) Falls nein, dann eventuell Python, Ruby, Perl, awk, bc, und und und zu hilfe ziehen. Und sei es durch char expr[256]; snprintf(expr, 256, "script.py %s", getExpressionFromUser()); system(expr) oder FILE * result = popen(expr); fread(expr); so aus dem Gedächtniss, schaue Dir die Parameter genauer an. hth
> alles overkill ... Da geb ich dir recht. > Wenn ja, würde ich nach einer Bibliothek suchen > (es muss was geben) Sowas kann man elegant mit 'Compiler-Compiler'-n erledigen. Als zb. lex und yacc, oder aber meinen Liebling COCO oder aber ... (Compiler-Compiler gibts wie Sand am Meer). > char expr[256]; > snprintf(expr, 256, "script.py %s", getExpressionFromUser()); > system(expr) > > oder > > FILE * result = popen(expr); > fread(expr); Was soll das alles bringen? Damit bist du extrem davon abhängig auf welchem OS das Ding läuft. An den OP: Wenn du das selbst programmieren willst, gibts neben der Stack-Technik auch noch die Möglichkeit des 'rekursiven Abstiegs'. Wenn du den erstmal verstanden hast, hast du ein prima Werkzeug, um damit unter anderem Command-Line-Interfaces, Text-Datei-Format-Leser oder eben Expression-Parser zu bauen. Einige Compiler-Compiler (unter anderem COCO) können auch rekurisive Abstiegscompiler erzeugen. Ich bevorzuge sie, weil sie einfacher zu debuggen sind, als die Tabellen-Parser die lex&yacc erzeugen.
Ein Beispiel für einen 'rekursiven Abstieg' der einen einfachen Taschenrechner realisert, findest du zb hier: http://www.willemer.de/informatik/compiler/bspcalc.htm
Ok, danke erst mal an alle, ich muss mich da jetzt erst mal etwas einarbeiten. Grüße, Bernd
Ich würde eine fertige Library wie UCalc benutzen: http://www.ucalc.com/ucalcfmp.html Hatte das mal in einem Delphi Projekt eingebaut und hat sehr einfach, zuverlässig und schnell funktioniert. Sowas selber zu realisieren ist halt sehr aufwändig wenn es dann wirklich auch noch alle Regeln wie Punkt- vor Strichoperationen, Klammern und dergleichen beherrschen soll.
Wenn für Dich Integerberechnungen ausreichend sind, kann Dir das kleine C++-Programm im Anhang weiterhelfen. Es kann beliebige Ausdrücke mit den vier Grundrechenarten (+,-,*,/), Zahlen in Dezimaldarstellung, dem Negationszeichen (-) und Klammerausdrücken auswerten. Die "Punkt- vor Strich"-Regel wird befolgt und überflüssige Leerzeichen und Tabs aus dem Eingabestring entfernt. Beispiel: (33 + 44 * -3) * (3 + 4 * -(5 + 6)) --> 4059 Soll das ganze auch für gebrochene Zahle funktionieren, musst Du im Wesentlichen den Typ der int-Methoden und der res-Variablen in double ändern und die Methode number erweitern, dass sie auch Dezimalpunkte und evtl. das Exponentzeichen 'e' erkennt und entsprechend auswertet. Das Programm ist etwas quick&dirty (gerade eben reingehackt), hat aber bei mir ganz gut funktioniert (gcc 4.0.2). Das Funktionsprinzip ist übrigens der schon angesprochene rekursive Abstieg. yalu
Nachtrag: So war das natürlich Müll: Die Fehlerbehandlung (throw 1) bei invaliden Zeichen am Ende des Ausdruck funktioniert nicht, da sie hinter dem return-Statement steht. Hier ist die korrigierte Version. yalu
Hallo, Interger reichen mir eigentlich. Ist ja recht einfach gestickt (wenn man weiß wie :-=). Werden das ganze dann noch um Schiebe- und Bitoperationen erweitern. Dann habe ich was ich brauche. Danke vielmals, Bernd
Ein sehr gutes und verbreitetes Verfahren ist es, rekursiv einen Binärbaum des Ausdrucks aufzubauen. Wie das geht sieht man im Angang (pdf und javaquellcode). War ne Aufgabe im Programmierpraktikum. Ist mehr als gut Kommentiert und lesbar und müsste, ausgenommen einiger Syntaxänderungen, 1:1 in C++ übernommen werden können. wenn noch fragen sind, dann immer her damit. Könnt euch sicher sein, dass der Quelltext nahezu fehlerfrei ist, habe dafür keine Punkte abgezogen bekommen. viel spaß damit christoph
Ein sehr gutes und verbreitetes Verfahren ist es, rekursiv einen Binärbaum des Ausdrucks aufzubauen. Wie das geht sieht man im Angang (pdf und javaquellcode). War ne Aufgabe im Programmierpraktikum. Ist mehr als gut Kommentiert und lesbar und müsste, ausgenommen einiger Syntaxänderungen, 1:1 in C++ übernommen werden können. wenn noch fragen sind, dann immer her damit. Könnt euch sicher sein, dass der Quelltext nahezu fehlerfrei ist, habe dafür keine Punkte abgezogen bekommen. viel spaß damit christoph
> Ein sehr gutes und verbreitetes Verfahren ist es, rekursiv einen > Binärbaum des Ausdrucks aufzubauen. Yep. Von dort kann man dann weitergehen und den Baum durch diverse Transformationen laufen lassen, bevor man ihn auswertet. zb. Vereinfachung oder was auch immer wieder ein beliebtes Beispiel ist: symbolisch differenzieren.
Hi , ich brauche einen einfachen Formelparser . der Parser von „yalu“ aus diesem Beitrag(s. eval.cpp) gefällt mir schon ganz gut ,bloß wie kann man da jetzt noch „sqrt“ und „sin“ bzw. „cos“ integrieren ? blickt da Jemand durch ? ich kriege es nicht hin. Wer kann helfen?
1 | #include <stdio.h> |
2 | #include <ctype.h> |
3 | |
4 | class Eval { |
5 | public:
|
6 | int eval(char *expr); |
7 | int sum(); |
8 | int prod(); |
9 | int factor(); |
10 | int number(); |
11 | private:
|
12 | void eatspace(); |
13 | char cur() { return *m_cptr; } |
14 | void next(); |
15 | char *m_cptr; |
16 | };
|
17 | |
18 | void Eval::eatspace() { |
19 | // überliest Spaces, Tabs usw.
|
20 | while(isspace(*m_cptr)) |
21 | m_cptr++; |
22 | }
|
23 | |
24 | void Eval::next() { |
25 | // liest nächstes Zeichen aus Eingabe
|
26 | m_cptr++; |
27 | eatspace(); |
28 | }
|
29 | |
30 | int Eval::eval(char *expr) { |
31 | // wertet kompletten Ausdruck aus
|
32 | m_cptr = expr; |
33 | eatspace(); |
34 | return sum(); |
35 | if(cur()) |
36 | throw 1; |
37 | }
|
38 | |
39 | int Eval::sum() { |
40 | // wertet Summe (evtl. mit 0 Summanden) aus
|
41 | int res = prod(); |
42 | for(;;) { |
43 | if(cur() == '+') { |
44 | next(); |
45 | res += prod(); |
46 | }
|
47 | else if(cur() == '-') { |
48 | next(); |
49 | res -= prod(); |
50 | }
|
51 | else
|
52 | break; |
53 | }
|
54 | return res; |
55 | }
|
56 | |
57 | int Eval::prod() { |
58 | // wertet Produkt (evtl. mit 0 Faktoren) aus
|
59 | int res = factor(); |
60 | for(;;) { |
61 | if(cur() == '*') { |
62 | next(); |
63 | res *= factor(); |
64 | }
|
65 | else if(cur() == '/') { |
66 | next(); |
67 | res /= factor(); |
68 | }
|
69 | else
|
70 | break; |
71 | }
|
72 | return res; |
73 | }
|
74 | |
75 | int Eval::factor() { |
76 | // wertet Faktor (Klammerausdruck, negierter Ausdruck oder Konstante aus
|
77 | int res; |
78 | switch(cur()) { |
79 | case '(': |
80 | next(); |
81 | res = sum(); |
82 | if(cur() == ')') |
83 | next(); |
84 | else
|
85 | throw 2; |
86 | break; |
87 | case '-': |
88 | next(); |
89 | res = -factor(); |
90 | break; |
91 | default:
|
92 | if(isdigit(cur())) |
93 | return number(); |
94 | else
|
95 | throw 3; |
96 | }
|
97 | return res; |
98 | }
|
99 | |
100 | int Eval::number() { |
101 | // wertet Integerzahl in Dezimaldarstellung aus
|
102 | int res = 0; |
103 | while(isdigit(cur())) { |
104 | res = 10 * res + cur() - '0'; |
105 | next(); |
106 | }
|
107 | return res; |
108 | }
|
109 | |
110 | int main() { |
111 | Eval ev; |
112 | char line[1023]; |
113 | int res, err; |
114 | |
115 | fgets(line, sizeof line, stdin); |
116 | try { |
117 | res = ev.eval(line); |
118 | }
|
119 | catch (int err) { |
120 | printf("error %d\n", err); |
121 | return 1; |
122 | }
|
123 | printf("%d\n", res); |
124 | return 0; |
125 | }
|
Zumindest unter Linux gibts eine "wordexp"-Funktion in der C-Bibliothek, die man für sowas missbrauchen kann: http://www.gnu.org/software/libc/manual/html_node/Word-Expansion.html
@DUMMI: > der Parser von „yalu“ aus diesem Beitrag(s. eval.cpp) gefällt mir > schon ganz gut ,bloß wie kann man da jetzt noch „sqrt“ und „sin“ > bzw. „cos“ integrieren ? Das Eval-Klasse war eigentlich eher als Beispiel gedacht, wie so etwas prinzipiell aufgebaut wird. Der Nutzen war allein schon dadurch eingeschränkt, dass man nur mit Integer-Zahlen rechnen konnte. Ich habe sie nun etwas erweitert, so dass man auch sinnvollere Dinge damit anstellen kann. Die Neuerungen: - Alle Berechnungen werden in Gleitkommaarithmetik durchgeführt. - Entsprechend werden in der Eingabe Gleitkommakonstanten (in C-Syntax) akzeptiert. - Symbolische Konstanten (pi und e) werden in ihre numerischen Äquivalente umgesetzt. - Es werden die wichtigsten mathematischen Funktionen (sin, cos, tan, asin, acos, atan, sinh, cosh, tanh, asinh, acosh, atanh, exp, log, log2, log10, sqrt, cbrt, fabs, ceil, floor, round, atan2, pow, hypot, fmod) ausgwertet. Die Namen entsprechen denen in der C-Bibliothek. Man kann nun also auch Ausdrücke wie den folgenden berechnen lassen: 4.3 + atan2(sin(-1.2e-14 + 2/e), 2 * sqrt(5.8)) Der Code ist nur wenig getestet. Falls jemand Fehler findet, bitte einfach hier melden.
Hey yalu, hast du eine schlaue Idee, wie man den Potenzoperator mit ^ umsetzen könnte? ich überlege grade, wie man den in prod() einbauen könnte.
Der Potenzoperator ^ bindet stärker als * und /. Also schreibt man dafür am besten eine eigene Methode power(), die von prod() aufgefufen und ihrerseits basexp() (ersetzt das bisherige factor()). Die Behandlung der Vorzeichen + und - (bisher in factor()) geschieht nun in power(), damit, wie in den meisten Programmiersprachen üblich, der Potenzoperator stärker bindet als die Vorzeichen. -3^2 ist also gleichbedeutend mit -(3^2). Zu beachten ist auch die Rechtsassoziativität der Potenzoperation, 2^3^4 ist also gleichbedeutend mit 2^(3^4).
:
Bearbeitet durch Moderator
Habt Ihr denn würglich keinen Respekt vor den Toten?
Danke @Yalu, die Funktion power() hatte ich auch schon, war mir aber überhaupt nicht sicher wie es denn nachher weiter gehen soll :-) echt cool!
Hallo hallo nochmals, vielleicht kann es jemand gebrauchen: ich habe den code aufgebohrt, sodass konsequent mit komplexen Zahlen gerechnet wird. Ein paar neue Funktionen habe ich eingebaut (zB. nthroot, wie in Matlab) sowie die ganzen Rechenoperationen für komplexe Zahlen (Arcus, Betrag, Re, Im usw.). Eingabe erfolgt z.B. als 10 + 8i. Es werden i und j akzeptiert. Diese sind auch als 'Konstanten' hinterlegt. Funktionen wie atan2 funktionieren nur mit reellwertigen Argumenten.
In vernünftigen, nicht im Laufe von Bastlergenerationen zusammengefrickelten Programmiersprachen gibt es dafür eine eval-Funktion. https://en.wikipedia.org/wiki/Eval
Stimmt, Javascript ist eine extrem vernünftige Programmiersprache. Es ist mindestens so vernünftig wie dein Kommentar qualifiziert ist.
Das lässt sich mit PHP noch steigern ...
Orakel schrieb: > Falls nein, dann eventuell Python, Ruby, Perl, awk, bc, und und und > zu hilfe ziehen. Und sei es durch So mancher Webseitenprogrammierer mit PHP denkt ähnlich. Wenn das dann nicht nur in sehr eingeschränkter Umgebung verwendet wird, dann gibts ein scheunentorgrosses Sicherheitsleck, weil der Anwender des Programms bzw. der Webseite vollen Durchgriff auf alle Python/Ruby/... Möglichkeiten hat.
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.