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

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

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

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.

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