Umgang mit Klammern beim Konvertieren von Infix-Ausdrücken in Postfix-Ausdrücke

Lesezeit: 4 Minuten

Benutzer-Avatar
Cody James Casey

Ich arbeite an einem Projekt in Java, bei dem ich einen Infix-Ausdruck in einen Postfix-Ausdruck konvertieren muss. Ich bin derzeit in der Lage, Infix-Ausdrücke mit dieser Methode in Postfix umzuwandeln, solange sie keine Klammern enthalten, aber ich kann nicht herausfinden, wie ich mit Klammern umgehen soll.

Grundsätzlich habe ich zwei Stapel, die Objekte enthalten, die “Token” genannt werden. Ein Token ist eine Wrapper-Klasse, die eine Zeichenfolge enthält, die entweder eine Zahl, eine Variable (die als Zahl ausgewertet wird, abhängig von der Benutzereingabe) oder einen Operator (dem Operator ist eine Prioritätsstufe zugeordnet, damit meine Methode bestimmen kann, wie es geht behandeln die Reihenfolge der Operationen zwischen ‘+’, ‘-‘, ‘*’ und “https://stackoverflow.com/”) oder eine Klammer (die Klammer hat eine Möglichkeit zu bestimmen, ob es sich um eine offene oder eine geschlossene Klammer handelt ).

Wie soll ich mit Klammern umgehen? Was ist mit mehreren Ebenen von Klammern?

public String toPostFix() {
    StringBuilder postfixstr = new StringBuilder();

    Stack<Token> in_fix = new Stack<>();
    Stack<Token> post_fix = new Stack<>();

    for (int i = tokens.length - 1; i >= 0; i--) {
        t = new Token(tokens[i]);
        in_fix.push
    }

    //there are still tokens to process
    while (!in_fix.empty()) {
        //is a number
        if (in_fix.peek().type == 1) {     
            postfixstr.append(in_fix.pop().toString());
        } 

        //is an operator and the stack is empty
        else if (in_fix.peek().type == 3 && post_fix.empty()) {   
            post_fix.push(in_fix.pop());
        } 

        // is an operator that has higher priority than the operator on the stack
        else if (in_fix.peek().type == 3 && in_fix.peek().isOperator() > post_fix.peek().isOperator()) {
            post_fix.push(in_fix.pop());
        } 

        // is an operator that has lower priority than the operator on the stack
        else if (in_fix.peek().type == 3 && in_fix.peek().isOperator() <= post_fix.peek().isOperator()) {
            postfixstr.append(post_fix.pop());
            post_fix.push(in_fix.pop());
        } 

        //puts the rest of the stack onto the output string
        if (in_fix.empty()) {
            while (!post_fix.empty()) {
                postfixstr.append(post_fix.pop());
            }
        }
    }

    return postfixstr.toString();
}

  • Was Sie haben, ist mehr oder weniger der Dijkstra-Rangierbahnhofalgorithmus, aber ohne die Handhabung von Klammern.

    – Benutzer207421

    1. November 2013 um 5:19 Uhr


  • Interessant. Ich suche gerade etwas Literatur dazu!

    – CodyJamesCasey

    1. November 2013 um 6:57 Uhr

Sie müssen die linke Klammer auf den Stapel schieben und den Stapel wie folgt verarbeiten, wenn Sie auf eine rechte Klammer stoßen:

// opening (
if (in_fix.peek().type == 4) {   
    post_fix.push(in_fix.pop());
}
//closing )
if(in_fix.peek().type == 5){
    while(!(post_fix.isEmpty() || post_fix.peek().type == 4)){
         postfixstr.append(post_fix.pop());
    }
    if (post_fix.isEmpty())
        ; // ERROR - unmatched )
    else
        post_fix.pop(); // pop the (
    in_fix.pop(); // pop the )
} 

  • @downvoter Dieser Algorithmus wurde 1961 von Edsger Dijkstra erfunden, und dies ist eine genaue Darstellung eines Teils davon. Ihr Kilometerstand variiert offensichtlich.

    – Benutzer207421

    1. November 2013 um 5:56 Uhr

  • Definitiv nicht ich! Haha.

    – dg_no_9

    1. November 2013 um 5:58 Uhr

  • @dg_no_9 et al. Der Witz entgeht mir. Die einzig richtige Antwort im Thread, und sie hat eine Ablehnung?

    – Benutzer207421

    1. November 2013 um 6:09 Uhr

  • Ich denke, Ihre und meine sind ähnliche Antworten, ich denke, Ihre Antwort ist zu richtig, deshalb habe ich Sie nicht im Gegensatz zu meiner herabgestuft. 🙂

    – dg_no_9

    1. November 2013 um 6:12 Uhr

  • Vielen Dank! Das funktioniert perfekt. =) Ich würde beim Up-Vote helfen, aber mein Ruf ist noch nicht hoch genug! hahaha

    – CodyJamesCasey

    1. November 2013 um 6:54 Uhr

Benutzer-Avatar
dg_no_9

Versuchen Sie es so:

    //opening Parenthesis 
        if (in_fix.peek().type == 4) {   
                    post_fix.push(in_fix.pop());
        }
        //closing Parenthesis 
        if(in_fix.peek().type == 5){
             //Till opening parenthesis encountered in stack, append operators to postfix. and pop parenthesis and do not append to post_fix.
             while(post_fix.peek().type!=4){
                 postfixstr.append(post_fix.pop());
             }
            //finally pop left parenthesis from post_fix stack.
            post_fix.pop();
        } 

  • Sieht nicht richtig aus. Wie wird sich die While-Bedingung jemals ändern?

    – Benutzer207421

    1. November 2013 um 5:23 Uhr

  • Entschuldigung, ich bin mit dem in_fix-Stack und dem post_fix-Stack verwechselt worden. Jetzt habe ich das bearbeitet. Danke für die Information. 🙂

    – dg_no_9

    1. November 2013 um 5:29 Uhr

  • Immer noch nicht richtig. Dadurch werden nur Klammern an das Postfix angehängt. Es sollte sein != 4. Sie müssen auch nach einer fehlenden rechten Klammer (d. h. einem leeren Stapel) suchen und das (. Ich schlage vor, Sie suchen es nach.

    – Benutzer207421

    1. November 2013 um 5:43 Uhr


  • Dies ist nicht die genau funktionierende Kopie des Codes, ich wollte ihm/ihr nur eine Idee geben. Deshalb habe ich die Logik in den Kommentaren erwähnt.

    – dg_no_9

    1. November 2013 um 5:44 Uhr

  • Als ich den Algorithmus vor einer halben Stunde in den Kommentaren benannte, bevor Ihre Antwort überhaupt gepostet wurde, war es kaum, sich selbst eine Vorstellung zu machen, und da ich Ihnen vor dem Downvoting mehrere Hinweise gegeben habe, war es das auch kaum. Aber genug ist genug. Ihre letzte Änderung ist immer noch unzureichend.

    – Benutzer207421

    1. November 2013 um 5:49 Uhr


1006690cookie-checkUmgang mit Klammern beim Konvertieren von Infix-Ausdrücken in Postfix-Ausdrücke

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy