递归地检查给定的字符串是否是平衡括号字符串 [英] Check if a given string is balanced brackets string, recursively

问题描述

作为 Java 新手(和编程)，我遇到了分配给我们的作业的麻烦.分配分为 3 部分，以检查给定的字符串是否有平衡括号.

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.

规则"如下:

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

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

任务的第一部分是编写一个方法，该方法将获取一个包含字符串的字符数组，并会找到包含括号的第一个索引(= 数组单元格)，以下之一:

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:

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

这当然很容易做到:

/**
 * 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(相反是假的！)， 1st='<' 2nd='e' = false ).这也没有问题:

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:

/**
 * 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"当且仅当字符串是平衡括号字符串.当然，我们需要使用我们编写的第 1 和 2 种方法，而且我们还得到了一个提示:

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:

提示:使用辅助方法，会得到 2 个字符串

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

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

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

否则返回false.在编写代码本身时，我目前卡住了，不知道如何从我的代码中第 26 行的递归调用继续此方法:

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:

/**
 * 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，我不知道如何继续.

I don't know how to continue if the recursive code from line 26 will return 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.

推荐答案

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

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:

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

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

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

算法(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

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

Note that i have imported the following classes:

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

这篇关于递归地检查给定的字符串是否是平衡括号字符串的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！