Décoder de manière récursive une chaîne codée sous forme de nombre suivi d'une sous-chaîne

Dans ce problème, nous devons décoder la chaîne donnée en ajoutant le nombre total de fois à plusieurs reprises.

Nous pouvons aborder le problème de trois manières différentes et utiliser deux piles ou une pile pour résoudre le problème. De plus, nous pouvons résoudre le problème sans utiliser deux piles.

Énoncé du problème - On nous donne une chaîne str contenant des crochets gauche et droit, des caractères alphabétiques et numériques. Nous devons décoder la chaîne de manière récursive.

Voici les modèles ou règles de décodage des chaînes.

• [chars] - "chars" doit apparaître plusieurs fois dans la chaîne de résultat.

Exemple

Entrez

str = "2[d]3[c2[n]]";

Sortie

ddcnncnncnn

Instructions

• Tout d'abord, nous décodons 2[n] et obtenons "2[d]3[cnn]".

• Ensuite, nous décodons 3[cnn]. Nous obtenons donc "2[d]cnnncnncnn".

• Ensuite, nous décodons 2[d]. Nous obtenons donc "ddcnnncnncnn".

Entrez

5[i]

Sortie

iiiii

Explication- Lorsque nous décodons la chaîne donnée, nous obtenons 5 "I".

Entrez

3[fg]

Sortie

fgfgfg

Explication- Lorsque nous décodons la chaîne d'entrée, nous obtenons "fg" 3 fois.

Méthode 1

Nous utiliserons deux piles pour résoudre le problème dans cette méthode. Lorsque nous obtenons une parenthèse ouvrante, nous la plaçons sur la pile. De plus, lorsque nous obtenons des caractères numériques, nous ajoutons tous les caractères numériques à un entier positif valide et les ajoutons à la pile d'entiers. Ensuite, lorsque nous obtenons le crochet fermant, nous retirons l’entier et le caractère de la pile.

Algorithme

Étape 1- Définissez la pile "instSt" pour stocker les nombres et "strSt" pour stocker les caractères de chaîne et les crochets gauches. De plus, « answer » est initialisé pour stocker la chaîne de résultat et « tempStr » est initialisé pour stocker la chaîne temporaire.

Étape 2- Commencez à parcourir la chaîne.

Étape 3- Si le caractère actuel est un nombre, initialisez "num" avec 0 pour stocker le nombre.

Étape 3.1 − Si le caractère au p^ièmeième index est un nombre, parcourez la chaîne jusqu'à ce que vous obteniez un caractère alphabétique ou une parenthèse. Dans la boucle, multipliez la valeur précédente de "num" par 10 et ajoutez-y le nombre actuel.

Étape 3.2− Augmentez la valeur de « p » de 1.

Étape 3.3 - Poussez la valeur numérique vers la pile "instSt".

Étape 4 - Si le caractère à l'index pth est un crochet droit, suivez ces étapes.

Étape 4.1- Initialisez "temp_str" avec une chaîne vide. Ensuite, si 'instSt' n'est pas vide, retirez le premier entier de la pile.

Étape 4.2 - Maintenant, utilisez une boucle jusqu'à ce que nous obtenions le support gauche ou que la pile devienne vide de la pile "strSt". Ajoutez également des caractères à "temp_str".

Étape 4.3 - Si nous avons arrêté de faire caca sur le personnage à cause de "[", supprimez-le.

Étape 4.4 - Ensuite, nous devons ajouter "temp_Str" "num" fois à la chaîne "answer".

Étape 4.5 - Insérez chaque caractère de la chaîne "réponse" dans la pile "strSt" et réinitialisez-la avec une chaîne vide.

Étape 5 − Si le caractère actuel est un crochet gauche, veuillez suivre les étapes ci-dessous.

Étape 5.1 − Si le caractère précédent est un nombre, poussez "[" sur la pile "StrSt". Sinon, poussez "[" sur la pile StrSt et poussez 1 sur la pile "instSt".

Étape 6− Si nous obtenons un caractère alphabétique, placez-le sur la pile "strSt".

Étape 7- Enfin, utilisez une boucle pour supprimer tous les caractères de la pile "strSt", ajoutez-les à la chaîne "réponse" et renvoyez-la.

Exemple

#include 
using namespace std;

string decodeTheString(string alpha) {
    stack instSt;
    stack StrSt;
    string tempStr = "", answer = "";
    // Iterate the string
    for (int p = 0; p < alpha.length(); p++) {
        int num = 0;
        // If we find the number, extract the number and push it to the stack
        if (alpha[p] >= '0' && alpha[p] <= '9') {
            // Making iterations until we get an alphabetic character
            while (alpha[p] >= '0' && alpha[p] <= '9') {
                num = num * 10 + alpha[p] - '0';
                p++;
            }
            p--;
            instSt.push(num);
        }
        // If the character at the pth index is closing bracket
        else if (alpha[p] == ']') {
            tempStr = "";
            num = 0;
            // Pop the number from the stack
            if (!instSt.empty()) {
                num = instSt.top();
                instSt.pop();
            }
            // Pop the character until we get the opening bracket
            while (!StrSt.empty() && StrSt.top() != '[') {
                tempStr = StrSt.top() + tempStr;
                StrSt.pop();
            }
            // remove the opening bracket
            if (!StrSt.empty() && StrSt.top() == '[')
                StrSt.pop();
            // Append string to answer for num times
            for (int j = 0; j < num; j++)
                answer = answer + tempStr;
            // Insert the updated string again into the stack
            for (int j = 0; j < answer.length(); j++)
                StrSt.push(answer[j]);
            answer = "";
        }
        // If the character at the pth index is an opening bracket
        else if (alpha[p] == '[') {
            if (alpha[p - 1] >= '0' && alpha[p - 1] <= '9') {
                StrSt.push(alpha[p]);
            } else {
                StrSt.push(alpha[p]);
                instSt.push(1);
            }
        } else {
            // Push alphabetic character in the string stack.
            StrSt.push(alpha[p]);
        }
    }
    // Pop all the elements, make a string, and return.
    while (!StrSt.empty()) {
        answer = StrSt.top() + answer;
        StrSt.pop();
    }
    return answer;
}
// starting code
int main() {
    string str = "2[d]3[c2[n]]";
    cout << "The resultant string after decoding it is - " << decodeTheString(str) << endl;
    return 0;
}

Sortie

The resultant string after decoding it is - ddcnncnncnn

Complexité temporelle− O(n^2) car nous parcourons la chaîne et continuons à pousser et à faire apparaître des éléments dans la pile.

Space Complexity− O(n) pour stocker les éléments dans la pile.

Méthode 2

Nous résoudrons le problème sans utiliser de stack dans cette méthode. De plus, nous utiliserons la méthode reverse() pour inverser la chaîne.

Algorithme

Étape 1- Commencez à parcourir la chaîne.

Étape 2− Si le i-ème caractère est "]", insérez-le dans la chaîne "réponse". Sinon, suivez les étapes ci-dessous.

Étape 3- Initialisez "temp_Str" avec une chaîne vide.

Étape 4- Continuez à parcourir la chaîne "réponse" jusqu'à ce que la chaîne soit vide ou que le caractère "[" soit trouvé. Continuez également à extraire le dernier caractère de la chaîne "answer" et à l'ajouter à la chaîne "temp_Str".

Étape 5- Inversez la chaîne "temp_Str" pendant que nous reculons à partir de l'endroit où nous avons trouvé le support "]".

Étape 6- Supprimez le dernier caractère de la chaîne "réponse" pour supprimer le caractère "[".

第 7 步- 如果“答案”字符串顶部包含数字，则使用数字生成一个整数，并将其存储在 number 变量中。

第 8 步- 反转数字字符串。

第 9 步- 使用 stoi() 方法将字符串转换为数字。

步骤 10 - 将 temp_Str 字符串附加到答案字符串“number”次。

第 11 步- 返回“答案”字符串。

示例

#include 
using namespace std;

string decodeTheString(string alpha) {
    string answer = "";
    // iterate the string characters
    for (int i = 0; i < alpha.length(); i++) {
        // for all other characters except the closing bracket
        if (alpha[i] != ']') {
            answer.push_back(alpha[i]);
        } else {
            // Extract the substring lying within the pair
            string temp_str = "";
            // Keep on popping characters until '[' is found.
            while (!answer.empty() && answer.back() != '[') {
                temp_str.push_back(answer.back());
                answer.pop_back();
            }
            // get original string by reversing the string
            reverse(temp_str.begin(), temp_str.end());
            // open bracket removal
            answer.pop_back();
            // get integer value before the '[' character
            string number = "";
            // get the number before opening bracket
            while (!answer.empty() && answer.back() >= '0' && answer.back() <= '9') {
                number.push_back(answer.back());
                answer.pop_back();
            }
            // reverse number string
            reverse(number.begin(), number.end());
            // convert string to integer
            int numInt = stoi(number);
            for (int p = 0; p < numInt; p++) {
                answer += temp_str;
            }
        }
    }
    return answer;
}
int main() {
    string str = "2[d]3[c2[n]]";
    cout << "The resultant string after decoding it is - " << decodeTheString(str) << endl;
    return 0;
}

输出

The resultant string after decoding it is − ddcnncnncnn

时间复杂度− O(N^2)，因为我们遍历字符串并在循环内使用reverse()方法。

空间复杂度− O(N) 来存储数字和临时字符串。

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!