爲什麼這個遞歸方法有效？

我正在編寫一個函數來滿足這些要求：給定一個字符串，如果它是嵌套的零對或多對括號（如(())或((()))），則返回true。建議：檢查第一個和最後一個字符，然後重新發現裏面的內容。爲什麼這個遞歸方法有效？

nestParen("(())") → true 
nestParen("((()))") → true 
nestParen("(((x))") → false

在網站上顯示的正確的解決方案是：

public boolean nestParen(String str) { 
    if (str.equals("")) return true; 
    if (str.charAt(0) == '(' && str.charAt(str.length()-1) == ')') 
     return nestParen(str.substring(1,str.length()-1)); 
    else 
     return false; 
}

我不明白爲什麼這個工程。如果給定的字符串有一個(之外的字符，如"，它不會碰到else情況並返回false而不是跳到下一個(？

來源

2014-10-17 Sarah Markers

你是對的; 'nestParen（「（（x））」）'將返回false。 – 2014-10-17 17:31:18

是的，它會像要求說的那樣。 – 2014-10-17 17:31:19

這些字符串都不包含'「'字符 – AdamMc331 2014-10-17 17:31:20

如許多示例代碼似乎很典型，建議的正確解決方案是不正確的。

這裏是一個真正正確的解決方案：

public boolean nestParen(final String value) 
{ 
    if (value != null) 
    { 
     if (value.isEmpty()) 
     { 
      return true; 
     } 

     if (value.charAt(0) == '(' && value.charAt(value.length()-1) == ')') 
     { 
      return nestParen(value.substring(1, value.length()-1)); 
     } 
     else 
     { 
      return false; 
     } 
    } 
    else // value is null 
    { 
     return true; 
    } 
}

說明：（同與其他的答案）

如果該參數不爲空，繼續。這可以防止NullPointerExceptions。
如果參數爲空，則返回true。如果一個字符串包含零個或多個嵌套parens對而沒有其他東西，問題似乎會返回true。
如果第一個字符是'（'，最後一個字符是'）'，去掉這些字符並再次檢查（這是遞歸）。（其中第一個不是'（'和/或最後一個不是'）'）返回false。
最後，如果參數爲null，則返回true（它包含零對，而不是其他任何東西）。

來源

2014-10-17 17:45:14 DwB

如果輸入的字符串包含一些其他的東西比(和)，使這項工作只需要調用另一個函數像下面調用該函數之前這肯定是不行的：

clean(String str){ 
    String str = "(((X+y)+z))"; 
    String retStr = ""; 
    for(int i = 0 ; i<str.length() ; i++){ 
     if(str.charAt(i) == '(' || str.charAt(i) == ')') 
     { 
      retStr += str.charAt(i); 
     } 
    } 
    return retStr 
}

，然後打電話給你的遞歸功能，輸入retStr。

來源

2014-10-17 17:45:43 Lrrr

爲什麼這個遞歸方法有效？

回答

相關問題