Recursively decode a string encoded as a count followed by a substring

In this problem, we need to decode the given string by repeatedly adding the total count number of times.

We can approach the problem in three different ways, and we can use two stacks or one stack to solve the problem. Also, we can solve the problem without using two stacks.

Problem Statement - We are given a string str containing left and right brackets, alpha and numeric characters. We need to decode the string recursively.

The following are patterns or rules for decoding strings.

• [chars] - "chars" should appear count times in the result string.

Example

enter

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

Output

ddcnncnncnn

illustrate

• First, we decode 2[n] and get "2[d]3[cnn]".

• Next, we decode 3[cnn]. So, we get "2[d]cnnncnncnn".

• Next, we decode 2[d]. So, we get "ddcnnncnncnn".

enter

5[i]

Output

iiiii

Explanation- When we decode the given string, we get 5 "I"s.

enter

3[fg]

Output

fgfgfg

Explanation- When we decode the input string, we get "fg" 3 times.

method 1

We will use two stacks to solve the problem in this method. When we get an opening parenthesis, we push it onto the stack. Additionally, when we get numeric characters, we append all numeric characters to a valid positive integer and add them to the integer stack. Afterwards, when we get the closing bracket, we pop the integer and character from the stack.

algorithm

Step 1- Define the "instSt" stack to store numbers and "strSt" to store string characters and left brackets. Additionally, "answer" is initialized to store the result string and "tempStr" is initialized to store the temporary string.

Step 2- Start traversing the string.

Step 3 - If the current character is a number, initialize "num" with 0 to store the number.

Step 3.1 − If the character at the p^thth index is a number, traverse the string until you get an alphabetic character or a bracket. Within the loop, multiply the previous value of "num" by 10 and add the current number to it.

Step 3.2− Increase the value of "p" by 1.

Step 3.3 - Push the numeric value to the "instSt" stack.

Step 4 - If the character at the pth index is a right bracket, follow these steps.

Step 4.1- Initialize "temp_str" with an empty string. Afterwards, if 'instSt' is not empty, pop the top integer from the stack.

Step 4.2 - Now, use a loop until we get the left bracket or the stack becomes empty from the "strSt" stack. Also, append characters to "temp_str".

Step 4.3 - If we stopped pooping the character due to "[", remove it.

Step 4.4 - Next, we need to append "temp_Str" "num" times to the "answer" string.

Step 4.5 - Insert each character of the "answer" string into the "strSt" stack and reinitialize it with an empty string.

Step 5 − If the current character is a left bracket, please follow the steps below.

Step 5.1 − If the previous character is a number, push "[" onto the stack "StrSt". Otherwise, push '[' onto the StrSt stack and push 1 onto the 'instSt' stack.

Step 6− If we get an alphabetic character, push it onto the "strSt" stack.

Step 7 - Finally, use a loop to remove all characters from the "strSt" stack, append to the "answer" string, and return it.

Example

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

Output

The resultant string after decoding it is - ddcnncnncnn

Time complexity− O(n^2), because we iterate over the string and keep pushing and popping elements to the stack.

Space Complexity− O(n) to store elements in the stack.

Method 2

We will solve the problem without using stack in this method. Additionally, we will use the reverse() method to reverse the string.

algorithm

Step 1- Start iterating the string.

Step 2− If the i-th character is "]", push it into the "answer" string. Otherwise, follow the steps below.

Step 3 - Initialize "temp_Str" with an empty string.

Step 4 - Continue iterating through the "answer" string until the string is empty or the "[" character is found. Also, continue popping the last character from the "answer" string and appending it to the "temp_Str" string.

Step 5 - Reverse the "temp_Str" string as we traverse backward from where we found the "]" bracket.

Step 6 - Remove the last character from the "answer" string to remove the "[" character.

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

The above is the detailed content of Recursively decode a string encoded as a count followed by a substring. For more information, please follow other related articles on the PHP Chinese website!