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] != '?')

由于任何字符都不同于两者之一，也许您的意思是 (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

这段代码存在三个问题：

@Basile_Starynkevitch 指出了使用调试器跟踪路径的重要性——在这种情况下，使用 VS2008，堆栈允许解析步骤并注意通过多个函数返回的路径。

@Picarus 正确记录了终止条件中的错误

这些解决方案导致发现：

解决方案，这个 void 函数需要两个return;，一个在终止条件之后终止，另一个在结束时捕获修剪的线程。从几个网站上看，似乎a return;in a void 函数是不寻常的，但这种情况下具有递归和多路径，它是必需的。

于 2012-07-27T19:18:03.563 回答