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
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.

The Future of C   and XML: Emerging Trends and TechnologiesThe Future of C and XML: Emerging Trends and TechnologiesApr 10, 2025 am 09:28 AM

The future development trends of C and XML are: 1) C will introduce new features such as modules, concepts and coroutines through the C 20 and C 23 standards to improve programming efficiency and security; 2) XML will continue to occupy an important position in data exchange and configuration files, but will face the challenges of JSON and YAML, and will develop in a more concise and easy-to-parse direction, such as the improvements of XMLSchema1.1 and XPath3.1.

Modern C   Design Patterns: Building Scalable and Maintainable SoftwareModern C Design Patterns: Building Scalable and Maintainable SoftwareApr 09, 2025 am 12:06 AM

The modern C design model uses new features of C 11 and beyond to help build more flexible and efficient software. 1) Use lambda expressions and std::function to simplify observer pattern. 2) Optimize performance through mobile semantics and perfect forwarding. 3) Intelligent pointers ensure type safety and resource management.

C   Multithreading and Concurrency: Mastering Parallel ProgrammingC Multithreading and Concurrency: Mastering Parallel ProgrammingApr 08, 2025 am 12:10 AM

C The core concepts of multithreading and concurrent programming include thread creation and management, synchronization and mutual exclusion, conditional variables, thread pooling, asynchronous programming, common errors and debugging techniques, and performance optimization and best practices. 1) Create threads using the std::thread class. The example shows how to create and wait for the thread to complete. 2) Synchronize and mutual exclusion to use std::mutex and std::lock_guard to protect shared resources and avoid data competition. 3) Condition variables realize communication and synchronization between threads through std::condition_variable. 4) The thread pool example shows how to use the ThreadPool class to process tasks in parallel to improve efficiency. 5) Asynchronous programming uses std::as

C   Deep Dive: Mastering Memory Management, Pointers, and TemplatesC Deep Dive: Mastering Memory Management, Pointers, and TemplatesApr 07, 2025 am 12:11 AM

C's memory management, pointers and templates are core features. 1. Memory management manually allocates and releases memory through new and deletes, and pay attention to the difference between heap and stack. 2. Pointers allow direct operation of memory addresses, and use them with caution. Smart pointers can simplify management. 3. Template implements generic programming, improves code reusability and flexibility, and needs to understand type derivation and specialization.

C   and System Programming: Low-Level Control and Hardware InteractionC and System Programming: Low-Level Control and Hardware InteractionApr 06, 2025 am 12:06 AM

C is suitable for system programming and hardware interaction because it provides control capabilities close to hardware and powerful features of object-oriented programming. 1)C Through low-level features such as pointer, memory management and bit operation, efficient system-level operation can be achieved. 2) Hardware interaction is implemented through device drivers, and C can write these drivers to handle communication with hardware devices.

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)
3 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Best Graphic Settings
3 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. How to Fix Audio if You Can't Hear Anyone
3 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
WWE 2K25: How To Unlock Everything In MyRise
4 weeks agoBy尊渡假赌尊渡假赌尊渡假赌

Hot Tools

DVWA

DVWA

Damn Vulnerable Web App (DVWA) is a PHP/MySQL web application that is very vulnerable. Its main goals are to be an aid for security professionals to test their skills and tools in a legal environment, to help web developers better understand the process of securing web applications, and to help teachers/students teach/learn in a classroom environment Web application security. The goal of DVWA is to practice some of the most common web vulnerabilities through a simple and straightforward interface, with varying degrees of difficulty. Please note that this software

VSCode Windows 64-bit Download

VSCode Windows 64-bit Download

A free and powerful IDE editor launched by Microsoft

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.

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

Powerful PHP integrated development environment

WebStorm Mac version

WebStorm Mac version

Useful JavaScript development tools