作为一名java新手（以及编程新手），我在分配给我们的任务时遇到了麻烦。该任务分为3部分，用于检查给定字符串是否有平衡括号。
"规则"如下：
"abcdefksdhgs"-平衡"[{aaa<bb>dd}]<232>"-平衡"[ff{<gg}]<ttt>"-不平衡（"<"没有闭包）"{<}>"-不平衡
任务的第一部分是编写一个方法，该方法将获得一个包含字符串的char数组，并将找到包含括号的第一个索引（=数组单元格），括号是以下内容之一：
} , { , ] , [ , ( , ) , > , <
这当然很容易做到：
/**
* 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（例如：1st='<'2nd='>'=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 == '<') && (secondChar == '>') ){
return true;
}//if
return false;
}//end of checkBracket
第三部分是编写一个RECURSIVE方法，该方法将获得一个字符串，并返回"true"当且仅当字符串是平衡括号字符串。当然，我们需要使用1st&我们已经编写了第二种方法，并且我们得到了一个提示：
提示：使用辅助方法，将获得2个字符串
在这方面我被卡住了。我提出了几个停止案例：
- 如果给定字符串中根本没有括号，则返回true
- 如果给定的字符串为空，则返回true（此选项包含在第一个方法中）
- 如果找到开括号和匹配的闭括号，则返回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，我不知道如何继续。
我很高兴能从这里的专家那里得到一些指导，告诉我该朝哪个方向走，否则我从一开始就做错了。
您可以使用Stack来跟踪下一个相应的括号。以下代码将起作用：
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();
}
我们的想法是保留一个打开的括号列表，如果你发现一个正在关闭的bracket，请检查它是否关闭了最后一个打开：
- 如果这些括号匹配，则从openedRackets列表中删除最后打开的括号，并继续递归检查字符串的其余部分
- 否则，你会发现一个括号关闭了一个打开过一次的神经，所以它是不平衡的
当字符串最终为空时，如果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);
}
}
测试：
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;
您的括号索引是一个很好的起点，但是，我认为您还需要一些组件。
首先，您需要能够只检查字符串的一小部分。所以你的签名应该是checkBalanced(String str, int start, int end)。当您最初开始一个字符串时，它将是checkBalanced(String str) { return checkBalanced(str,0,str.length()-1; }，因为它开始的"小"部分恰好是整个字符串。
然后我会从绳子的前面开始，找到第一个括号。然后，我从那里开始工作，直到我打到第一个括号的正确闭合括号。如果我在没有找到任何大括号的情况下穿过字符串，我会返回true。如果我穿过字符串，在找到左大括号之前找到了右大括号，则返回false。这些是您的基本情况，在任何递归算法中都是必需的。
如果我找到了预期的大括号，我会在这两者之间的子字符串上运行checkBalanced，并从右大括号后的子字符串到字符串末尾运行checkBalance。（请注意，"字符串的末尾"不是string.length（），而是传入的结束索引。当我们在该方法中时，我们只关心传入该方法的范围。）这些是你实际的递归，在这种情况下你有两个。
使用regexp。如果出现这样的情况：<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
//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);
}
}
}