Klammer-Parser

Hallo zusammmen,
ich muss fürs ein Projekt einen kleinen Formelparser schreiben und habe mir überlegt erst einmal eine Klasse zu schreiben die mir einen String in Klammerebenen hierarchisch zerlegt um dann später nur noch simple Terme zu erhalten. Keine Angst: Ich will nicht dass einer meine Hausaufgaben macht...ich brauche nur Anregungen und Denkansätze .

x^2+(1+2+3)-(3*(4+5*(3*x)))

wird also zu:

x^2+ _____ - ___________
     1+2+3   3* ________
                4+5* ___
                     3*x

Mein Problem ist: Ich finde keinen Punkt an dem ich anfangen soll. Wie muss ich die Parserfunktion aufbauen um das ganze in eine Baumstruktur zu bekommen? Wär nett wenn ihr mir dabei ein wenig mit Rat und Tat zur Seite stehen könntet. Hoff' dass ihr versteht was ich meine.

Danke für eure Bemühungen,

Olli

*aleph_0

Willst du unbedingt zuerst einen Baum aufbauen? Wenn nein, kannst du dir die Beispiele von http://research.att.com/~bs oder http://spirit.sourceforge.net anschauen. Bei letzterem kannst du deine Grammatik elegant in C++ mit einer der EBNF ähnlichen Syntax eingeben!

Jester

Deine Idee das in lauter Teile zu zerlegen klingt doch schonmal garnicht schlecht. Klingt vielleicht auch etwas rekursiv... möglicherweise ist es garnicht so viel Arbeit.

Zum zerlegen in Teile kann ich Dir zumindest mal folgenden Tip geben: Orientiere Dich an den schließenden Klammern! Wenn eine Klammer schließt, dann kannst Du von dort aus nach links bis zur nächsten sich öffnenden Klammer lesen und Du hast einen kompletten Ausdruck gefunden, der in einer Klammer steht. Findest Du erst wieder eine schließende Klammer, dann warst Du nicht ganz innen... Du mußt also von innen heraus arbeiten. Am besten liest Du die Eingabe von Links nach Rechts und bei jeder schließenden Klammer parst Du den vorangehenden Ausdruck ohne Klammern. Auf die Art und Weise erwischst Du alle Ausdrücke.
Aufpassen mußt Du dabei allerdings mit so Sachen wie Punkt vor Strich, nicht daß Du das falsch in Deinen Baum einsortierst.

MfG Jester

Bashar

Suchstichwort: Rekursiver Abstiegsparser (bzw. recursive descent parser). Das dürfte das einfachste sein. Im Struppi ist übrigens auch einer drin.

entelechie

ich hab mal einen in C++ geschrieben, der sich an dem von b. stroustrup
anlehnt.
falls du ihn dir anschauen willst, schau auf meiner seite vorbei
(unter parser).

Vielen Dank euch allen. Ihr habt mir echt weiter geholfen . Ich gucke mir die Sachen mal an.