Match brackets the kotlin way

Question

I'm giving Kotlin a go; coding contently, I have an ArrayList of chars which i want to classify depending on how brackets are matched:

(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

My solution comes out(recursive):

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

This works, but is this how you do it in Kotlin? It feels like I've coded java in Kotlin syntax

Found this Functional languages better at recursion, I've tried thinking in terms of manipulating functions and sending them down the recursion but to no avail. I'd be glad to be pointed in the right direction, code, or some pseudo-code of a possible refactoring.

(Omitted some extension methods regarding brackets, I think it's clear what they do)

Answer 1

Another, possibly a simpler approach to this problem is maintaining a stack of brackets while you iterate over the characters.

When you encounter another bracket:

• If it matches the top of the stack, you pop the top of the stack;

• If it does not match the top of the stack (or the stack is empty), you push it onto the stack.

If any brackets remain on the stack at the end, it means they are unmatched, and the answer is false. If the stack ends up empty, the answer is true.

This is correct, because a bracket at position i in a sequence can match another one at position j, only if there's no unmatched bracket of a different kind between them (at position k, i < k < j). The stack algorithm simulates exactly this logic of matching.

Basically, this algorithm could be implemented in a single 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()

_{I've reused your extensions c.isBracket(...) and c.matchesBracket(...). The Stack<T> is a JDK class.}

This algorithm hides the recursion and the brackets nesting inside the abstraction of the brackets stack. Compare: your current approach implicitly uses the function call stack instead of the brackets stack, but the purpose is the same: it either finds a match for the top character or makes a deeper recursive call with another character on top.

Answer 2

Hotkey's answer (using a for loop) is great. However, you asked for an optimized recursion solution. Here is an optimized tail recursive function (Note the tailrec modifier before the 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())}")
}

This function calls itself until the input becomes empty and returns true if the stack is empty when the input becomes empty.

If we look at the decompiled Java equivalent of the generated bytecode, this recursion has been optimized to an efficient while loop by the compiler so we won't get StackOverflowException (removed Intrinsics null checks):

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