Coincide con los corchetes de la manera kotlin

Voy a darle una oportunidad a Kotlin; Codificando con satisfacción, tengo una ArrayList de caracteres que quiero clasificar según cómo se combinen los corchetes:

(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 

Mi solución sale (recursiva):

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

Esto funciona, pero ¿así es como lo haces en Kotlin? Se siente como si hubiera codificado java en la syntax de Kotlin

Encontré estos lenguajes funcionales mejor en recursión , he intentado pensar en términos de manipulación de funciones y enviarlas por la recursión, pero fue en vano. Me alegraría que me señalaran en la dirección correcta, el código o algún seudocódigo de una posible refactorización.

(Omitido algunos methods de extensión con respecto a los corchetes, creo que está claro lo que hacen)

Otro, posiblemente un enfoque más simple para este problema es mantener una stack de corchetes mientras itera sobre los caracteres.

Cuando te encuentras con otro paréntesis:

  • Si coincide con la parte superior de la stack, aparece la parte superior de la stack;

  • Si no coincide con la parte superior de la stack (o la stack está vacía), la inserta en la stack.

Si algún paréntesis permanece en la stack al final, significa que no tienen igual, y la respuesta es false . Si la stack termina vacía, la respuesta es true .

Esto es correcto, porque un paréntesis en la position i en una secuencia puede coincidir con otro en la position j , solo si no hay un parche sin igual de un tipo diferente entre ellos (en la position k , i < k < j ). El algorithm de stack simula exactamente esta lógica de emparejamiento.

Básicamente, este algorithm podría implementarse en un solo 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() 

He reutilizado tus extensiones c.isBracket(...) y c.matchesBracket(...) . Stack<T> es una class JDK.

Este algorithm oculta la recursión y los corchetes que anidan dentro de la abstracción de la stack de corchetes. Compare: su enfoque actual usa implícitamente la stack de llamadas de function en lugar de la stack de corchetes, pero el propósito es el mismo: o encuentra una coincidencia para el personaje principal o realiza una llamada recursiva más profunda con otro personaje en la parte superior.

La respuesta de Hotkey (usando un bucle for) es genial. Sin embargo, solicitó una solución de recursión optimizada. Aquí hay una function recursiva optimizada de la queue (Observe el modificador tailrec antes de la function):

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

Esta function se llama a sí misma hasta que la input se vuelva vacía y devuelve verdadero si la stack está vacía cuando la input se vacía.

Si observamos el equivalente Java descomstackdo del bytecode generado, el comstackdor ha optimizado esta recursión en un ciclo while eficiente, por lo que no obtendremos StackOverflowException (se eliminarán las comprobaciones nulas de Intrinsics):

 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); } } 
  • El ejemplo de Kotlin Quasar no funciona
  • Error al usar un object para implementar una list vacía
  • Integración de HTML y CSS con Kotlin y Spring MVC
  • ¿Cómo funciona la interpolación de cadenas en Kotlin?
  • ¿Cómo declaras un campo polimórfico que usa JsonTypeInfo.As.WRAPPER_OBJECT con Jackson XML?
  • Android Architecture Components Room ViewModel CompleteableFormAction
  • ¿Cómo es útil la delegación de kotlin?
  • Proguard y Kotlin-Reflect / Kotlin Anotaciones
  • ¿No se puede agregar el conector mysql en build.gradle para un proyecto de kotlin?
  • Las vistas no se muestran en ViewPager
  • Convención de nomenclatura de Kotlin para methods de retorno booleans