この関数は、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 ループは、オーバーフローを修正するための試みでした。一部のスレッドには当てはまらないのではないかと思いましたが、それらをプルーニングしたかったので、どうすればよいかわかりません