检查一个给定的字符串是否平衡括号字符串，递归地

Question

我作为一个新手在Java（和编程的所有）与赋予给我们的任务麻烦。分配分为3部分，以检查给定字符串是否有平衡括号。

的 “规则” 如下：

• "abcdefksdhgs" - 平衡
• "[{aaa<bb>dd}]<232>" - 平衡
• "[ff{<gg}]<ttt>" - 不均衡（不封闭的 '<'）
• "{<}>" - 不平衡

分配的第一部分是写，将得到字符数组包含字符串， 并且将找到的第一个索引包含托架（=阵列单元），执行以下操作之一的方法：

} , { , ] , [ , (,) , > , < 

当然，这是很容易做到：

/** 
* bracketIndex - 1st Method: 
* this method will get a single string (read from the text file), 
* and will find the first index char that is any bracket of the following: },{,],[,(,),>,< 
* @param str1 - the given string. 
* @return index - the first index that contains character that is one of the brackets listed above. 
*/ 
public static int bracketIndex(String str1){ 
     int index = -1; // default value: didn't find any bracket in the string. 
     int i = 0; 
     for(i = 0; i < str1.length(); i++){ 
       if(str1.charAt(i) == '}' || str1.charAt(i) == '{' || str1.charAt(i) == ']' || str1.charAt(i) == '[' || str1.charAt(i) == '(' || str1.charAt(i) == ')' || str1.charAt(i) == '>' || str1.charAt(i) == '<'){ 
         return index = i; 
       }//if 
     }//for 
     return index; 
}//end of bracketIndex 

第二部分是写将得到两个字符，并返回true的方法只有当第二个字符是第一个字符的适当的右括号（例如：1 ='<'2nd ='>'= true（相反是假！），1st ='<'2nd = 'e'= false）。这也没有问题：

/** 
* checkBracket - 2nd Method: 
* 
* @param firstChar, secondChar - two chars. 
* @return True - if the the two chars are brackets, in which the second char is the closing bracket of the first char 
*/ 
public static boolean checkBracket(char firstChar, char secondChar){ 
     if ( (firstChar == '(') && (secondChar == ')') || 
         (firstChar == '[') && (secondChar == ']') || 
         (firstChar == '{') && (secondChar == '}') || 
         (firstChar == '<') && (secondChar == '>') ){ 
       return true; 
     }//if 
     return false; 
}//end of checkBracket 

第三部分是写一个递归方法，会得到一个字符串，并将返回“真” 当且仅当该字符串是平衡支架字符串。当然，我们需要使用我们已经写1 &第二方法，也是我们得到一个提示：

提示：使用的辅助方法，将得到2串

在这部分我米卡住了。我想出了几个停车情况：

1. 如果没有括号都在给定的字符串 - 返回true
2. 如果给定的字符串为空，则返回true（这个选项被覆盖在第一方法）
3. 如果找到打开支架，以及匹配闭架 - 返回true

否则，返回false。在代码 写作本身，我目前卡住，不知道如何从递归调用继续行26在我的代码这种方法：

/** 
* checkBalance - 3rd Method: 
* will check if a given string is a balanced string. 
* @param str1 - the given string to check. 
* @return true - if the given string is balanced, false - if the given string isn't balanced. 
*/ 
public static boolean checkBalance(String str1){ 
     boolean ans; 
     int a = bracketIndex(str1); 
     if (a == -1){ 
       return ans = true; 
     }//if 
     if(str1.charAt(a) == '{' || 
         str1.charAt(a) == '[' || 
         str1.charAt(a) == '<' || 
         str1.charAt(a) == '(' ){ 
       int b = bracketIndex(str1.substring(a))+1 ; 
       if(b != 0){ 
         if(checkBracket (str1.charAt(a), str1.charAt(b)) == true){ 
           return ans = true; 
         }//if 
         if(str1.charAt(b) == '{' || 
             str1.charAt(b) == '[' || 
             str1.charAt(b) == '<' || 
             str1.charAt(b) == '(' ){ 
           checkBalance(str1.substring(b-1)); 
         }//if 
         else{ 
           return ans = false; 
         }//else 
       }//if 
     }//if 
     return ans = false; 
}//end of checkBalance 

我不知道该怎么继续，如果来自第26行的递归代码将返回true。

我很乐意从这里的专家那里得到一些指导，告诉我要走向哪个方向，或者我从一开始就做错了一切。

Answer 1

的想法是保持打开的括号的列表，如果你找到一个封闭brackt，检查是否关闭最后打开：

• 如果这些括号匹配，则删除最后从打开然后继续对字符串的其余部分进行递归检查
• 否则您发现一个括号会关闭一次打开的神经，所以它不是平衡的。

当弦终于空，如果brackes的列表为空太（所以所有的brackes已关闭）返回true，否则false

算法（在Java中）：

public static boolean isBalanced(final String str1, final LinkedList<Character> openedBrackets, final Map<Character, Character> closeToOpen) { 
    if ((str1 == null) || str1.isEmpty()) { 
     return openedBrackets.isEmpty(); 
    } else if (closeToOpen.containsValue(str1.charAt(0))) { 
     openedBrackets.add(str1.charAt(0)); 
     return isBalanced(str1.substring(1), openedBrackets, closeToOpen); 
    } else if (closeToOpen.containsKey(str1.charAt(0))) { 
     if (openedBrackets.getLast() == closeToOpen.get(str1.charAt(0))) { 
      openedBrackets.removeLast(); 
      return isBalanced(str1.substring(1), openedBrackets, closeToOpen); 
     } else { 
      return false; 
     } 
    } else { 
     return isBalanced(str1.substring(1), openedBrackets, closeToOpen); 
    } 
} 

TEST：

public static void main(final String[] args) { 
    final Map<Character, Character> closeToOpen = new HashMap<Character, Character>(); 
    closeToOpen.put('}', '{'); 
    closeToOpen.put(']', '['); 
    closeToOpen.put(')', '('); 
    closeToOpen.put('>', '<'); 

    final String[] testSet = new String[] { "abcdefksdhgs", "[{aaa<bb>dd}]<232>", "[ff{<gg}]<ttt>", "{<}>" }; 
    for (final String test : testSet) { 
     System.out.println(test + " -> " + isBalanced(test, new LinkedList<Character>(), closeToOpen)); 
    } 
} 

输出：

abcdefksdhgs -> true 
[{aaa<bb>dd}]<232> -> true 
[ff{<gg}]<ttt> -> false 
{<}> -> false 

请注意，我已经导入以下类：

import java.util.HashMap; 
import java.util.LinkedList; 
import java.util.Map; 

Answer 2

您的括号索引是一个很好的起点，但我认为您需要更多的组件。

首先，您需要只能检查字符串的一小部分。所以你的签名应该是checkBalanced(String str, int start, int end)。当你最初启动一个字符串时，它将是checkBalanced(String str) { return checkBalanced(str,0,str.length()-1; }，因为它开头的“小”部分恰好是整个字符串。

然后我会从字符串的前面开始，找到第一个括号。然后我从那里开始工作，直到我击中第一个支架的正确右大括号。如果我在没有找到任何大括号的情况下通过了字符串，我将返回true。如果我通过弦线并在找到一个开口支架之前找到了一个闭合的大括号，我将返回false。这些是你的基本情况，并且在递归算法中是必需的。

如果我发现支撑如预期的那样，我在两者之间的子字符串上运行checkBalanced，并且我在从紧接大括号到字符串末尾之后立即在子字符串上运行checkBalanced。 （请注意，“字符串的结尾”不是string.length（），而是传入的结束索引。我们只关心在该方法中传递给该方法的范围。）这些是您的实际递归，在这种情况下，你有两个。

Answer 3

使用正则表达式。如果发生这种情况：<bb>，（无括号内）将其替换为零字符串，重复，直到成功。这样的：

static Pattern noBrackets = Pattern.compile("^[^\\[\\]{}()<>]*$"); 
static Pattern p = Pattern.compile("[{(<\\[][^\\[\\]{}()<>]*[})>\\]]"); 

static boolean balanced(String s) { 
    if (s.length() == 0) { 
     return true; 
    } 
    Matcher m = p.matcher(s); 
    if (!m.find()) { 
     m = noBrackets.matcher(s); 
     return m.find(); 
    } 
    boolean e; 
    switch (s.charAt(m.start())) { 
     case '{': 
      e = s.charAt(m.end() - 1) == '}'; 
      break; 
     case '[': 
      e = s.charAt(m.end() - 1) == ']'; 
      break; 
     case '(': 
      e = s.charAt(m.end() - 1) == ')'; 
      break; 
     case '<': 
      e = s.charAt(m.end() - 1) == '>'; 
      break; 
     default: 
      return false; 
    } 
    if (!e) { 
     return false; 
    } 
    return balanced(s.substring(0, m.start()) + s.substring(m.end())); 
} 

public static void main(String[] args) { 
    for (String s : new String[]{ 
     "abcdefksdhgs", 
     "[{aaa<bb>dd}]<232>", 
     "[ff{<gg}]<ttt>", 
     "{<}>" 
    }) { 
     System.out.println(s + ":\t" + balanced(s)); 
    } 
} 

输出：

abcdefksdhgs: true 
[{aaa<bb>dd}]<232>: true 
[ff{<gg}]<ttt>: false 
{<}>: false 

Answer 4

//basic code non strack algorithm just started learning java ignore space and time. 
/// {[()]}[][]{} 
// {[(-a -> }]) -b -> replace a(]}) -> reverse a(}]))-> 
//Split string to substring {[()]}, next [], next [], next{} 

public class testbrackets { 
    static String stringfirst; 
    static String stringsecond; 
    static int open = 0; 
    public static void main(String[] args) { 
     splitstring("(()){}()"); 
    } 
static void splitstring(String str){ 

    int len = str.length(); 
    for(int i=0;i<=len-1;i++){ 
     stringfirst=""; 
     stringsecond=""; 
     System.out.println("loop starttttttt"); 
     char a = str.charAt(i); 
    if(a=='{'||a=='['||a=='(') 
    { 
     open = open+1; 
     continue; 
    } 
    if(a=='}'||a==']'||a==')'){ 
     if(open==0){ 
      System.out.println(open+"started with closing brace"); 
      return; 
     } 
     String stringfirst=str.substring(i-open, i); 
     System.out.println("stringfirst"+stringfirst); 
     String stringsecond=str.substring(i, i+open); 
     System.out.println("stringsecond"+stringsecond); 
     replace(stringfirst, stringsecond); 

     } 
    i=(i+open)-1; 
    open=0; 
    System.out.println(i); 
    } 
    } 
    static void replace(String stringfirst, String stringsecond){ 
     stringfirst = stringfirst.replace('{', '}'); 
     stringfirst = stringfirst.replace('(', ')'); 
     stringfirst = stringfirst.replace('[', ']'); 
     StringBuilder stringfirst1 = new StringBuilder(stringfirst); 
     stringfirst = stringfirst1.reverse().toString(); 
    System.out.println("stringfirst"+stringfirst); 
    System.out.println("stringsecond"+stringsecond); 
if(stringfirst.equals(stringsecond)){ 
    System.out.println("pass"); 
} 
    else{ 
     System.out.println("fail"); 
     System.exit(0); 
     } 
    } 
} 

Answer 5

您面包车使用堆栈跟踪预计今后相应的支架。下面的代码将工作：

public boolean isValid(String s) { 
    HashMap<Character, Character> closeBracketMap = new HashMap<Character, Character>(); 
    closeBracketMap.put(')', '('); 
    closeBracketMap.put(']', '['); 
    closeBracketMap.put('}', '{'); 
    closeBracketMap.put('>', '<'); 
    HashSet<Character> openBracketSet = new HashSet<Character>(
     closeBracketMap.values()); 
    Stack<Character> stack = new Stack<Character>(); 
    char[] chars = s.toCharArray(); 
    for (int i = 0; i < chars.length; i++) { 
     char cur = chars[i]; 
     if (openBracketSet.contains(cur)) { 
      stack.push(cur); 
     } else if (closeBracketMap.keySet().contains(cur)) { // close brackets 
      if (stack.isEmpty()) { 
       return false; 
      } 
      if (closeBracketMap.get(cur) != stack.peek()) { 
       return false; 
      } 
      stack.pop(); 
     } 
    } 
    return stack.isEmpty(); 
}