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

Question

作为一名java(和编程)新手，我在完成分配给我们的任务时遇到了麻烦。作业分为三部分，检查给定的字符串是否有平衡括号。

“规则”如下：

• "abcdefksdhgs"-是平衡的
• "[{aaa

赋值的第一部分是编写一个方法，该方法将获取包含字符串的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=）

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

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

在这一部分，我被困住了。我提出了几个停止案例：

1. 如果给定字符串中根本没有括号-返回true
2. 如果给定的字符串为空，则返回true（此选项包含在第1个方法中）
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

匿名用户

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

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

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

如果我如预期的那样找到了大括号，我将对两者之间的子字符串运行checkBalanced，并对紧接在右大括号之后到字符串末尾的子字符串运行checkBalanced。(注意“字符串结尾”不是string.length()，而是传入的结尾索引。当我们在这个方法中时，我们只关心传递给这个方法的范围。)这些是你实际的递归，在这种情况下你有两个。

Answer 2

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

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

当字符串最终为空时，如果括号列表也为空（因此所有括号都已关闭）返回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;

Answer 3

您可以使用堆栈来跟踪预期的下一个相应括号。以下代码将起作用：

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