CODEWITHSUNDEEP
javarecursion
Adiel
Adiel

Reputation: 1215

Check if a given string is balanced brackets string, recursively

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.

The "rules" are as follows:

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: 

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

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: 

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

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

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

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

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.

Upvotes: 4

Views: 12941

Answers (5)

Ling Zhong
Ling Zhong

Reputation: 1804

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

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

Upvotes: 1

sai tvs
sai tvs

Reputation: 1

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

Upvotes: 0

Sergey Fedorov
Sergey Fedorov

Reputation: 2169

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

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

Upvotes: 0

Luca Mastrostefano
Luca Mastrostefano

Reputation: 3271

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.

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

ALGORITHM (in 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;

Upvotes: 0

corsiKa
corsiKa

Reputation: 82579

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.

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.

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.

Upvotes: 0

Related Questions