遞歸確定嵌套圓括號（JAVA）

我想寫一個方法來確定一個字符串中括號的嵌套對。實例：「（（））」爲真「（（4））」爲假「（）（）」爲假「（（（））」爲假遞歸確定嵌套圓括號（JAVA）

public static boolean nestedBrackets(String s){ 
if(s.length()<4){ 
return false; 
} 
    else if(s.charAt(0) == '('&&s.charAt(s.length()-1)== ')'){ 

    if(s.charAt(1)=='('&&s.charAt(s.length()-2)==')'&&s.length()==4){ 
     return true; 
    } 
     else if(s.charAt(2)=='(' && s.charAt(s.length()-3)==')'&&s.length()==6){ 
     return true; 
     } 

    else { 
     return false; 
    } 
    } 
    else { 
    return false;

來源

2014-04-22 user3513461

你目前的實施有什麼問題？ –

@EricJ。它（（（））條件失敗，因爲它返回true。OP，nester parens的規則是什麼？原始字符串是否只包含parens？ –

這需要使用堆棧。需要知道嵌套級別 – Boj

要做到這個遞歸，我們需要思考的問題歸納所以我的基礎情形是：

沒有括號離開返回true
非成對括號離開，返回假

我感性的步驟將是：從左邊

開始，找到第一個（如果我找到一個），然後從右側返回false

開始，並找到第一），如果我找到一個（返回false

如果我從右邊找到一個（從左邊開始），然後將字符串縮小到它們之間的子串並進行遞歸。

所以，pseudoishcode會是什麼樣子：

Public Boolean ParenFinder(String testString){ 
    int left = 0; 
    int right = 0; 
    for (int i = 0; i < testString.length(); i++){ 
     if (testString.charAt(i) == '('){ 
       left = i; 
       break; 
     } 
     if (testString.charAt(i) == ')'){ 
       return false; 
     } 
    } 
    for (int i = testString.length(); i > 0; i--){ 
     if (testString.charAt(i) == ')'){ 
       right = i; 
       break; 
     } 
     if (testString.charAt(i) == '('){ 
       return false; 
     } 
    } 

    if (left == 0 && right == 0 && testString.charAt(0) != '(') 
        return true; 
    return (ParenFinder(testString.subString(left, right));    
}

來源

2014-04-22 01:03:05

@ user3513461您可能需要根據您的確切規則對其進行調整 –

由於您的問題被標記「遞歸」遞歸解決方案提供。

public static boolean nestedBrackets(String s) 
{ 
    if (s.length() < 2) 
    { 
     return false; 
    } 
    if (s.charAt(0) != '(') 
    { 
     return false; 
    } 
    if (s.charAt(s.length() - 1) != ')') 
    { 
     return false; 
    } 
    if (s.length() == 2) 
    { 
     return true; 
    } 
    return nestedBrackets(s.substring(1, s.length() - 1)); 
}

實現很簡單。每次遞歸時，確保整個表達式在括號內，然後對括號內的內容進行遞歸。對於一對括號，終端條件達到：「（）」。

注意：您沒有提及空字符串大小寫（「」）的預期結果。以上提供的解決方案爲空字符串返回false。

來源

2014-04-22 01:32:20

遞歸確定嵌套圓括號（JAVA）

回答

相關問題