Определить, сбалансирована ли строка, содержащая круглые скобки.

Question

Это школьное задание, которое пыталось решить в течение недели, я все еще не знаю, как получить реальный ответ. Если кто-то так добр и руководит мной с помощью каких-то твердых указателей, это будет действительно оценено, обратите внимание, что я не хочу решения. Например, строки(), [()], {([])},() [] представляют собой 4 сбалансированные строки.

Написать Рекурсивный метод: `

public static boolean isBalanced(String in) 

, которая возвращает истину, если в это сбалансированная Скобки строка и ложь, если это не так.

Вот часть кода Айв работает на:

public static boolean isBalanced(String in){ 
     if(in.length() == 0){ 
      return true; 
     } 
     char aux = in.charAt(0); 
     if(aux == '{' ||aux == '[' ||aux == '('){ 
      if(aux == '{'){ 
       return isBalanced(in.substring(1)); 
      } 
      if(aux == '}'){ 
       return false || isBalanced(in.substring(1)); 
      } 
      if(aux == '['){ 
       return isBalanced(in.substring(1)); 
      } 
      if(aux == ']'){ 
       return false || isBalanced(in.substring(1)); 
      }if(aux == '('){ 
       return isBalanced(in.substring(1)); 
      } 
      if(aux == ')'){ 
       return false || isBalanced(in.substring(1)); 
      } 
     } 
     return isBalanced(in.substring(1)); 
    } 

} 

Answer 1

Поскольку вы не хотите, решение вставить копию &, вы должны проверить это сообщение: https://stackoverflow.com/a/25854415/1057547

написано в PHP, но воплощает идею, которую вы легко адаптируете. Страница для «проверки» ваших данных по-прежнему доступна: http://dog-net.org/string.php, поэтому вы можете протестировать «огромные» строки без оформления документов.

---

По вашему мнению, вам необходимо реализовать рекурсивный подход. Таким образом, с дал подпись из isbalanced(String str) Есть два варианта, на мой взгляд, чтобы сгенерировать рекурсивный подход:

Во-первых, вы могли бы - в первом вызове рекурсии - итерации по строке с использованием описанных способов, до вы сбалансированы , но имеют оставшуюся строку. Тогда вам просто нужно рекурсивно вызвать метод на оставшейся строке.

Таким образом, для входной строки () [()]{([])}()[] стек вызовов должны стать:

isBalanced("()[()]{([])}()[]"); 
isBalanced("[()]{([])}()[]"); 
    isBalanced("{([])}()[]"); 
    isBalanced("()[]"); 
    isBalanced("[]"); 

Это, однако, будет не вдаваться в рекурсию для строк, как {([])} - потому что они могут быть обработаны в течение одного вызова.

Второй способ - ввести рекурсию в зависимости от «символов». Таким образом, вы всегда ищете подходящую скобку первого открывающего кронштейна в рамках ОДНОГО рекурсивного вызова, замените и и продолжите с другого вызова. Это было бы более медленное решение - по производительности - но позволяющее рекурсии с данной сигнатурой.

стеком вызовов, то должен выглядеть следующим образом:

isBalanced("()[()]{([])}()[]"); 
isBalanced("__[()]{([])}()[]"); 
    isBalanced("___()_{([])}()[]"); 
    isBalanced("______{([])}()[]"); 
    isBalanced("_______([])_()[]"); 
    isBalanced("________[]__()[]"); 
     isBalanced("____________()[]"); 
     isBalanced("______________[]"); 
     isBalanced("________________"); 

пс .: Независимо от того, что вы делаете, не забывайте добавлять

isBalanced(String str){ 
    if (str.length() % 2 != 0) return false; 
    ... 
} 

для "A +" :-)