PHP met en œuvre une méthode efficace pour inverser les sous-chaînes entre parenthèses

Des questions fréquemment posées dans le traitement des chaînes

Pendant le processus de programmation, le traitement des chaînes est une exigence très fréquente. Surtout lorsque la rencontre des parenthèses et leurs structures imbriquées, inverser les sous-chaînes entre parenthèses causent souvent des problèmes aux développeurs. Cet article présentera comment inverser les chaînes de chaque paire de supports de la description du problème, des idées d'algorithmes à des implémentations spécifiques.

Description du problème

Compte tenu d'une chaîne contenant des caractères et des supports normaux, l'objectif est d'inverser le contenu entre chaque paire de supports. Par exemple, entrez "(ABC) DE (FGH)" et la sortie attendue est "CBADEHGF". Ces problèmes peuvent être efficacement résolus par des règles et des étapes claires.

Exemples d'entrée et de sortie

Les exemples suivants aident à comprendre le problème:

 entrer: "(xyz)(abc)"
Sortir: "zyxcba"

entrer: "a(bc(de)fg)h"
Sortir: "ahgfedcba"

Idées de mise en œuvre

La structure de données la plus appropriée pour résoudre ce problème est la pile, car la pile peut facilement gérer les hiérarchies imbriquées des supports. Le processus global est le suivant:

• Initialise une pile et une variable utilisée pour épisser la chaîne actuelle.
• Itérer à travers chaque caractère de la chaîne:
• Lorsque le support d'ouverture "(", poussez la chaîne actuelle dans la pile et effacez la chaîne actuelle pour commencer à traiter le contenu entre les supports.
• Lorsque le support de clôture ")" est rencontré, la chaîne actuelle est inversée et épissée avec la chaîne supérieure de la pile pour mettre à jour la chaîne actuelle.
• D'autres caractères sont ajoutés directement à la chaîne actuelle.
• Une fois la traversée terminée, la chaîne actuelle est le résultat final.

Exemple de code PHP

 function reverseParentheses($s) {
    $stack = [];
    $currentString = "";
    for ($i = 0; $i < strlen($s); $i++) {
        $char = $s[$i];
        if ($char === '(') {
            array_push($stack, $currentString);
            $currentString = "";
        } elseif ($char === ')') {
            $currentString = strrev($currentString);
            if (!empty($stack)) {
                $currentString = array_pop($stack) . $currentString;
            }
        } else {
            $currentString .= $char;
        }
    }
    return $currentString;
}

// Exemple d&#39;appel
echo reverseParentheses("(abc)de(fgh)"); // Sortir cbadehgf

Analyse des performances

La complexité temporelle de cette méthode est O (n), et n est la longueur de la chaîne d'entrée car chaque caractère est accessible une fois. La complexité spatiale est également O (n), qui est utilisée pour stocker la pile et la chaîne actuelle.

Résumé

L'utilisation de la structure de pile pour inverser les sous-chaînes entre parenthèses est une solution efficace à de tels problèmes. Les idées et les exemples de code introduits dans cet article conviennent aux applications de référence lors de la rencontre des exigences de traitement des chaînes similaires dans des projets réels, aidant les développeurs à améliorer l'efficacité du codage et les capacités de résolution de problèmes.