通配符匹配字符串

Question

我正在尝试编写一个函数bool match(char pattern[], char expresssion[]) 它检查模式是否与表达式匹配。如果 * 出现在模式中，它可以与任何字符串匹配 - 空字符串也是如此。这就是我的问题出现的地方。

我正在努力迎合这个明星。我的第一个想法是检查星号之后出现的下一个字符，看看它是否出现在表达式中。如果它出现在第 n 个位置，我在模式中移动一个字符并开始检查离第 n 个位置更远的表达式。然而，我应该从左边还是从右边检查我的表情并不总是很明显。例如 - 如果从左侧检查，则此测试将失败：

match("a*b", "ababab")

因为只有第一个 "b" 会被星星 "devoured"。相反，如果我从右边检查，那么这个测试就会失败：

match("a*b*b*", "abbbbbbbba")

你能告诉我如何处理这颗星吗？

Answer 1

诀窍是编写递归函数并匹配字符，直到找到“*”。一旦遇到“*”，那么任何事情都是公平的，所以你可以 return 为真。

bool match(char const *pattern, char const *file) {
    for (; *pattern != '[=10=]'; ++pattern) {
        switch (*pattern) {
        case '*': {
            //if pattern terminates after * then file can be anything, thus
            //terminate and return true.
            if (pattern[1] == '[=10=]')
                return true;
            //pattern doesn't terminate so cut off '*' from pattern,
            //increment file and repeat.
            size_t max = strlen(file);
            for (size_t i = 0; i < max; i++)
                if (match(pattern + 1, file + i))
                    return true;
            return false;
        }
        default:
            //if pattern doesn't specify a '?' or a '*', it must be a regular
            //character and so, must require a like for like match with file.
            if (*file != *pattern)
                return false;
            ++file;
        }
    }
    //we have iterated through the whole of pattern and so file must end too
    //if we are to match.
    return *file == '[=10=]';
}

然后您可以向 switch 语句添加额外的分支并向您的 glob 工具添加功能。例如，尝试为“?”添加逻辑。

通配符匹配字符串

Wildcard matching strings

c

string

algorithm

wildcard