具有 20,000 个大小字符串的 C++ 堆栈溢出

Question

我的简单程序源代码如下，它找到(嵌套的)括号对并重复字符串。

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

我在 MSVC 中遇到了这个 Stack Overflow 错误，但在 WSL2 ubuntu 20.04 clang-10 中没有出现。我在 Visual Studio 2019 中进行了测试。

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

这是怎么回事？我用 VS 调试它，但我不知道出了什么问题。

Answer 1

我通过将递归代码更改为迭代代码解决了我的问题。

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

是的，我知道这不是最好的迭代代码，我更喜欢递归而不是迭代，但这行得通。