C++ Stack Overflow with 20,000 size string

Question

My simple program source code is following and it find the (nested) parenthesis pair and repeat the string.

2(R) -> RR

#include <iostream>
#include <string>
#include <stack>
using namespace std;

string repeated(string str, int n){
    string repeat;
    for(int _=0; _<n; _++)
        repeat.append(str);
    return repeat;
}

string solution(string rgb, int recurdepth) {
    stack<int> s;

    for(int i=0; i<rgb.size(); i++){
        if(rgb[i]=='(') {
            s.emplace(i);
        }
        else if(rgb[i]==')') {
            int startp = s.top();
            char command = rgb[startp-1];
            string childstr = rgb.substr(startp+1, i-(startp+1));
                
            string tmp2;
            tmp2 = repeated(childstr, (int) command - '0');

            rgb.erase(startp-1, i+1-(startp-1));
            rgb.insert(startp-1, tmp2);
            
// change the string and start from first
            return solution(rgb, recurdepth+1);
        }
    }
// if there are no parenthesis, just return
    return rgb;
}

int main(int, char**) {    
    string in1;
    for(int i=0; i<5000; i++) in1.append("2(R)");
    cout<< in1.size() << endl;
    string answer = solution(in1, 1);
    cout << answer.size() << endl;
    cout << "answer: " << answer << endl;
}

I encountered this Stack Overflow error with MSVC, but not occured in WSL2 ubuntu 20.04 clang-10. I tested in Visual Studio 2019.

Unhandled exception at 0x00007FFFF99FE798 (ntdll.dll) in ConsoleApplication1.exe: 0xC00000FD: Stack overflow (parameters: 0x0000000000000001, 0x000000B0F6003FD8).

What's wrong with this? I debug this with VS, but i don't know what's wrong.

Recursion can do that to you. You may have to find a non-recursive solution or be a lot sneakier with how you're allocating storage. — user4581301
– user4581301, Commented Nov 1, 2020 at 3:30
Linux by default have an 8 MiB stack per process, while Windows only have a single 1 MiB stack. That would probably explain the different in behavior. — Some programmer dude
– Some programmer dude, Commented Nov 1, 2020 at 3:33
As I know that though string variable declared in stack, it allocated in heap. Is this error associated with it? — varvir
– varvir, Commented Nov 1, 2020 at 3:40
The recursion depth is limited. The string will have 24 or so bytes per recursion — drescherjm
– drescherjm, Commented Nov 1, 2020 at 3:41
Recursion. Function calls on almost all systems uses the stack for the data bout the call as well as the local variables. Deep recursion will exhaust the stack. — Some programmer dude
– Some programmer dude, Commented Nov 1, 2020 at 3:43

cigien · Accepted Answer · 2020-11-01 04:49:28Z

I solved my problem by changing my recursion code to iteration code.

#include <iostream>
#include <string>
#include <stack>
using namespace std;


string repeated(string str, int n) {
    string repeat;
    for (int _ = 0; _ < n; _++)
        repeat.append(str);
    return repeat;
}

string solution(string rgb) {
    bool isthereparen = true;
    stack<int> s;

    while (isthereparen)
    {
        for (int i = 0; i < rgb.size(); i++) {
            if (rgb[i] == '(') {
                s.emplace(i);
            }
            else if (rgb[i] == ')') {
                isthereparen = false;

                int startp = s.top();
                char command = rgb[startp - 1];
                string childstr = rgb.substr(startp + 1, i - (startp + 1));

                string tmp2;
                tmp2 = repeated(childstr, (int)command - '0');

                rgb.erase(startp - 1, i + 1 - (startp - 1));
                rgb.insert(startp - 1, tmp2);
                break;
            }
        }

        if (isthereparen == false) {
            isthereparen = true;
        }
        else {
            isthereparen = false;
        }
    }

    return rgb;
}

int main(int, char**) {
    string in1;
    for (int i = 0; i < 10000; i++) in1.append("2(R)");
    cout << in1.size() << endl;
    string answer = solution(in1);
    cout << answer.size() << endl;
    cout << "answer: " << answer << endl;
}

Yeah, I know this is not the best iteration code, and I prefer recursion to iteration, but this works.

Collectives™ on Stack Overflow

C++ Stack Overflow with 20,000 size string

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related