logo标签列表

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

javarecursion
4
我作为一个Java新手遇到了困难（也是在编程方面），我们被分配了一个任务。该任务分为三个部分，检查给定字符串是否具有平衡的括号。
"规则"如下：
- "abcdefksdhgs" - 平衡的 - "[{aaa<bb>dd}]<232>" - 平衡的 - "[ff{<gg}]<ttt>" - 不平衡（'<'没有关闭） - "{<}>" - 不平衡
任务的第一部分是编写一个方法，该方法将获取包含字符串的字符数组，并找到第一个包含以下括号的索引（=数组单元格）：
} , { , ] , [ , ( , ) , > , <

当然，这很容易实现：
/**
 * 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

第三部分是编写一个递归方法，该方法将获取一个字符串，并且仅当该字符串为平衡括号字符串时返回“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，我不知道该如何继续。

我很高兴能从这里的专家那里得到一些指导，告诉我应该朝哪个方向前进，或者我从一开始就做错了。

1
我想你可能没有完全理解这个提示。它的意思是说，主函数只需要接收一个参数并返回一个布尔值，而不需要是递归的本身。相反，应该有一个递归的辅助函数，它接收两个字符串（并返回其实现中方便的任何内容，例如整数索引或另一个字符串）。 - Blckknght
5个回答
1
你可以使用栈来跟踪下一个对应的括号。以下代码可行：
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();
}
0
//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);
        }
    }
}
0

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

  • 如果这些括号匹配，则从打开的括号列表中删除最后一个，并继续递归地检查其余的字符串
  • 否则，你找到了一个关闭从未打开过的括号，所以它不平衡。

当字符串最终为空时，如果括号列表也为空（因此所有括号都已关闭），返回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;
嘿，我听从了你的建议和主意，成功了！ 这是我最终使用的代码： http://pastebin.com/HzdUWU3U顺便说一下， 我没有使用所有那些导入的类，因为我们在课堂上还没有学习到它们，所以我不被允许使用。 - Adiel
太好了！你当然也可以使用字符串作为堆栈来保存打开的括号。实现得很好！ - Luca Mastrostefano
0
使用正则表达式。如果出现像这样的情况：<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
0

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

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

然后我会从字符串的开头开始找到第一个括号。然后我从那里开始工作，直到找到第一个括号的正确闭合括号。如果我在没有找到任何括号的情况下通过了字符串，我就返回true。如果我通过了字符串，并在找到开放括号之前找到了一个闭合括号，我就返回false。这些是递归算法中的基本情况，也是必需的。

如果我找到了预期的大括号，我将在两个子字符串之间运行checkBalanced，并在关闭大括号后立即运行checkBalanced以及字符串末尾的子字符串。 （请注意，“字符串的末尾”不是string.length()，而是传递的结束索引。在该方法中，我们只关心传递给该方法的范围。）这些是实际的递归，在这种情况下，您有两个递归调用。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接