boolschen Ausdruck parsen??



  • Hallo Leute,

    angenommen, ich habe so einen String als Input:

    "a and b or (c and (d or e))"
    

    Ich muß a,b,c,d,e da "rausholen", be- bzw. verarbeiten und die numerischen Einzelergebnisse entsprechend dem Ausdruck verknüpfen.

    Irgendwie hab ich gerade gar keinen Plan, wie man da ran gehen kann 😕 😕 😕

    Kann mir jemand aufhelfen?



  • Mache es mit strtok.

    char string[] = ""a and b or (c and (d or e))";
    char trenn[]   = " ,()";
    char *token;
    
    void main( void )
    {
       token = strtok( string, trenn );
       while( token != NULL )
       {
          cout<<token<<endl;
          token = strtok( NULL, trenn );
       }
    }
    

    Du erhällst als Ausgabe
    a
    and
    b
    or
    ...



  • daishi schrieb:

    Mache es mit strtok.
    Du erhällst als Ausgabe
    a
    and
    b
    or
    ...

    Hm. Und wie mach ich das mit den verschachtelten Klammern??? Den String einfach auseinanderzunehmen reicht wohl nicht, ich muß ja den logischen Zusammenhang der Verknüpfung wahren.



  • Toll! Und die Klammern sind dann weg.

    Bini: Google mal nach Top-Down-Parser oder Recursive-Descent-Parser.



  • Ey Older, du hast schon mehr als 6000 beiträge?

    OIDA! 🕶 🕶 🕶 🕶 🕶 🕶 🕶 🕶 🕶 🕶



  • Bashar schrieb:

    Bini: Google mal nach Top-Down-Parser oder Recursive-Descent-Parser.

    Hm, hab ich gemacht. Aber - um ganz ehrlich zu sein - das trägt eher noch zur Verwirrung bei. Ich mach erst seit kurzem C++ und hab auch kein Informatik studiert 😞
    Hast Du vielleicht einen konkreteren Tipp?!



  • Nein, leider nicht. Parsen ist nunmal nicht das einfachste Thema ...



  • Baum aufbauen



  • Du musst die Klammern schon auflösen. Dazu suchst du dir am besten erstmal die erste Schließende und dann die geöffnete vor dieser Schließenden usw..



  • Hi,

    für dein Problem gibt es mehrere Lösungsansätze. Einer wäre es, in dem du zuerst die Infix-Notation deines booleschen Ausdrucks in die Postfix-Notation transformierst (Dazu findest du zahlreiche Links im Web, z.B.
    http://sulfur.vancouver.wsu.edu/~cs223/CptS223_InfixToPostfix.htm oder
    http://www.cs.utexas.edu/users/lavender/courses/ee360c/lectures/lecture-24.pdf ).
    Ein Beispiel:
    Infix:
    A OR B AND C
    Postfix:
    A B C AND OR
    Danach kannst du den Postfix-String mit Hilfe eines Stacks parsen. Wenn du auf einen Operanden stößt (z.B. "a"), pusht du ihn auf den Operanden-Stack. Wenn du dagegen auf einen Operator (z.B. AND) triffst, popst du die passende Anzahl Operanden vom Stack (AND ist ein binärer Operator, also 2. Beim NOT wäre es z.B. nur 1 Operand), führst die entsprechende Operation aus und pusht das Ergebnis wieder auf den Stack. Das machst du so lange, bis du den gesamten String geparst hast. Danach steht das Ergebnis auf dem Stack. 🙂

    flo


Log in to reply