Stacks and Queues

Balanced Parentheses

Walk a string of bracket characters. Push every opening bracket. On a closing bracket, pop and verify it matches; mismatch or empty-stack pop means unbalanced. At end of string, stack must be empty.

Algorithm

Canonical input "({[]})" (balanced) finishes with the stack empty and the result true.

stack push/pop Use an `ArrayDeque<Char>` as the open-bracket stack; push by `stack.addLast(ch)`, pop by `stack.removeLast()`.
matching map A small `matchOpen(close)` helper returns the expected opener for each closing bracket — three explicit `when` arms keep the lesson compact.

Basic Implementation

basic.kt
Replay: real traced execution (multi-file project)
fun matchOpen(close: Char): Char = when (close) {
	')' -> '('
	']' -> '['
	'}' -> '{'
	else -> ' '
}

fun main() {
	val text = "({[]})"
	val stack = ArrayDeque<Char>()
	var balanced = true
	for (i in text.indices) {
		val ch = text[i]
		if (ch == '(' || ch == '[' || ch == '{') {
			stack.addLast(ch)
		} else {
			if (stack.isEmpty() || stack.last() != matchOpen(ch)) {
				balanced = false
				break
			}
			stack.removeLast()
		}
	}
	if (stack.isNotEmpty()) {
		balanced = false
	}
	println(if (balanced) "True" else "False")
}

  1. text ← ({[]})

    8fun main() {9	val text = "({[]})"10	val stack = ArrayDeque<Char>()
    values this step({[]})text

  2. stack ← []

    9val text = "({[]})"10val stack = ArrayDeque<Char>()11var balanced = true
    values this step[]stack

  3. balanced ← true

    10val stack = ArrayDeque<Char>()11var balanced = true12for (i in text.indices) {
    values this steptruebalanced

  4. stack ← [(]

    12for (i in text.indices) {13	val ch = text[i]14	if (ch == '(' || ch == '[' || ch == '{') {
    values this step[(]stack(ch

  5. stack ← [(, {]

    12for (i in text.indices) {13	val ch = text[i]14	if (ch == '(' || ch == '[' || ch == '{') {
    values this step[(, {]stack{ch

  6. stack ← [(, {, []

    12for (i in text.indices) {13	val ch = text[i]14	if (ch == '(' || ch == '[' || ch == '{') {
    values this step[(, {, []stack[ch

  7. stack ← [(, {]

    12for (i in text.indices) {13	val ch = text[i]14	if (ch == '(' || ch == '[' || ch == '{') {
    values this step[(, {]stack]ch

  8. stack ← [(]

    12for (i in text.indices) {13	val ch = text[i]14	if (ch == '(' || ch == '[' || ch == '{') {
    values this step[(]stack}ch

  9. stack ← []

    12for (i in text.indices) {13	val ch = text[i]14	if (ch == '(' || ch == '[' || ch == '{') {
    values this step[]stack)ch

  10. balanced ← true, stdout ← True

    27	println(if (balanced) "True" else "False")28}
    values this steptruebalancedTruestdout[]stack

Complexity

  • Time: O(n)
  • Space: O(n) worst case

Implementation notes

  • Kotlin: ArrayDeque<Char> with addLast / removeLast / last() is the smallest honest stack shape; the stdlib already exposes a proper deque so the lesson can stay on the explicit push/pop pattern instead of leaning on a generic MutableList<Char>.
  • The matchOpen helper documents the closing -> opening map without leaking runtime references into the replay.
  • The replay highlights the current character, shows the stack updating each frame, and surfaces the final balanced/unbalanced verdict.