Java if語句被跳過

Question

下面的方法接受一個字符串和一個模式，如果它們相互匹配則返回true。一個 '。'匹配1個字符和'*'匹配0或更多（例如expMatch("abc", "a.c")應返回真實）。我添加了一堆打印語句來查看我出錯的地方，即使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它跳過如果？任何想法爲什麼？ P.S.我不在尋找解決方案，只是爲什麼if語句被跳過。

Answer 1

即使您應用其他人建議的修復，您的方法在邏輯上也是不正確的。試試這個測試案例：

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

這是因爲當你在模式遇到*，你沒有辦法知道有多少個字符從搜索字符串「吃」。

至少可以說，你需要一個循環，而不僅僅是一個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; 
      } 
     } 
    } 
} 

Answer 2

你需要你的expMatch前加一個return（）調用 - 因爲false來自你的最後一行return false;

什麼情況是這樣的：

• 調用expMatch（）與兩個字符串。
• 你進入if子句
• if子句進入expMatch（）遞歸
• 你進入else子句
• else子句進入expMatch（）遞歸
• 您再次進入if語句
• 你離開expMatch（）方法
• 你離開其他expMatch方法
• 返回false

Answer 3

您總是從最後的方法返回false。您正遞歸調用expmatch，但從不使用返回值。代碼進入第一個，如果遞歸（因爲長度不是1）並且在返回時會返回到返回false的最終返回語句。