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 a plain `stack <- character(0)` vector as the open-bracket stack; push by `stack[length(stack) + 1] <- ch`, pop by `stack <- stack[-length(stack)]`.
matching map A small `match_open(close)` helper returns the expected opener for each closing bracket — three explicit branches keep the lesson compact.

Basic Implementation

basic.R
Replay: real traced execution (multi-file project)
match_open <- function(close) {
	if (close == ")") {
		return("(")
	} else if (close == "]") {
		return("[")
	} else if (close == "}") {
		return("{")
	}
	return(" ")
}

text <- "({[]})"
stack <- character(0)
balanced <- TRUE
i <- 1
while (balanced && i <= nchar(text)) {
	ch <- substr(text, i, i)
	if (ch == "(" || ch == "[" || ch == "{") {
		stack[length(stack) + 1] <- ch
	} else {
		if (length(stack) == 0 || stack[length(stack)] != match_open(ch)) {
			balanced <- FALSE
		} else {
			stack <- stack[-length(stack)]
		}
	}
	i <- i + 1
}
if (length(stack) != 0) {
	balanced <- FALSE
}
if (balanced) {
	cat("True\n", sep = "")
} else {
	cat("False\n", sep = "")
}

  1. text ← ({[]})

    12text <- "({[]})"13stack <- character(0)
    values this step({[]})text

  2. stack ← []

    12text <- "({[]})"13stack <- character(0)14balanced <- TRUE
    values this step[]stack

  3. balanced ← true

    13stack <- character(0)14balanced <- TRUE15i <- 1
    values this steptruebalanced

  4. stack ← [(]

    16while (balanced && i <= nchar(text)) {17	ch <- substr(text, i, i)18	if (ch == "(" || ch == "[" || ch == "{") {
    values this step[(]stack(ch

  5. stack ← [(, {]

    16while (balanced && i <= nchar(text)) {17	ch <- substr(text, i, i)18	if (ch == "(" || ch == "[" || ch == "{") {
    values this step[(, {]stack{ch

  6. stack ← [(, {, []

    16while (balanced && i <= nchar(text)) {17	ch <- substr(text, i, i)18	if (ch == "(" || ch == "[" || ch == "{") {
    values this step[(, {, []stack[ch

  7. stack ← [(, {]

    16while (balanced && i <= nchar(text)) {17	ch <- substr(text, i, i)18	if (ch == "(" || ch == "[" || ch == "{") {
    values this step[(, {]stack]ch

  8. stack ← [(]

    16while (balanced && i <= nchar(text)) {17	ch <- substr(text, i, i)18	if (ch == "(" || ch == "[" || ch == "{") {
    values this step[(]stack}ch

  9. stack ← []

    16while (balanced && i <= nchar(text)) {17	ch <- substr(text, i, i)18	if (ch == "(" || ch == "[" || ch == "{") {
    values this step[]stack)ch

  10. balanced ← true, stdout ← True

    32if (balanced) {33	cat("True\n", sep = "")34} else {
    values this steptruebalancedTruestdout[]stack

Complexity

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

Implementation notes

  • R: a plain character vector with stack[length(stack) + 1] <- ch for push and stack <- stack[-length(stack)] (negative-index slice removal) for pop is the smallest honest stack shape; reaching for append() / head() would hide the explicit push/pop pattern. A balanced flag plus while (balanced && i <= nchar(text)) keeps the early-exit visible without leaning on a custom break.
  • The match_open helper documents the closing -> opening map without leaking runtime references into the replay.
  • substr(text, i, i) is the canonical single-byte extraction for an ASCII bracket string; the lesson does not exercise multibyte sequences.
  • The replay highlights the current character, shows the stack updating each frame, and surfaces the final balanced/unbalanced verdict.