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

我作为java中的新手（以及编程本身）遇到了麻烦，并给了我们一个赋值。 赋值分为3个部分，以检查给定的字符串是否具有平衡括号。

“规则”如下：

• "abcdefksdhgs" – 是平衡的
• "[{aaadd}]" – 是平衡的
• "[ff{<gg}]" – 不平衡（’ < ‘没有关闭）
• "{" – 不平衡

赋值的第一部分是编写一个方法来获取包含字符串的char数组，并找到包含括号的FIRST索引（=数组单元格），其中一个如下：

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

那当然很容易做到：

 /** * 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.charAt(i) == '<'){ return index = i; }//if }//for return index; }//end of bracketIndex 

第二部分是编写一个将获得两个字符的方法，并且只有当第二个字符是第一个字符的适当结束括号时才返回true（例如：1st =”= true（反之为false） ！），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 == '') ){ return true; }//if return false; }//end of checkBracket 

第三部分是编写一个RECURSIVE方法，它将获得一个字符串，并且当且仅当字符串是平衡括号字符串时才返回“true”。 当然我们需要使用我们编写的第一和第二种方法，并且我们还得到了一个提示：

提示：使用辅助方法，将获得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

我们的想法是保留一个打开的括号列表，如果你找到一个关闭的括号，检查它是否关闭了最后打开的括号：

• 如果这些括号匹配，则从opensBrackets列表中删除最后一个打开并继续以字符串的其余部分递归检查
• 否则你会发现一个括号可以关闭一个打开的神经，所以它不平衡。

当字符串最后为空时，如果括号列表也为空（所以所有的括号都已关闭）返回true ，否则为false

算法 （Java）：

 public static boolean isBalanced(final String str1, final LinkedList openedBrackets, final Map 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); } } 

测试 ：

 public static void main(final String[] args) { final Map closeToOpen = new HashMap(); closeToOpen.put('}', '{'); closeToOpen.put(']', '['); closeToOpen.put(')', '('); closeToOpen.put('>', '<'); final String[] testSet = new String[] { "abcdefksdhgs", "[{aaadd}]<232>", "[ff{", "{<}>" }; for (final String test : testSet) { System.out.println(test + " -> " + isBalanced(test, new LinkedList(), closeToOpen)); } } 

输出 ：

 abcdefksdhgs -> true [{aaadd}]<232> -> true [ff{ -> 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

使用正则表达式。 如果出现这样的情况： ，（内部没有括号）将其替换为零字符串，重复直到成功。 像那样：

 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", "[{aaadd}]<232>", "[ff{", "{<}>" }) { System.out.println(s + ":\t" + balanced(s)); } } 

输出：

 abcdefksdhgs: true [{aaadd}]<232>: true [ff{: 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 closeBracketMap = new HashMap(); closeBracketMap.put(')', '('); closeBracketMap.put(']', '['); closeBracketMap.put('}', '{'); closeBracketMap.put('>', '<'); HashSet openBracketSet = new HashSet( closeBracketMap.values()); Stack stack = new Stack(); 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(); }