Comment gérer les parenthèses dans les conversions Infix vers Postfix ?

Gestion des parenthèses dans les conversions Infix en Postfix

La conversion d'expressions infixes en expressions postfix nécessite une gestion minutieuse des parenthèses. La présence de parenthèses pose des problèmes pour déterminer l'ordre correct des opérations. Pour résoudre ce problème, l'approche suivante peut être utilisée :

Mécanisme de gestion des parenthèses

Pousser les parenthèses gauches : Lorsque vous rencontrez une parenthèse gauche, poussez-la sur la pile d'opérateurs.

Parenthèses de droit de traitement : Lors de la rencontre d'un droit parenthèse :

1. Supprimez les opérateurs de la pile et ajoutez-les à la chaîne de sortie jusqu'à ce qu'une parenthèse ouvrante soit rencontrée.
2. Si la pile est vide sans trouver de parenthèse ouvrante, cela indique une parenthèse fermante sans correspondance.
3. Si une parenthèse ouvrante est trouvée, retirez-la de la pile.
4. Sortez la parenthèse droite de la pile d'entrée.

Implémentation du code

Le code Java suivant montre comment modifier la méthode toPostFix() pour gérer les parenthèses :

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(t);
    }

    //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());
        } 

        // opening (
        else if (in_fix.peek().type == 4) {   
            post_fix.push(in_fix.pop());
        }

        // closing )
        else 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 )
        }

        //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();
}

En implémentant ces étapes, la méthode toPostFix() peut gérer efficacement les expressions impliquant des parenthèses, garantissant le bon ordre des opérations et produisant le suffixe souhaité. expressions.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!