Dekodieren Sie rekursiv eine Zeichenfolge, die als Anzahl gefolgt von einer Teilzeichenfolge codiert ist

In diesem Problem müssen wir die gegebene Zeichenfolge dekodieren, indem wir die Gesamtzahl wiederholt addieren.

Wir können das Problem auf drei verschiedene Arten angehen und können zwei Stapel oder einen Stapel verwenden, um das Problem zu lösen. Wir können das Problem auch lösen, ohne zwei Stapel zu verwenden.

Problemstellung – Wir erhalten eine Zeichenfolge str, die linke und rechte Klammern, Buchstaben und numerische Zeichen enthält. Wir müssen die Zeichenfolge rekursiv dekodieren.

Im Folgenden sind die Muster oder Regeln zum Dekodieren von Zeichenfolgen aufgeführt.

• [chars] – „chars“ sollten in der Ergebniszeichenfolge mehrere Male vorkommen.

Beispiel

Eintreten

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

Ausgabe

ddcnncnncnn

Anleitung

• Zuerst dekodieren wir 2[n] und erhalten „2[d]3[cnn]“.

• Als nächstes dekodieren wir 3[cnn]. Wir erhalten also „2[d]cnnncnncnn“.

• Als nächstes dekodieren wir 2[d]. Also erhalten wir „ddcnnncnncnn“.

Eintreten

5[i]

Ausgabe

iiiii

Erklärung – Wenn wir die gegebene Zeichenfolge dekodieren, erhalten wir 5 „I“.

Eintreten

3[fg]

Ausgabe

fgfgfg

Erklärung- Wenn wir die Eingabezeichenfolge dekodieren, erhalten wir dreimal „fg“.

Methode 1

Wir werden bei dieser Methode zwei Stapel verwenden, um das Problem zu lösen. Wenn wir eine öffnende Klammer erhalten, legen wir sie auf den Stapel. Wenn wir außerdem numerische Zeichen erhalten, hängen wir alle numerischen Zeichen an eine gültige positive Ganzzahl an und fügen sie dem Ganzzahlstapel hinzu. Wenn wir anschließend die schließende Klammer erhalten, entfernen wir die Ganzzahl und das Zeichen vom Stapel.

Algorithmus

Schritt 1- Definieren Sie den Stapel „instSt“ zum Speichern von Zahlen und „strSt“ zum Speichern von Zeichenfolgen und linken Klammern. Darüber hinaus wird „answer“ initialisiert, um die Ergebniszeichenfolge zu speichern, und „tempStr“ wird initialisiert, um die temporäre Zeichenfolge zu speichern.

Schritt 2 – Beginnen Sie mit dem Durchqueren der Saite.

Schritt 3 – Wenn das aktuelle Zeichen eine Zahl ist, initialisieren Sie „num“ mit 0, um die Zahl zu speichern.

Schritt 3.1 − Wenn das Zeichen am p^tenten Index eine Zahl ist, durchlaufen Sie die Zeichenfolge, bis Sie ein alphabetisches Zeichen oder eine Klammer erhalten. Multiplizieren Sie innerhalb der Schleife den vorherigen Wert von „num“ mit 10 und addieren Sie die aktuelle Zahl dazu.

Schritt 3.2− Erhöhen Sie den Wert von „p“ um 1.

Schritt 3.3 - Schieben Sie den numerischen Wert auf den Stapel „instSt“.

Schritt 4 - Wenn das Zeichen am p-ten Index eine rechte Klammer ist, befolgen Sie diese Schritte.

Schritt 4.1 – Initialisieren Sie „temp_str“ mit einer leeren Zeichenfolge. Wenn „instSt“ anschließend nicht leer ist, entfernen Sie die oberste Ganzzahl vom Stapel.

Schritt 4.2 - Verwenden Sie nun eine Schleife, bis wir die linke Klammer erhalten oder der Stapel vom Stapel „strSt“ leer wird. Hängen Sie außerdem Zeichen an „temp_str“ an.

Schritt 4.3 - Wenn wir wegen „[“ aufgehört haben, das Zeichen zu kacken, entfernen Sie es.

Schritt 4.4 - Als nächstes müssen wir „temp_Str“ „num“ mal an die „answer“-Zeichenfolge anhängen.

Schritt 4.5 - Fügen Sie jedes Zeichen der Zeichenfolge „answer“ in den Stapel „strSt“ ein und initialisieren Sie ihn mit einer leeren Zeichenfolge neu.

Schritt 5 − Wenn das aktuelle Zeichen eine linke Klammer ist, befolgen Sie bitte die folgenden Schritte.

Schritt 5.1 − Wenn das vorherige Zeichen eine Zahl ist, schieben Sie „[“ auf den Stapel „StrSt“. Andernfalls schieben Sie „[“ auf den StrSt-Stapel und 1 auf den „instSt“-Stapel.

Schritt 6− Wenn wir ein alphabetisches Zeichen erhalten, schieben Sie es auf den Stapel „strSt“.

Schritt 7 – Abschließend verwenden Sie eine Schleife, um alle Zeichen aus dem Stapel „strSt“ zu entfernen, an die Zeichenfolge „answer“ anzuhängen und diese zurückzugeben.

Beispiel

#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;
}

Ausgabe

The resultant string after decoding it is - ddcnncnncnn

Zeitliche Komplexität− O(n^2), da wir über die Zeichenfolge iterieren und weiterhin Elemente auf den Stapel schieben und ablegen.

Space Complexity− O(n) zum Speichern von Elementen im Stapel.

Methode 2

Wir werden das Problem lösen, ohne bei dieser Methode einen Stapel zu verwenden. Zusätzlich verwenden wir die Methode reverse(), um die Zeichenfolge umzukehren.

Algorithmus

Schritt 1 – Beginnen Sie mit der Iteration über die Zeichenfolge.

Schritt 2− Wenn das i-te Zeichen „]“ ist, schieben Sie es in die „Antwort“-Zeichenfolge. Befolgen Sie andernfalls die folgenden Schritte.

Schritt 3 – Initialisieren Sie „temp_Str“ mit einer leeren Zeichenfolge.

Schritt 4 – Durchlaufen Sie die Zeichenfolge „Antwort“ weiter, bis die Zeichenfolge leer ist oder das Zeichen „[“ gefunden wird. Entfernen Sie außerdem weiterhin das letzte Zeichen aus der Zeichenfolge „answer“ und hängen Sie es an die Zeichenfolge „temp_Str“ an.

Schritt 5 – Kehren Sie die Zeichenfolge „temp_Str“ um, während wir von der Stelle, an der wir die Klammer „]“ gefunden haben, rückwärts gehen.

Schritt 6 – Entfernen Sie das letzte Zeichen aus der „Antwort“-Zeichenfolge, um das „[“-Zeichen zu entfernen.

第 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) 来存储数字和临时字符串。

Das obige ist der detaillierte Inhalt vonDekodieren Sie rekursiv eine Zeichenfolge, die als Anzahl gefolgt von einer Teilzeichenfolge codiert ist. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!