1

テスト データ セットでは次のコードが機能しますが、同様のサイズの 2 番目のテスト セットに変更するとオーバーフローします。

トークンの文字列を関連付けられた新しいトークンの文字列に変更するには、このベクトル ルックアップ関数を使用します。

//looks for input string in vector and returns output, 'c' is check row, 'r' is return row
string vectorSearch(string &check, int &direction, int n, int c, int r, int level) 
{
    if ((direction == 1 && check.length() <= 1) || n == list.size()-1 ||(direction == 0 && check.length() > 1)) { //if reading and string is 1 char then pass over
        if (direction == 1){ //convert '???' into '?'
            string temp = "";
            bool wildToken = false;
            for (unsigned int i = 0; i < check.length(); i++) {
                temp+='?';
                if (check.compare(temp) == 0) { check = '?'; wildToken = false; } //done,'???" case, return '?' token
                else if (check[i] == '?') wildToken = true; //not done searching
            }
        }

        return check;
    } else {
        if (list[n][c] == check || list[n][c] == ('0'+check)) //add dummy '0'
            return list[n][r];
        else 
            return vectorSearch (check, direction, n+1, c, r, level);
    }
}

十数回の変換で正常に動作した後、スタックがオーバーフローします

この関数から vectorSearch が呼び出されます

//this function takes an ontology and direction==1 (default) changes from string 
//to single char or if direction==0 takes single char and converts to string representation
string Lexicon::convertOntology(string input, int level, int direction, string out, string temp) 
{
    if (input == "" && temp == "") 
        return out; //check for completed conversion
    else {
        if (direction == 0 || input[0] == '.' || input[0] == '-' || input == "" ) { //found deliniator or end
            if (temp == "") temp = input[0]; //condition for reverse w/o deleniators
            if (input != "") return convertOntology(input.substr(1), level+1, direction, 
                out+=vectorSearch(temp, direction, 0, direction, 1-direction, level));
            else {
                string empty = "";
                return convertOntology(empty, level+1, direction, out+=vectorSearch(temp, direction, 0, direction, 1-direction, level));
            }
        } else 
            return convertOntology(input.substr(1), level, direction, out, temp+=input[0]); //increment and check
    }
}
4

3 に答える 3

3

スタックスペースが不足する前に、再帰を使用して深く掘り下げることしかできません。幸いなことに、再帰関数は反復的に書き直すことができます。以下はあなたのvectorSearchの正しい反復実装であると私は信じています、私は後者をあなたに任せます。

string vectorSearch(string &check, int &direction, int n, int c, int r, int level) 
{
    while(true)
    {
        if ((direction == 1 && check.length() <= 1) || n == list.size()-1 ||(direction == 0 && check.length() > 1)) { //if reading and string is 1 char then pass over
            if (direction == 1){ //convert '???' into '?'
                string temp = "";
                bool wildToken = false;
                for (unsigned int i = 0; i < check.length(); i++) {
                    temp+='?';
                    if (check.compare(temp) == 0) { check = '?'; wildToken = false; } //done,'???" case, return '?' token
                    else if (check[i] == '?') wildToken = true; //not done searching
                }
            }

            return check;
        } else if (list[n][c] == check || list[n][c] == ('0'+check)) {//add dummy '0'
                return list[n][r];
        }

        n++;
    }
}
于 2012-08-29T09:19:57.850 に答える
3

コール スタックは有限のリソースであり、他のリソースと同様に枯渇する可能性があります。関数が大きいほど (内部で作成するローカル変数の作成に関して)、各呼び出しがスタックで使用するスペースの量が大きくなります。何らかの方法で再帰呼び出しの回数を制限できない限り、再帰では避けられないことです。

于 2012-08-29T09:13:52.407 に答える
0

レビューとコメントありがとうございます。

関数は問題ありません - この再帰関数バンドルは、それが動作するデータベースに文字列が存在することを必要とし、これらが特別な条件を誤って認識し、ダミー文字を挿入する前に文字列をチェックします。これら2つに先行する再帰関数があります.3つの再帰関数のバンドルを書いたことを正しく知りませんでした.1つはパラメータ内でデータベースに存在するものよりも長い文字列を検索していました. 明らかに、パラメータはスタックよりも広かった。パラメータをチェックインしましたが、1 つが更新されておらず、制御していませんでした。

特別な条件を修正しました。文字列は同じ長さになり、検索パラメーターが修正されました。

投稿された機能はそれほど複雑ではありません。

于 2012-08-29T22:31:07.830 に答える