hilfe beim parsen

[partitionist]

Ich eine konsoleanwendung bei der man befehle ausführen kann, so nun möchte ich eine art taschenrechner integrieren wie beim Monad dem Nachfolger von cmd.
Dabei wird z.b. das eingeben: 5+23 oder 23-44+5.
Jetzt muss ermittelt werden das da zahlen sind und diese von den operatoren zu trennen und zu berechnen. Der folgende Code ist zum einlesen der Befehle dabei sollen rechenoperationen möglich werden, wie läßt sich sowas realisiern?

...
string str; //Eingabe String

do
{    
    //Befehl mit Parameter einlesen
    getline(cin, str);
    
    istringstream cmdline (str);
    string input;
    vector<string> params;


    if (cmdline >> input) 
    {
        string tmp;
        while (cmdline >> tmp) 
        {
            params.push_back (tmp);
        }

/*
--------------------------------------
    Eingelesene Befehle...
--------------------------------------
*/
        if(input == "Befehl_A")
        {           
        } 
        ....
}while(1);
..

 

[RedWing]

Hallo,

wenn ich dich richtig verstanden habe, möchtest du einen math. Term einlesen,
diesen parsen (also nach syntaktischer Korrektheit prüfen) und anschließend
berechnen.
Da gibts 2 Möglichkeiten:
1.) Du machst dich über "Parser Generatoren" bzw "Compiler Compiler" schlau.
Das sind Tools die dir Anhand einer bestimmten Grammatik als Eingabe einen Parser
automatisch erzeugen können.
Beispiele für diese Tools wären bspw yacc für Unixbetriebssysteme oder der Linuxclon
bison...

oder:
2.) du machst dir die plagevolle Arbeit und schreibst dir selber so ein Teil...
Siehe dazu:
http://www.tutorials.de/forum/c-c/219171-string-int.html?highlight=parser

//edit: Mit dem Begriff "Teil" meinte ich nat. nicht einen kompletten Parser für eine beliebige Sprache
sondern nur einen konkreten Parser für das berechnen eines math Termes

Gruß,

RedWing

 

[deepthroat]

Hi.

Das was RedWing beschrieben hat ist natürlich die hohe Schule. Allerdings kannst du diese Aufgabe auch etwas einfacher lösen.

Du kannst den Ausdruck auch mithilfe einer Stapelverarbeitung berechnen. Und das geht so:

Du verwendest 2 Stacks. Einen Operatoren- und einen Operandenstack.

Als erstes versuchst du den String mit einem Stringstream in eine Variable als Zahl (int bzw. double) einzulesen. Klappt das, dann pusht du den Wert auf den Operandenstack.

Danach bzw. wenn das nicht geklappt hat, muß ein Operator vorliegen den du dann einliest und auf den Operatorenstack pushen kannst.

Soweit so gut. Du mußt dann nur immer schauen ob du die Stacks eventuell reduzieren kannst oder nicht. Das hängt von der Priorität der Operatoren ab.

Beispiel: "3+4*5-1"

Wenn du den Ausdruck mit der Methode liest, dann pusht du erst die 3 auf den Operandenstack, dann das Plus auf den Operatorenstack, die 4 wieder auf den Operandenstack. Dann liest du als Operator das Sternchen ein. Diesen Operator vergleichst du mit dem Operator ganz oben auf dem Operatorenstack und wenn dieser eine Priorität größer oder gleich dem gerade gelesenen Operator hat, dann kannst du reduzieren indem du die Operation ausführst.

In diesem Fall hat das Sternchen - also die Multiplikation - eine höhere Priorität als das Plus auf dem Operatorenstack und man kann leider nicht reduzieren; Punktrechnung geht eben vor Strichrechnung.

Also auch das Sternchen auf den Operatorenstack pushen und dann die 5 auf den Operandenstack.

Danach lesen wir das Minus und vergleichen es sogleich mit dem Operator oben auf dem Operatorenstack und stellen fest, dass diesmal das Minus klar eine niedrigere Priorität hat als das Sternchen. Wir können also reduzieren. Dazu poppen wir die obersten 2 Werte vom Operandenstack (also die 4 und die 5) und auch das Sternchen wird vom Operandenstack entfernt. Dann führen wir die Operation aus und pushen das Ergebnis wieder auf den Operandenstack.

Das Ganze machen wir solange wie der Operator auf dem Operatorenstack eine Priorität größer oder gleich dem gelesenen Operator hat. Da Plus und Minus die gleiche Priorität haben, können wir also nochmal reduzieren. Wir pushen die 3 und die 20 vom Stack, entfernen auch das Plus vom Operatorenstack und pushen das Ergebnis der Operation wieder auf dem Operandenstack zurück.

Jetzt ist der Operatorenstack leer, wir können also nicht mehr weiter reduzieren. Das heißt das Minus kommt jetzt oben auf den Operatorenstack.

Nachdem die 1 gelesen und auch auf den Operandenstack gewandert ist stellen wir fest das die Eingabe zu Ende ist. Jetzt müssen wir solange reduzieren bis der Operatorenstack leer ist. Das Ergebnis vom Ausdruck steht dann als einziger Wert noch auf dem Operandenstack, in diesem Fall also 22.

Gruß

 

[jokey2]

Ist auch nicht schlecht, die Lösung, allerdings, wenn der Term Klammern enthält, wird's schon deutlich komplizierter. Vor Allem, wenn auch noch mehrere Klammern geschachtelt sind.
Da müßtest Du erst den gewsamten Klammerausdruck einlesen und ihn mit einem eigenen Stack behandeln. Und das für jede Klammerebene.

 

[deepthroat]

Ja, da hast du schon Recht: bei Klammern wird's kompilizierter. Eigentlich ist ja so eine Klammer kein Operator und der Term im Inneren wie ein eigener Ausdruck zu behandeln.

Allerdings kann man das auch als Spezialfall behandeln und eine öffnende Klammer mit auf den Operatorenstack pushen. Dann muß man immer wenn man auf eine schließende Klammer trifft solange reduzieren bis man die dazugehörige öffnende Klammer erreicht hat. Auf diese Weise benötigt man nicht unbedingt noch weitere Stacks und kann den Ausdruck sequentiell verarbeiten.

Gruß