Java if 语句被跳过

Question

下面的方法接受一个字符串和一个模式，如果它们相互匹配，则 returns true。一个 '。'匹配 1 个字符，'*' 匹配 0 个或更多字符（例如 expMatch("abc", "a.c") 应该 return true）。我添加了一堆打印语句以查看我哪里出错了，即使 str.length() == 1 似乎也跳过了 if 语句。

我用System.out.println(expMatch("abc", "a*c"));

来称呼它

代码如下：

public static boolean expMatch(String str, String pat)
{   
    if (str.charAt(0) == pat.charAt(0) || pat.charAt(0) == '.')
    {
        System.out.println("in if");
        System.out.println(str.charAt(0));
        System.out.println(pat.charAt(0));
        System.out.println(str.length());
        if (str.length() == 1)
            return true;
        expMatch(str.substring(1), pat.substring(1));
    }

    else if (pat.charAt(0) == '*')
    {   
        System.out.println("in else");
        System.out.println(str.charAt(0));
        System.out.println(pat.charAt(0));
        if (str.length() == 1)
            return true;
        if (str.charAt(0) == pat.charAt(1)) //val of * = 0
            expMatch(str, pat.substring(1));
        else if (str.charAt(1) ==pat.charAt(1))
            expMatch(str.substring(1), pat.substring(1));           
    }

    return false;           
}

输出为：

in if
a
a
3
in else
b
*
in if
c
c
1
false

即使长度为 1 也会跳过 if？知道为什么吗？ P.S。我不是在寻找解决方案，只是为什么要跳过 if 语句。

Answer 1

您需要在调用 expMatch() 之前添加一个 return - 因为 false 来自您的最后一行 return false;

这是怎么回事：

你用这两个字符串调用 expMatch()。
你输入if子句
if子句递归进入expMatch()
你输入else子句
else子句递归进入expMatch()
你又输入了if子句
您离开 expMatch() 方法
你离开另一个 expMatch 方法
false 是 returned

Answer 2

你在最后的方法中总是 return false。您正在递归调用 expmatch 但从未使用 return 值。代码进入第一个 if，递归（因为长度不是 1）并且在 returning 将转到最后的 return 语句，returns false。

Answer 3

即使您应用了其他人建议的修复方法，您的方法在逻辑上也是不正确的。试试这个测试用例：

System.out.println(expMatch("abddddc", "a*c"));

这是因为当你在模式中遇到*时，你无法知道搜索字符串中有多少个字符"to eat"。

至少可以说，您需要在某处进行循环，而不仅仅是 if。让我尝试为您修复它（不确定是否可能，不确定您是否总是知道要走哪条路，我的意思是在您的递归中）。再考虑一下。这是另一个令人不快的测试用例：

System.out.println(expMatch("adddcac", "a*c")); 
// the * needs to eat dddca (despite the c present in dddca),  
// it should not stop recursing there at that c

我想你需要在这里进行某种全面搜索。
只有 if 或 while 循环是不够的。

编辑：这是一个固定版本，带有一堆讨厌的测试。我认为这称为 非线性递归（因为它不是您尝试的单一路径）。虽然对那个词不是 100% 确定。

public class Test055 {

    public static void main(String[] args) {
        // System.out.println(expMatch("abddddc", "a*c"));

        System.out.println(expMatch("adcax", "a*c"));
        System.out.println(expMatch("adcax", "a*c*"));

        System.out.println(expMatch("adcacm", "*"));
        System.out.println(expMatch("adcacmmm", "a*c"));
        System.out.println(expMatch("adcacmmmc", "a*c"));
        System.out.println(expMatch("adcac", "a*c"));

        System.out.println(expMatch("adcacxb", "a*c.b"));
        System.out.println(expMatch("adcacyyb", "a*c.b"));
        System.out.println(expMatch("adcacyyb", "a*c*b"));

    }

    public static boolean expMatch(String str, String pat)
    {
        // System.out.println("=====================");
        // System.out.println("str=" + str);
        // System.out.println("pat=" + pat);

        if (pat.length() == 0 && str.length() > 0) {
            return false;
        } else if (pat.length() == 0 && str.length() == 0) {
            return true;
        } else if (pat.charAt(0) == '.'){
            return str.length() >= 1 && expMatch(str.substring(1), pat.substring(1));
        }else if (pat.charAt(0) != '*'){
            return str.length() >= 1 && pat.charAt(0) == str.charAt(0) && expMatch(str.substring(1), pat.substring(1));
        }else{
            // Now let's handle the tricky part

            // (1) Look for the 1st non-star in pattern
            int k=-1;
            char ch = ' ';
            for (int i=0; i<pat.length(); i++){
                if (pat.charAt(i) != '*'){
                    k = i;
                    ch = pat.charAt(k);
                    break;
                }
            }

            if (k==-1){
                // (2A) only stars found in pattern, OK, any str matches that
                return true;
            }else{
                // (2B) do full search now checking all  
                // possible candidate chars in str that 
                // match the char ch from pattern
                for (int i=0; i<str.length(); i++){
                    if (str.charAt(i)==ch){
                        boolean b = expMatch(str.substring(i+1), pat.substring(k+1));
                        if (b) return true;
                    }
                }
                return false;
            }
        }
    }
}

Java if 语句被跳过

Java if-statement being skipped

java

recursion

if-statement