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.

Basic Implementation

basic.R

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 = "")
}

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.

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.