Weis jemand, wie man mathematische Ausdrücke in C++ auswert

[bernd (Gast)]

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

[Timmo H. (masterfx)]

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.

[manu (Gast)]

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

[bernd (Gast)]

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();

[bernd (Gast)]

@ 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?

[Orakel (Gast)]

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

[Karl H. (kbuchegg)]

> 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.

[Karl H. (kbuchegg)]

Ein Beispiel für einen 'rekursiven Abstieg' der einen
einfachen Taschenrechner realisert, findest du zb hier:
http://www.willemer.de/informatik/compiler/bspcalc.htm

[bernd (Gast)]

Ok,

danke erst mal an alle, ich muss mich da jetzt erst mal etwas
einarbeiten.

Grüße,
Bernd

[Johnny (Gast)]

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.

[yalu (Gast)]

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

[yalu (Gast)]

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

[bernd (Gast)]

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

[Christoph Peters (Gast)]

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

[Christoph Peters (Gast)]

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

[Karl heinz B. (kbucheg)]

> 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.

[DUMMI (Gast)]

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?

#include <stdio.h>
#include <ctype.h>

class Eval {
  public:
    int eval(char *expr);
    int sum();
    int prod();
    int factor();
    int number();
  private:
    void eatspace();
    char cur() { return *m_cptr; }
    void next();
    char *m_cptr;
};

void Eval::eatspace() {
  // überliest Spaces, Tabs usw.
  while(isspace(*m_cptr))
    m_cptr++;
}

void Eval::next() {
  // liest nächstes Zeichen aus Eingabe
  m_cptr++;
  eatspace();
}

int Eval::eval(char *expr) {
  // wertet kompletten Ausdruck aus
  m_cptr = expr;
  eatspace();
  return sum();
  if(cur())
    throw 1;
}

int Eval::sum() {
  // wertet Summe (evtl. mit 0 Summanden) aus
  int res = prod();
  for(;;) {
    if(cur() == '+') {
      next();
      res += prod();
    }
    else if(cur() == '-') {
      next();
      res -= prod();
    }
    else
      break;
  }
  return res;
}

int Eval::prod() {
  // wertet Produkt (evtl. mit 0 Faktoren) aus
  int res = factor();
  for(;;) {
    if(cur() == '*') {
      next();
      res *= factor();
    }
    else if(cur() == '/') {
      next();
      res /= factor();
    }
    else
      break;
  }
  return res;
}

int Eval::factor() {
  // wertet Faktor (Klammerausdruck, negierter Ausdruck oder Konstante aus
  int res;
  switch(cur()) {
    case '(':
      next();
      res = sum();
      if(cur() == ')')
        next();
      else
        throw 2;
      break;
    case '-':
      next();
      res = -factor();
      break;
    default:
      if(isdigit(cur()))
        return number();
      else
        throw 3;
  }
  return res;
}

int Eval::number() {
  // wertet Integerzahl in Dezimaldarstellung aus
  int res = 0;
  while(isdigit(cur())) {
    res = 10 * res + cur() - '0';
    next();
  }
  return res;
}

int main() {
  Eval ev;
  char line[1023];
  int res, err;

  fgets(line, sizeof line, stdin);
  try {
    res = ev.eval(line);
  }
  catch (int err) {
    printf("error %d\n", err);
    return 1;
  }
  printf("%d\n", res);
  return 0;
}

[Sven P. (Gast)]

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

[yalu (Gast)]

@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.

[Tobias P. (hubertus)]

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.

[Yalu X. (yalu) (Moderator)]

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).

[Sebastian S. (amateur)]

Habt Ihr denn würglich keinen Respekt vor den Toten?

[Tobias P. (hubertus)]

Danke @Yalu, die Funktion power() hatte ich auch schon, war mir aber 
überhaupt nicht sicher wie es denn nachher weiter gehen soll :-)
echt cool!

[Tobias P. (hubertus)]

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.

[Duck&wech (Gast)]

In vernünftigen, nicht im Laufe von Bastlergenerationen 
zusammengefrickelten Programmiersprachen gibt es dafür eine 
eval-Funktion.
https://en.wikipedia.org/wiki/Eval

[Tobias P. (hubertus)]

Stimmt, Javascript ist eine extrem vernünftige Programmiersprache. Es 
ist mindestens so vernünftig wie dein Kommentar qualifiziert ist.

[Rufus Τ. F. (rufus)]

Das lässt sich mit PHP noch steigern ...

[(prx) A. K. (prx)]

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.