编写带有节点步过的树状解析递归函数 [英] write trie parsing recursive function with node step over

问题描述

目的:该函数通过匹配输入字符串的路径后面的字符串 trie 进行解析.当字符串中的所有字符都被解析后，返回true.如果仍然存在有效路径，我想跳过一个字符并返回.

The purpose: This function parses through a string trie following the path that matches an input string of characters. When all the char in the string are parsed, true is returned. I want to step over a char and return if there is still a valid path.

应用程序:字符串是高速公路项目的位置层次结构.因此，项目 5 有一个路线 C，其偏移量为 N，工作区为 3；5CN3.但是，有时我想为涵盖所有位置的项目任务定义所有子位置的字符串.因此，0"是所有位置；对于半天的操作，如等级泥土没有工作区 - 所有代表这项任务的都是北线 C 中的所有工作区；5CN0.如果操作涵盖整个项目，则相同；5000.

The application: the strings are a location hierarchy for a highway project. So, project 5 has an alignment C, that has an offset of N and a workzone 3; 5CN3. But, sometimes I want to define a string for all child locations for a project task that covers all the locations. So, '0' is all locations; for a half day operation like grade dirt has no workzones - all the so to represent this task is all workzones in the north alignment C; 5CN0. same for if an operation covers the whole project; 5000.

方法:我可以使用通配符 '?'函数，但为了抽象位置，我想保留此特定步骤.也许 '?'是正确的方法，但似乎失去了一些控制.此外，这可以在没有 for 循环的情况下编写并使用位置索引参数；也许这就是问题所在——也许是在回溯.

Approaches: I could have used a wildcard '?' function but I want to keep this specific step over for the purpose of abstracting the locations. Maybe '?' is the right approach, but seems to loose some control. Also, this could be written without the for loop and use a position index parameter; maybe that is where this goes wrong - maybe on backtracking.

Code:nodeT 是树节点，word 是输入字符串，这个函数是一个 bool 并且返回 1/0 如果字符串路径存在.

Code: nodeT is the trie nodes, word is the input string, this function is a bool and returns 1/0 if the string path exists.

bool Lexicon::containsWordHelper(nodeT *w, string word)) //check if prefix can be combined
{
    if(word == "") { //base case: all char found
        return true;
    } else {
        for(int i = 0; i < w->alpha.size(); i++) { //Loop through all of the children of the current node
            if (w->alpha[i].letter == word[0])
                return containsWordHelper(w->alpha[i].next, word.substr(1));
            else if (word[0] == '0') //if '0' then step over and continue searching for valid path
                containsWordHelper(w->alpha[i].next, word.substr(1)); //removed return here to allow looping through all the possible paths
        } //I think it is continuing through after the loop and triggering return false
    }
    return false; //if char is missing - meaning the exact code is not there
}

问题在于，当使用0"通配符时，这会返回 false.这里出了什么问题?我的知识有限.

The problem is that this returns false when a '0' wildcard is used. What is going wrong here? My knowledge is limited.

我解决了这个问题一段时间并使用了howboutthis howboutthat"方法，发现将 return 放在 step over 语句的末尾是有效的.

I hacked on this problem for awhile and used the 'howboutthis howboutthat' approach, and found that placing the return at the end of the step over statement works.

bool Lexicon::containsWordHelper(nodeT *w, string word, int &time, int &wag, string compare) //check if prefix can be combined
{
    if(word == "") { //base case: all letters found
        if ((w->begin-wag) <= time && time <= (w->end+wag)) 
            return w->isWord; // case 2: timecard check for high/low date range
        else if (time == ConvertDateToEpoch(9999, 01, 01)) return w->isWord; //this is for single code lookup w/o date
    } else {
        for(int i = 0; i < w->alpha.size(); i++) { //Loop through all of the children of the current node
            if (w->alpha[i].letter == word[0])
                return containsWordHelper(w->alpha[i].next, word.substr(1), time, wag, compare);
            else if (word[0] == 'ž')
                if (containsWordHelper(w->alpha[i].next, word.substr(1), time, wag, compare)) return true;
        }
    }
    return false; //if char is missing - meaning the exact code is not there
}

如果我只返回以 true 结尾的路径，那么我应该在递归完成后放置返回，然后仅在 true 时有条件地返回，这似乎是合乎逻辑的.回想起来，它是有效的，而且似乎是合乎逻辑的，但我对此的信心充其量只是粗略的.

It seems logical that if I only one the path that ends in true to return then I should place the return after the recursion is done and then conditionally pass back only if true. It works and seems logical in retrospect, but my confidence in this is sketchy at best.

我仍然有同样的问题.出了什么问题?

I still have the same question. What is/was going wrong?

推荐答案

已解决:在包含递归调用的 if 语句之后放置 return

Solved: place a return after an if statement containing the recursive call

bool Lexicon::containsWordHelper(nodeT *w, string word) 
    {
        if(word == "") return w->isWord;
        else {
            for(int i = 0; i < w->alpha.size(); i++) {
                if (w->alpha[i].letter == word[0])
                    return containsWordHelper(w->alpha[i].next, word.substr(1));
                else if (word[0] == 'ž')
                    if (containsWordHelper(w->alpha[i].next, word.substr(1))) return true;
            }
        }
        return false;
    }

这篇关于编写带有节点步过的树状解析递归函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！