Exploring Stack Operations in Kotlin

Introduction to the Lesson

Welcome back! As we continue to explore stack operations in Kotlin, remember how these structures serve similar functions in programming as they do in simple physical tasks. For instance, when you stack plates, the last one you put on top is the first one you'll take off when setting the table. A computer's stack allows us to temporarily put away pieces of data, just as we can pile those plates and retrieve them later in the reverse order of how they were placed. Today, we will apply the last-in, first-out principle to solve two specific problems that will solidify your understanding of stack operations in Kotlin.

Problem 1: Validating Parentheses

Validating nested structures such as parentheses is common in computing — it's like ensuring that a series of opened boxes are correctly closed. We will create a function to verify that a string of parentheses is properly nested and closed — essentially checking for balance.

Problem 1: Actualization

Unbalanced parenthesis can result in errors while coding in most programming languages. A potential use case of this function is making sure a conditional if-statement contains open and closing braces {} containing the statement to be executed.

Problem 1: Naive Approach

If we consider a simple way to approach this problem, we could initialize a counter variable for each type of bracket (parentheses, braces, and square brackets), increment the counters when we encounter an opening bracket, and decrement it when we get a closing bracket. Although this approach checks whether we have a closing bracket for every opening bracket, it completely misses one critical aspect — the order of brackets. For the brackets to be considered balanced, every closing bracket must correspond to the most recently opened bracket of the same type, which is not checked in this approach.

Problem 1: Efficient Approach

A stack data structure is an efficient way to solve this problem. The stack follows the LIFO (Last In, First Out) principle, which makes it highly suitable to track the order of opening and closing brackets, as the most recently opened bracket needs to be closed before we move on to the next opening bracket.

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

Kotlin

fun areBracketsBalanced(inputStr: String): Boolean {
    val bracketMap = mapOf('(' to ')', '[' to ']', '{' to '}')
    val openPar = setOf('(', '[', '{')
    val stack = ArrayDeque<Char>()
}

fun areBracketsBalanced(inputStr: String): Boolean {
    val bracketMap = mapOf('(' to ')', '[' to ']', '{' to '}')
    val openPar = setOf('(', '[', '{')
    val stack = ArrayDeque<Char>()
}

Kotlin

    for (character in inputStr) {
        when {
            openPar.contains(character) -> {
                stack.push(character)
            }
            stack.isNotEmpty() && character == bracketMap[stack.peek()] -> {
                stack.pop()
            }
            else -> {
                return false
            }
        }
    }
    return stack.isEmpty()
}

    for (character in inputStr) {
        when {
            openPar.contains(character) -> {
                stack.push(character)
            }
            stack.isNotEmpty() && character == bracketMap[stack.peek()] -> {
                stack.pop()
            }
            else -> {
                return false
            }
        }
    }
    return stack.isEmpty()
}

Kotlin

fun reverseString(str: String): String {
    val stack = ArrayDeque<Char>()
    for (char in str) {
        stack.push(char)
    }
    val reversed = StringBuilder()
    while (stack.isNotEmpty()) {
        reversed.append(stack.pop())
    }
    return reversed.toString()
}

fun reverseString(str: String): String {
    val stack = ArrayDeque<Char>()
    for (char in str) {
        stack.push(char)
    }
    val reversed = StringBuilder()
    while (stack.isNotEmpty()) {
        reversed.append(stack.pop())
    }
    return reversed.toString()
}

Kotlin

fun areBracketsBalanced(inputStr: String): Boolean {
    val bracketMap = mapOf('(' to ')', '[' to ']', '{' to '}')
    val openPar = setOf('(', '[', '{')
    val stack = ArrayDeque<Char>()
}

Kotlin

    for (character in inputStr) {
        when {
            openPar.contains(character) -> {
                stack.push(character)
            }
            stack.isNotEmpty() && character == bracketMap[stack.peek()] -> {
                stack.pop()
            }
            else -> {
                return false
            }
        }
    }
    return stack.isEmpty()
}

Kotlin

fun reverseString(str: String): String {
    val stack = ArrayDeque<Char>()
    for (char in str) {
        stack.push(char)
    }
    val reversed = StringBuilder()
    while (stack.isNotEmpty()) {
        reversed.append(stack.pop())
    }
    return reversed.toString()
}

Introduction to the Lesson

Problem 1: Validating Parentheses

Problem 1: Actualization

Problem 1: Naive Approach

Problem 1: Efficient Approach

Join the 1M+ learners on CodeSignal

Problem 1: Algorithm

Problem 1: Solution Building

Problem 2: Reverse a String using a Stack

Problem 2: Actualization

Problem 2: Approach Explanation

Problem 2: Solution Building

Lesson Summary