Матч скобки kotlin способ

Я отдаю Котлин; кодируя, я имею ArrayList символов, которые я хочу классифицировать в зависимости от того, как скобки совпадают:

(abcde) // ok characters other than brackets can go anywhere )abcde( // ok matching the brackets 'invertedly' are ok (({()})) // ok )()()([] // ok ([)] // bad can't have different overlapping bracket pairs ((((( // bad all brackets need to have a match 

Мое решение выходит (рекурсивно):

 //charList is a property //Recursion starter'upper private fun classifyListOfCharacters() : Boolean{ var j = 0 while (j < charList.size ) { if (charList[j].isBracket()){ j = checkMatchingBrackets(j+1, charList[j]) } j++ } return j == commandList.size } private fun checkMatchingBrackets(i: Int, firstBracket :Char) : Int{ var j = i while (j < charList.size ) { if (charList[j].isBracket()){ if (charList[j].matchesBracket(firstBracket)){ return j //Matched bracket normal/inverted } j = checkMatchingBrackets(j+1, charList[j]) } j++ } return j } 

Это работает, но так ли это вы делаете в Котлине? Кажется, что я кодировал java в синтаксисе Котлина

Нашли это Функциональные языки лучше при рекурсии , я пробовал думать с точки зрения манипулирования функциями и отправки их по рекурсии, но безрезультатно. Я был бы рад, если бы был направлен в правильном направлении, код или какой-то псевдокод возможного рефакторинга.

(Опущены некоторые методы расширения в отношении скобок, я думаю, что ясно, что они делают)

    Другой, возможно, более простой подход к этой проблеме – это сохранение стопки скобок, в то время как вы перебираете символы.

    Когда вы сталкиваетесь с другим кронштейном:

    • Если он совпадает с верхней частью стека, вы выталкиваете верхнюю часть стека;

    • Если он не соответствует вершине стека (или стек пуст), вы вставляете его в стек.

    Если какие-либо скобки остаются в стеке в конце, это означает, что они не имеют аналогов, а ответ false . Если стек заканчивается пустым, ответ true .

    Это правильно, потому что скобка в позиции i в последовательности может соответствовать другой в позиции j , только если между ними нет несогласованной скобки другого типа (в позиции k , i < k < j ). Алгоритм стека имитирует именно эту логику сопоставления.

    В принципе, этот алгоритм может быть реализован в одиночном for -loop:

     val stack = Stack<Char>() for (c in charList) { if (!c.isBracket()) continue if (stack.isNotEmpty() && c.matchesBracket(stack.peek())) { stack.pop() } else { stack.push(c) } } return stack.isEmpty() 

    Я повторно использовал ваши расширения c.isBracket(...) и c.matchesBracket(...) . Stack<T> – класс JDK.

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

    Ответ на горячую клавишу (используя цикл for) отлично. Однако вы попросили оптимизированное решение для рекурсии. Вот оптимизированная функция хвостовой tailrec (обратите внимание на модификатор tailrec перед функцией):

     tailrec fun isBalanced(input: List<Char>, stack: Stack<Char>): Boolean = when { input.isEmpty() -> stack.isEmpty() else -> { val c = input.first() if (c.isBracket()) { if (stack.isNotEmpty() && c.matchesBracket(stack.peek())) { stack.pop() } else { stack.push(c) } } isBalanced(input.subList(1, input.size), stack) } } fun main(args: Array<String>) { println("check: ${isBalanced("(abcde)".toList(), Stack())}") } 

    Эта функция вызывает себя до тех пор, пока вход не станет пустым и вернет true, если стек пуст, когда вход становится пустым.

    Если мы рассмотрим декомпилированный Java-эквивалент сгенерированного байт-кода, эта рекурсия была оптимизирована для эффективного цикла while компилятором, поэтому мы не получим StackOverflowException (удаленные проверки Intrinsics null):

     public static final boolean isBalanced(@NotNull String input, @NotNull Stack stack) { while(true) { CharSequence c = (CharSequence)input; if(c.length() == 0) { return stack.isEmpty(); } char c1 = StringsKt.first((CharSequence)input); if(isBracket(c1)) { Collection var3 = (Collection)stack; if(!var3.isEmpty() && matchesBracket(c1, ((Character)stack.peek()).charValue())) { stack.pop(); } else { stack.push(Character.valueOf(c1)); } } input = StringsKt.drop(input, 1); } }