Блог

Главная - Вопросы по программированию - Переполнение стека C строкой размером 20 000

Переполнение стека C строкой размером 20 000

#c

#c

Вопрос:

Ниже приведен мой простой исходный код программы, и он находит (вложенную) пару круглых скобок и повторяет строку.

 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, но не возникло в 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, но я не знаю, что не так.

скриншот отладки

Комментарии:

1. Рекурсия может сделать это с вами. Возможно, вам придется найти нерекурсивное решение или быть намного хитрее с тем, как вы распределяете хранилище.

2. Linux по умолчанию имеет стек размером 8 МБ на процесс, в то время как Windows имеет только один стек размером 1 МБ. Это, вероятно, объяснило бы разницу в поведении.

3. Поскольку я знаю, что, хотя строковая переменная объявлена в стеке, она выделяется в куче. Связана ли эта ошибка с этим?

4. Глубина рекурсии ограничена. Строка будет содержать около 24 байт на рекурсию

5. Рекурсия. Вызовы функций почти во всех системах используют стек для передачи данных о вызове, а также для локальных переменных. Глубокая рекурсия исчерпает стек.

Ответ №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;
}

Да, я знаю, что это не лучший итерационный код, и я предпочитаю рекурсию итерации, но это работает.