search
HomeBackend DevelopmentC++Recursively decode a string encoded as a count followed by a substring

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 pthth 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!

Statement
This article is reproduced at:tutorialspoint. If there is any infringement, please contact admin@php.cn delete
C# vs. C  : Learning Curves and Developer ExperienceC# vs. C : Learning Curves and Developer ExperienceApr 18, 2025 am 12:13 AM

There are significant differences in the learning curves of C# and C and developer experience. 1) The learning curve of C# is relatively flat and is suitable for rapid development and enterprise-level applications. 2) The learning curve of C is steep and is suitable for high-performance and low-level control scenarios.

C# vs. C  : Object-Oriented Programming and FeaturesC# vs. C : Object-Oriented Programming and FeaturesApr 17, 2025 am 12:02 AM

There are significant differences in how C# and C implement and features in object-oriented programming (OOP). 1) The class definition and syntax of C# are more concise and support advanced features such as LINQ. 2) C provides finer granular control, suitable for system programming and high performance needs. Both have their own advantages, and the choice should be based on the specific application scenario.

From XML to C  : Data Transformation and ManipulationFrom XML to C : Data Transformation and ManipulationApr 16, 2025 am 12:08 AM

Converting from XML to C and performing data operations can be achieved through the following steps: 1) parsing XML files using tinyxml2 library, 2) mapping data into C's data structure, 3) using C standard library such as std::vector for data operations. Through these steps, data converted from XML can be processed and manipulated efficiently.

C# vs. C  : Memory Management and Garbage CollectionC# vs. C : Memory Management and Garbage CollectionApr 15, 2025 am 12:16 AM

C# uses automatic garbage collection mechanism, while C uses manual memory management. 1. C#'s garbage collector automatically manages memory to reduce the risk of memory leakage, but may lead to performance degradation. 2.C provides flexible memory control, suitable for applications that require fine management, but should be handled with caution to avoid memory leakage.

Beyond the Hype: Assessing the Relevance of C   TodayBeyond the Hype: Assessing the Relevance of C TodayApr 14, 2025 am 12:01 AM

C still has important relevance in modern programming. 1) High performance and direct hardware operation capabilities make it the first choice in the fields of game development, embedded systems and high-performance computing. 2) Rich programming paradigms and modern features such as smart pointers and template programming enhance its flexibility and efficiency. Although the learning curve is steep, its powerful capabilities make it still important in today's programming ecosystem.

The C   Community: Resources, Support, and DevelopmentThe C Community: Resources, Support, and DevelopmentApr 13, 2025 am 12:01 AM

C Learners and developers can get resources and support from StackOverflow, Reddit's r/cpp community, Coursera and edX courses, open source projects on GitHub, professional consulting services, and CppCon. 1. StackOverflow provides answers to technical questions; 2. Reddit's r/cpp community shares the latest news; 3. Coursera and edX provide formal C courses; 4. Open source projects on GitHub such as LLVM and Boost improve skills; 5. Professional consulting services such as JetBrains and Perforce provide technical support; 6. CppCon and other conferences help careers

C# vs. C  : Where Each Language ExcelsC# vs. C : Where Each Language ExcelsApr 12, 2025 am 12:08 AM

C# is suitable for projects that require high development efficiency and cross-platform support, while C is suitable for applications that require high performance and underlying control. 1) C# simplifies development, provides garbage collection and rich class libraries, suitable for enterprise-level applications. 2)C allows direct memory operation, suitable for game development and high-performance computing.

The Continued Use of C  : Reasons for Its EnduranceThe Continued Use of C : Reasons for Its EnduranceApr 11, 2025 am 12:02 AM

C Reasons for continuous use include its high performance, wide application and evolving characteristics. 1) High-efficiency performance: C performs excellently in system programming and high-performance computing by directly manipulating memory and hardware. 2) Widely used: shine in the fields of game development, embedded systems, etc. 3) Continuous evolution: Since its release in 1983, C has continued to add new features to maintain its competitiveness.

See all articles

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

AI Hentai Generator

AI Hentai Generator

Generate AI Hentai for free.

Hot Article

R.E.P.O. Energy Crystals Explained and What They Do (Yellow Crystal)
1 months agoBy尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Best Graphic Settings
1 months agoBy尊渡假赌尊渡假赌尊渡假赌
Will R.E.P.O. Have Crossplay?
1 months agoBy尊渡假赌尊渡假赌尊渡假赌

Hot Tools

Safe Exam Browser

Safe Exam Browser

Safe Exam Browser is a secure browser environment for taking online exams securely. This software turns any computer into a secure workstation. It controls access to any utility and prevents students from using unauthorized resources.

WebStorm Mac version

WebStorm Mac version

Useful JavaScript development tools

SAP NetWeaver Server Adapter for Eclipse

SAP NetWeaver Server Adapter for Eclipse

Integrate Eclipse with SAP NetWeaver application server.

MinGW - Minimalist GNU for Windows

MinGW - Minimalist GNU for Windows

This project is in the process of being migrated to osdn.net/projects/mingw, you can continue to follow us there. MinGW: A native Windows port of the GNU Compiler Collection (GCC), freely distributable import libraries and header files for building native Windows applications; includes extensions to the MSVC runtime to support C99 functionality. All MinGW software can run on 64-bit Windows platforms.

Atom editor mac version download

Atom editor mac version download

The most popular open source editor