Fun-Soft - Programmierforum

Autor

Thread - Seiten: > 1 <

000
19.12.2007, 17:07 Uhr
~halloihr
Gast

Hallo zusammen
Für mein Info2 Praktikum bin ich auf der Suche nach einem Programm, dass eine Funktion (aufgeschrieben mit der polnischen Notation) einliest, die einzelnen Elemente in einen Baum schreibt und man für verschiedene x Werte das Ergebnis ausgeben lassen kann.
Warum schreib ich das nicht selbst?
Keiner aus unserem Kurs, bzw. aus den höheren Semestern hat jemals eine ähnliche Aufgabe bearbeiten müssen und wir stehen alle da wie der Ochs vorm Berg.
Wenn nicht irgentwer von uns ein ähnliches Programm auftreibt oder einen eingefleischten C++ Programmierer dürfen wir nächstes Jahr nochmal ran. Dementsprechend verzweifelt bin ich

Wenn jemand etwas ähnliches schonmal programmiert hat, wäre ich sehr sehr dankbar wenn ich mir das mal anschauen könnte. Ich habe nämlich keine Ahnung wie die Knoten erzeugt werden sollen, wie sie verknüpft werden, wie die Rechnung ansich vonstatten geht.
Wenn ich das richtig sehe, brauchen wir eigentlich nur die Schleife schreiben, die den String auswertet und Elemente in den Baum einträgt. Die Knotenklassen hat er ja vorgegeben. Aber...ich kann zu dem Programm nicht mal ne gescheite Frage stellen.
In guter Hoffnung *hust*

Epimetheus

Aufgabe:
Schreiben Sie ein Programm, das eine Funktions-Formel in Postfix-Form einliest

und hieraus einen Baum erzeugt. Danach kann der Anwender den Baum fuer ver-

schiedene Werte von x wiederholt auswerten lassen. Die Wiederholung endet bei

der Eingabe einer 0. Dabei soll aber auch fuer den Wert 0 noch einmal die Aus-

wertung erfolgen.

Die Postfix-Form soll folgende Elemente enthalten:

+ : Add

- : Sub

* : Mul

/ : Div

_ : Minus

x : X

n gefolgt von Zahl : Num

f gefolgt von Funktionsnamen : Func1

; : Kennzeichnet das Ende der Eingabe

Der auf f folgende Funktionsname soll mit jeweils einem Leerzeichen vor und

hinter dem Namen von der uebrigen Eingabe getrennt sein, damit er sicher iso-

liert werden kann.

Beispiel:

Fuer die Formel

3*sqrt(x/2)+x*sin(x)/2

lautet die Eingabe

n3xn2/f sqrt *xxf sin *n2/+;

Vorgegebener Code:

C++:

#include <stack>
#include <cmath>
#include <string>
#include <cctype>

class Knoten{
   private:
      static double x;
   public:
      static void setx(double d){x=d;}
      static double getx() {return x;}
      virtual double compute()const=0;
};
double Knoten::x;

class Knoten0:public Knoten{};

class Knoten1:public Knoten{
      protected:
         Knoten *p1;
      public:
         Knoten1(Knoten* k):p1(k){}
};

class Knoten2:public Knoten{
      protected:
           Knoten *p1,*p2;
      public:
         Knoten2(Knoten *k1,Knoten *k2):p1(k1),p2(k2){}
};

class Minus:public Knoten1{
    public:
       Minus(Knoten *k):Knoten1(k){}
       double compute()const{return-p1->compute();}
};

class Add:public Knoten2{
     public:
       Add(Knoten *k1,Knoten *k2):Knoten2(k1,k2){}
       double compute()const {return p1->compute()+p2->compute);}
};

class Sub:public Knoten2{
     public:
       Add(Knoten *k1,Knoten *k2):Knoten2(k1,k2){}
       double compute()const {return p1->compute()- p2->compute);}
};

class Mul:public Knoten2{
     public:
       Add(Knoten *k1,Knoten *k2):Knoten2(k1,k2){}
       double compute()const {return p1->compute()*p2->compute);}
};

class Div:public Knoten2{
     public:
       Add(Knoten *k1,Knoten *k2):Knoten2(k1,k2){}
       double compute()const {return p1->compute()/p2->compute);}
};

class Num:public Knoten0{
   private:
      double num;
   public:
      Num(double d):num(d){}
      double compute()const{return num}
};

class x:public Knoten0{
   public:
      double compute()const{return Knoten::getx();}
};

class Func1:public Knoten1{
    private:
       double (*f)(double);
    public:
       Func1(double g(double),Knoten *h):Knoten1(k),f(g){}
       double compute()const{return f(p1->compute())}
};

class Exp{
   private:
      Knoten *p;
   public:
      Exp(Knoten *q):p(q){}
      double operator()(double x)const{
      Knoten::setx(x);
      return p->compute();
                                      }
};

Bearbeitung von 0xdeadbeef:

cpp-tag repariert

Dieser Post wurde am 19.12.2007 um 19:29 Uhr von 0xdeadbeef editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

001
19.12.2007, 17:27 Uhr
Blubber2063

Also auf jeden Fall solltest du deine Knotenklassen die du ableitest ordentlich bennenen.
Ansonsten schau dir mal rekursive decent parser an. Text parsen(Kontextfreie Grammatiken), Abstrakten Syntax Baum generieren und den dann auswerten. Das was ihr schreiben sollt klingt ja schwer nach einem Interpreter, also einfach mal Literatur zum Compilerbau greifen.

Dieser Post wurde am 19.12.2007 um 17:27 Uhr von Blubber2063 editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

002
19.12.2007, 17:47 Uhr
~halloihr
Gast

Hi
Jop. Sowas hat der Prof auch gemeint. Auf diese Weise kann man Compiler bauen...
Das Problem was wir haben: Wir studieren E-Technik und kein Informatik. Wir haben noch nie ein Programm geschrieben in dem Klassen abgeleitet wurden, eigene Namespaces definiert wurden, virtuelle Funktionen drin vorkamen. etc.
Die Programme sollen wöchentlich abgegeben werden und ich kann mir jetzt nicht 4 Infobücher schnappen, mich die ganzen Weihnachtsferien hinsetzen und versuchen unser Problem zu lösen. Dazu haben wir zuviele andere Fächer.
Klar ist die Frage "Wie geht das?" ziemlich scheiße von mir gestellt. Aber naja...probieren kann mans. =

*würg*

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

003
19.12.2007, 19:16 Uhr
xXx
Devil

Bei solcher, noch relativ leichter Grammatik wäre evtl. wirklich das Interpreter Pattern (ein Design Pattern) geeignet.
Ansonsten kannst du dir vllt. mal spirit von boost.org angucken ...

http://en.wikipedia.org/wiki/Interpreter_pattern
www.java2s.com/Code/Java/Design-Pattern/InterpreterPatternCalculator.htm
www.exciton.cs.rice.edu/JAvaResources/DesignPatterns/intepreter.htm

nutz einfach selber google, yahoo usw.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

004
19.12.2007, 19:21 Uhr
0xdeadbeef
Gott
(Operator)

Naja, ein recursive descent parser wäre hier wohl ziemlicher Overkill, da sollte auch ein einfacher Kellerautomat reichen. Dafür ist die Postfix-Notation ja schließlich da.

Wenn x jetzt beim Parsen schon bekannt wäre - also der Ausdruck zu interpretieren wäre - wärs ja nach dem Auseinanderpfriemeln denkbar einfach. Für den Ausdruck

n3xn2/f sqrt *xxf sin *n2/+;

Sähe das etwa so aus:

Lege 3 auf den Stack, Rest xn2/f sqrt *xxf sin *n2/+;
Lege x auf den Stack, Rest n2/f sqrt *xxf sin *n2/+;
Lege 2 auf den Stack, Rest /f sqrt *xxf sin *n2/+;
Nimm zwei Elemente vom Stack, dividiere, lege das Ergebnis zurück. Rest f sqrt *xxf sin *n2/+;
Nimm ein Element vom Stack, rechne sqrt aus, lege das Ergebnis zurück, Rest *xxf sin *n2/+;
Nimm zwei Elemente vom Stack, multipliziere, lege das Ergebnis zurück, Rest xxf sin *n2/+;
Lege x auf den Stack, Rest xf sin *n2/+;
Lege x auf den Stack, Rest f sin *n2/+;
Nimm ein Element von Stack, rechne sin aus, lege das Ergebnis zurück, Rest *n2/+;
Nimm zwei Elemente vom Stack, multipliziere, lege das Ergebnis zurück, Rest n2/+;
Lege 2 auf den Stack, Rest /+;
Nimm zwei Elemente vom Stack, dividiere, lege das Ergebnis zurück, Rest +;
Nimm zwei Elemente vom Stack, addiere, lege das Ergebnis zurück, Rest ;
Prüfe, ob der Stack ein Element groß ist, wenn nicht, Fehler, wenn ja, nimm das Ergebnis vom Stack.

Aus diesem Prozess willst du jetzt, anstatt das auszurechnen, aber einen abstrakten Syntaxbaum zusammensetzen, also dir die Struktur merken. Was du am Ende haben willst, sieht etwa so aus:

Code:

           +
    .--------------.
    *              /
.------.        .------.
3     sqrt      *      2
       |      .---.
       /     sin  x
    .-----.   |
    x     2   x

Für deinen Prozess bedeutet das im Grunde, dass du dir einen Stack von Baumknoten halten musst, und anstatt die Operation, wie oben, gleich durchzuführen, du die entsprechende Anzahl Baumknoten vom Stack nimmst, einen Baumknoten mit dem Kennzeichen der entsprechenden Operation erstellst, ihm die beiden anderen Baumknoten als Kinder zuweist, und den fertigen Baumknoten wieder auf den Stack legst. Am Ende liegt dann dein Wurzelknoten auf dem Stack.
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra

Dieser Post wurde am 19.12.2007 um 19:23 Uhr von 0xdeadbeef editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

Seiten: > 1 < [ C / C++ (ANSI-Standard) ]

ThWBoard 2.73 FloSoft-Edition
© by Paul Baecher & Felix Gonschorek (www.thwboard.de)

Anpassungen des Forums
© by Flo-Soft (www.flo-soft.de)

Sie sind Besucher: