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 `ArrayBuffer[Char]` as the open-bracket stack; push by `stack += ch`, pop by `stack.remove(stack.length - 1)`.
matching map A small `matchOpen(close)` helper returns the expected opener for each closing bracket — three explicit `match` arms keep the lesson compact.

Basic Implementation

basic.scala
Replay: real traced execution (multi-file project)
import scala.collection.mutable.ArrayBuffer

object Main {
	def matchOpen(close: Char): Char = close match {
		case ')' => '('
		case ']' => '['
		case '}' => '{'
		case _   => ' '
	}

	def main(args: Array[String]): Unit = {
		val text = "({[]})"
		val stack = ArrayBuffer.empty[Char]
		var balanced = true
		var i = 0
		while (balanced && i < text.length) {
			val ch = text(i)
			if (ch == '(' || ch == '[' || ch == '{') {
				stack += ch
			} else {
				if (stack.isEmpty || stack.last != matchOpen(ch)) {
					balanced = false
				} else {
					stack.remove(stack.length - 1)
				}
			}
			i = i + 1
		}
		if (stack.nonEmpty) {
			balanced = false
		}
		println(if (balanced) "True" else "False")
	}
}

  1. text ← ({[]})

    11def main(args: Array[String]): Unit = {12	val text = "({[]})"13	val stack = ArrayBuffer.empty[Char]
    values this step({[]})text

  2. stack ← []

    12val text = "({[]})"13val stack = ArrayBuffer.empty[Char]14var balanced = true
    values this step[]stack

  3. balanced ← true

    13val stack = ArrayBuffer.empty[Char]14var balanced = true15var i = 0
    values this steptruebalanced

  4. stack ← [(]

    16while (balanced && i < text.length) {17	val ch = text(i)18	if (ch == '(' || ch == '[' || ch == '{') {
    values this step[(]stack(ch

  5. stack ← [(, {]

    16while (balanced && i < text.length) {17	val ch = text(i)18	if (ch == '(' || ch == '[' || ch == '{') {
    values this step[(, {]stack{ch

  6. stack ← [(, {, []

    16while (balanced && i < text.length) {17	val ch = text(i)18	if (ch == '(' || ch == '[' || ch == '{') {
    values this step[(, {, []stack[ch

  7. stack ← [(, {]

    16while (balanced && i < text.length) {17	val ch = text(i)18	if (ch == '(' || ch == '[' || ch == '{') {
    values this step[(, {]stack]ch

  8. stack ← [(]

    16while (balanced && i < text.length) {17	val ch = text(i)18	if (ch == '(' || ch == '[' || ch == '{') {
    values this step[(]stack}ch

  9. stack ← []

    16while (balanced && i < text.length) {17	val ch = text(i)18	if (ch == '(' || ch == '[' || ch == '{') {
    values this step[]stack)ch

  10. balanced ← true, stdout ← True

    32		println(if (balanced) "True" else "False")33	}34}
    values this steptruebalancedTruestdout[]stack

Complexity

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

Implementation notes

  • Scala: ArrayBuffer[Char] with += / remove(length - 1) / last is the smallest honest stack shape; reaching for scala.collection.mutable.Stack would hide the explicit push/pop pattern. A var balanced plus a while (balanced && i < text.length) loop keeps the early-exit visible without leaning on scala.util.boundary.
  • 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.