Вопрос:
Я пытаюсь написать метод, который определяет вложенные пары круглых скобок в строке. Примеры: “(())” истинно “((4))” false “()()” false “((())” false
public static boolean nestedBrackets(String s){ if(s.length()<4){ return false; } else if(s.charAt(0) == ‘(‘&&s.charAt(s.length()-1)== ‘)’){ if(s.charAt(1)=='(‘&&s.charAt(s.length()-2)==’)’&&s.length()==4){ return true; } else if(s.charAt(2)=='(‘ && s.charAt(s.length()-3)==’)’&&s.length()==6){ return true; } else { return false; } } else { return false; Ответ №1
Поскольку ваш вопрос помечен как “рекурсия”, предлагается рекурсивное решение.
public static boolean nestedBrackets(String s) { if (s.length() < 2) { return false; } if (s.charAt(0) != ‘(‘) { return false; } if (s.charAt(s.length() — 1) != ‘)’) { return false; } if (s.length() == 2) { return true; } return nestedBrackets(s.substring(1, s.length() — 1)); }
Реализация прост. С каждой рекурсией убедитесь, что все выражение находится в круглых скобках, а затем запишите содержимое в круглых скобках. Конечное условие достигается для одной пары круглых скобок: “()”.
Примечание. Вы не укажете ожидаемый результат для пустого флага (“”). Вышеприведенное ниже решение возвращает false для пустой строки.
Ответ №2
Чтобы сделать это рекурсивно, нам нужно подумать об индукции. Итак, мои базовые случаи:
- Не осталось парнов, которое возвращает true
- не парный парен слева, который возвращает false
Мой индуктивный шаг:
начните с левой стороны и найдите первый (если я найду a), тогда верните false
начинать с правой и находить первый), если я найду (return false
если я нахожу (слева и справа) справа, а затем сжимаю строку до подстроки между ними и рекурсивно.
Итак, псевдоид будет выглядеть так:
Public Boolean ParenFinder(String testString){ int left = 0; int right = 0; for (int i = 0; i < testString.length(); i++){ if (testString.charAt(i) == ‘(‘){ left = i; break; } if (testString.charAt(i) == ‘)’){ return false; } } for (int i = testString.length(); i > 0; i—){ if (testString.charAt(i) == ‘)’){ right = i; break; } if (testString.charAt(i) == ‘(‘){ return false; } } if (left == 0 && right == 0 && testString.charAt(0) != ‘(‘) return true; return (ParenFinder(testString.subString(left, right)); }
