Проверьте, соответствует ли данная строка сбалансированным скобкам строка, рекурсивно

Question

У меня возникла проблема с новичком в java (и вообще программированием) с заданием, которое нам было дано. Назначение делится на 3 части, чтобы проверить, имеет ли данная строка сбалансированные скобки.

"правила" являются следующие:

• "abcdefksdhgs" - сбалансирован
• "[{aaa<bb>dd}]<232>" - сбалансирован
• "[ff{<gg}]<ttt>" - не сбалансирован (не закрытия для '<')
• "{<}>" - НЕ сбалансирован

1-й части задания было написать метод, который получит массив символов, содержащий строку, и будет найти первый индекс (= массив ячеек), содержащий кронштейн, одно из следующих действий:

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

это, конечно, было легко сделать:

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

2-ая часть была написать метод, который получит два символа, и возвращает истину, только если второй символ является подходящим закрывающая скобка первого гольца (пример: первый = '<' 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 

3-я часть, чтобы написать рекурсивный метод, который получит строку, и возвращает «истинный» тогда и только тогда, когда строка сбалансирована струна скобки. Конечно, мы должны использовать 1-й 2-й & методы, которые мы уже писали, а также нам дали подсказку:

ПОДСКАЗКА: использовать метод помощи, который получит 2 строки

В этой части я» m застрял. Я придумал несколько случаев остановки:

1. если нет скобка вообще в данной строке - возвращает истинное
2. , если данная строка пуста возвращающие (этот вариант рассматривается в 1-й метод)
3. при обнаружении открытого кронштейна, а закрывающая скобка соответствия - возвращает истину

в противном случае, возвращение ложным. в коде записываясь, я в настоящее время застрял и не знаю, как дальше от рекурсивного вызова в строке 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

Идея заключается в том, чтобы сохранить список открытых скобок, и если вы найдете закрывающий brackt, проверьте, если он закрывает последний открыто:

• Если те матчи скобки, а затем удалите последние отрытые из список открытых брейков и продолжить рекурсивно проверять остальную строку.
• Кроме того, вы обнаружили скобки, которые закрывают один из серверов, один раз открываются, поэтому он не сбалансирован.

Когда струна, наконец, пустая, если список brackes пуст тоже (так что все brackes было закрыто) вернуться 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); 
    } 
} 

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

ВЫХОД:

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 2

Ваш индекс скобок - отличное стартовое место, но, я думаю, вам нужно еще несколько компонентов.

Во-первых, вы должны уметь проверять только небольшую часть строки. Таким образом, ваша подпись должна быть checkBalanced(String str, int start, int end). Когда вы начинаете сначала строку, это будет checkBalanced(String str) { return checkBalanced(str,0,str.length()-1; }, так как «маленькая» секция, с которой она начинается, оказывается всей строкой.

Затем я начинал с начала строки и находил первую скобку. Затем я начинаю оттуда и работаю, пока не нахожу подходящую закрывающую скобу первой скобки. Если бы я сделал это через строку без каких-либо фигурных скобок, я вернусь. Если бы я сделал это через строку и нашел закрывающую фигуру, прежде чем я нашел открытую фигурную скобку, я возвращаю ложь. Это ваши базовые случаи и требуются в любом рекурсивном алгоритме.

Если я нашел скобу, как ожидалось, я запустил свой checkBalanced на подстроке между ними, и я запустил checkBalanced на подстроке сразу после закрытия скобки до конца строки. (Обратите внимание, что «конец строки» не является string.length(), а скорее конечным индексом, который был передан. Нам остается только учитывать диапазон, переданный методу, когда мы находимся в этом методе.) Это ваши фактические рекурсии, и в этом случае у вас есть два из них.

Answer 3

Использование регулярных выражений. Если есть такие случаи: <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 

Answer 4

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

Answer 5

Вы ван использовать стек для отслеживания следующего соответствующего кронштейна ожидается.Следующий код будет работать:

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