0

この関数は、wild'*' と '?' を含む文字列を取ります。ワイルドカードを使用し、ワイルドカードをツリー データベースからの可能な文字に置き換えますnodeT *w。out一時文字列を保持します。各候補は、参照された bst に追加されます。

void Lexicon::matchRegExpHelper(nodeT *w, string wild, Set<string> &matchSet, string out)
{   
    if (wild == "") matchSet.add(out);

    else {
        if (wild[0] != '*' || wild[0] != '?') { //this parses up to the wildcard, earlier versions used a position parameter and looped through the prefix chars recursively
            for (int j = 0; j < w->alpha.size(); j++)
                if (wild[0] == w->alpha[j].letter) matchRegExpHelper(w->alpha[j].next, wild.substr(1), matchSet, out+=wild[0]);
        } else {
            for (int i = 0; i < w->alpha.size(); i++) { 
                if (wild[0] == '?') matchRegExpHelper(w->alpha[i].next, wild.substr(1), matchSet, out+=w->alpha[i].letter);//follow path
                else { //logically, wild[0] == '*' must be true
                    if (ontLength == (wild.length() + out.length())) matchRegExpHelper(w->alpha[i].next, wild.substr(1), matchSet, out+=w->alpha[i].letter); //ontology is full, treat like a '?'
                    else matchRegExpHelper(w->alpha[i].next, wild.substr(1), matchSet, out+=(w->alpha[i].letter+'*')); //keep adding chars
                }
            }
        }
    }
}

最初のワイルドカードに到達すると、関数は最初からやり直します。これを for ループを使用して、ループを使用せずに、さまざまな「プルーン」アプローチで書き直そうとしました。基本的なものが欠けており、これは後戻りの問題であると思われます。最終的にスタックはオーバーフローします。

質問: 1) 概念的に欠けているものは何ですか? 2) この機能を修正するにはどうすればよいですか?

for ループのないバージョン - テスト ケースは少し異なりますが似ています。もう一度テストして見つける必要があります。

else {
            if (wild[0] == '?'){
                matchRegExpHelper(w, wild, ++pos, matchSet, out);//return and check next path
                matchRegExpHelper(w->alpha[pos].next, wild.substr(1), 0, matchSet, out+=w->alpha[pos].letter);//follow path
            }
            if (wild[0] == '*'){
                matchRegExpHelper(w, wild, ++pos, matchSet, out);//return and check next path
                if (ontLength == (wild.length() + out.length()))matchRegExpHelper(w->alpha[pos].next, wild.substr(1), 0, matchSet, out+=w->alpha[pos].letter); //ontology is full, treat like a '?'
                else matchRegExpHelper(w->alpha[pos].next, wild.substr(1), 0, matchSet, out+=(w->alpha[pos].letter+'*')); //keep adding chars
            }
            if (wild[0] == w->alpha[pos].letter) matchRegExpHelper(w->alpha[pos].next, wild.substr(1), 0, matchSet, out+=wild[0]);  

            matchRegExpHelper(w, wild, ++pos, matchSet, out);//check next path
        }
        for (int i = 0; i < w->alpha.size(); i++) matchRegExpHelper(w->alpha[i].next, wild.substr(1), 0, matchSet, out+=wild[0]);//step over char

最後の for ループは、オーバーフローを修正するための試みでした。一部のスレッドには当てはまらないのではないかと思いましたが、それらをプルーニングしたかったので、どうすればよいかわかりません

4

3 に答える 3

2

この条件は常に真です: (wild[0] != '*' || wild[0] != '?')

任意の文字は 2 つのうちの 1 つとは異なるため、(wild[0] != '*' && wild[0] != '?') を意味する可能性があります。

これがあなたの進歩に少しでも役立つことを願っています...

また、概念的には、私は通常、再帰関数内で「for」を使用しません。「for」を使用せずに書き直してみてください。おそらく、より明確になり、効率的ではないかもしれませんが、機能したら、アルゴリズムの微調整を開始できます..

于 2012-07-27T11:05:05.807 に答える
1

すべての再帰には、基本終了条件が必要です。

という感じです

 if (wild[0] != '*' || wild[0] != '?')

は間違っています (文字が同時に a'*'と aになることはできないため、そのテストは常に真です)、論理和ではなく論理積'?'でなければなりません&&||

しかし、コメントで述べたように、デバッガーの使用方法を実際に学ぶ必要があります(つまり、ブレークポイントを配置する、バックトレースを要求する、変数の値を照会する)。

デバッグに精通していることは、この特定のプログラム (または宿題) を超えて、一生にわたって価値のあるスキルです。

于 2012-07-27T11:04:17.833 に答える
0

このコードには 3 つの問題がありました。

@Basile_Starynkevitch は、デバッガーを使用してパスをたどることの重要性を指摘しました。この場合、VS2008 では、スタックはステップを解析し、いくつかの関数を介して戻るパスに注意することができました。

@Picarusは、終了条件のエラーを正しく指摘しました

これらの解決策により、次のことがわかりました。

解決策として、この void 関数には 2 つreturn;の が必要です。1 つは終了条件の後に終了し、もう 1 つは最後にプルーニングされたスレッドをキャッチします。いくつかのウェブサイトを読んだところ、return;in a void 関数は珍しいようですが、この場合、再帰と複数のパスが必要でした。

于 2012-07-27T19:18:03.563 に答える