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

Check if a given string is balanced brackets string, recursively

提问by Adiel

I am having trouble as a newbie in java (and programming at all) with an assignment that was given to us. The assignment is divided to 3 parts, to check if a given string has balanced brackets.

作为 Java（和编程）的新手，我遇到了分配给我们的任务的麻烦。分配分为 3 部分，以检查给定的字符串是否具有平衡括号。

The "rules" are as follows:

“规则”如下：

• "abcdefksdhgs"- is balanced
• "[{aaa<bb>dd}]<232>"- is balanced
• "[ff{<gg}]<ttt>"- is NOT balanced ( no closure for '<' )
• "{<}>"- is NOT balanced

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

The 1st part of the assignment was to write a method that will get a char array containing a string, and will find the FIRST index (= array cell) containing a bracket, one of the following:

作业的第一部分是编写一个方法，该方法将获取包含字符串的 char 数组，并找到包含括号的第一个索引（= 数组单元格），以下之一：

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

That of course was easily done:

这当然很容易做到：

/**
 * 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

The 2nd part was to write a method that will get two chars, and return true only if the second char is the appropriate closing bracket of the first char (example: 1st='<' 2nd='>' = true (opposite is false!), 1st='<' 2nd='e' = false ). That was also no trouble:

第二部分是编写一个方法，该方法将获取两个字符，并且仅当第二个字符是第一个字符的适当右括号时才返回 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

The 3rd part is to write a RECURSIVE method, that will get a string, and will return "true" if and only if the string is balanced bracket string. Of course we need to use 1st&2nd methods we've written, and also we were given an hint:

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

HINT: use an aid method, that will get 2 strings

提示：使用辅助方法，将获得 2 个字符串

On this part I'm stuck. I've come up with several stop cases:

在这部分我被卡住了。我想出了几个停止案例：

1. if there is no bracket at all in the given string - return true
2. if the given string is empty return true (this option is covered in the 1st method)
3. if found open bracket, and a matching closing bracket - return true

1. 如果给定字符串中根本没有括号 - 返回 true
2. 如果给定的字符串为空，则返回 true（此选项包含在第一种方法中）
3. 如果找到左括号和匹配的右括号 - 返回 true

otherwise, return false. in the code writing itself, i'm currently stuck and don't know how to continue from the recursive calling in line 26 in my code for this method:

否则，返回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

I don't know how to continue if the recursive code from line 26 will return true.

如果第 26 行的递归代码返回 true，我不知道如何继续。

I'll be glad to get some guidance from the experts in here, on which direction to go, or I'm doing it all wrong from the start.

我很高兴能从这里的专家那里得到一些指导，告诉我该往哪个方向走，否则我从一开始就做错了。

采纳答案by Luca Mastrostefano

The idea is to keep a list of the opened brackets, and if you find a closing brackt, check if it closes the last opened:

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

• If those brackets match, then remove the last opened from the list of openedBrackets and continue to check recursively on the rest of the string
• Else you have found a brackets that close a nerver opened once, so it is not balanced.

• 如果这些括号匹配，则从openedBrackets 列表中删除最后打开的括号并继续递归检查字符串的其余部分
• 否则，您发现了关闭神经神经的括号打开一次，因此它不平衡。

When the string is finally empty, if the list of brackes is empty too (so all the brackes has been closed) return true, else false

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

ALGORITHM(in Java):

算法（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));
    }
}

OUTPUT:

输出：

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

Note that i have imported the following classes:

请注意，我导入了以下类：

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

回答by corsiKa

Your bracket index is a great starting place, but, I think you need a few more components.

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

First, you need to be able to check only a small part of the string. So your signature should be checkBalanced(String str, int start, int end). When you start a string initially, it would be checkBalanced(String str) { return checkBalanced(str,0,str.length()-1; }as the "small" section it starts with happens to be the entire string.

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

I would then start at the front of the string and find the first bracket. I then start from there and work until I hit the proper closing brace of the first bracket. If I made it through the string without any braces being found, I return true. If I made it through the string and found a closing brace before I found an opening brace, I return false. These are your base-cases, and are required in any recursive algorithm.

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

If I found the brace as expected, I run my checkBalanced on the substring between the two, and I run checkBalanced on the substring from immediately after the closing brace to the end of the string. (Note that "end of the string" is not string.length(), but rather the end index that was passed in. We only care about the range passed in to the method while we're in that method.) These are your actual recursions, and in this case you have two of them.

如果我按预期找到了大括号，我会在两者之间的子字符串上运行 checkBalanced，然后在子字符串上从右大括号之后到字符串末尾运行 checkBalanced。（请注意，“字符串的结尾”不是 string.length()，而是传入的结束索引。我们只关心在该方法中传入该方法的范围。）这些是您的实际的递归，在这种情况下，你有两个。

回答by Sergey Fedorov

Use regexp. If there are occurence like this: <bb>, (no brackets inside) replace it to zero string, repeat until success. Like that:

使用正则表达式。如果出现这样的情况：<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));
    }
}

Output:

输出：

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

回答by sai tvs

//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);
        }
    }
}

回答by Ling Zhong

You van use a Stack to keep track of the next corresponding bracket expected. The following code will work:

您使用 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();
}