Checking that brackets match (an application of stacks)

This lesson covers checking bracket matching with a stack in R, with the aim of seeing a practical application of the data structure.

With a stack (last in, first out) you push each opening bracket such as ( or [, and each time a closing bracket arrives you check it against the top of the stack.

The sample code holds the opening bracket for each closing bracket in the named list pairs, pushes with vector operations using c() when an opening bracket arrives, and checks against the top of the stack when a closing one does. If the stack is empty at the end, the brackets balance.

A common early stumble is handling several kinds of bracket at once (round, square, and curly mixed together). Counting openings and closings is not enough — you have to check they nest in the right order.

Similar thinking sits behind editor auto-completion and syntax checking. It is an idea with broad application.

📖 Reference code

is_balanced <- function(str) {
  stack <- c()
  pairs <- list(")" = "(", "]" = "[", "}" = "{")
  chars <- strsplit(str, "")[[1]]
  for (ch in chars) {
    if (ch %in% c("(", "[", "{")) {
      stack <- c(stack, ch)
    } else if (ch %in% c(")", "]", "}")) {
      if (length(stack) == 0 || stack[length(stack)] != pairs[[ch]]) {
        return(FALSE)
      }
      stack <- stack[-length(stack)]
    }
  }
  length(stack) == 0
}

cat(is_balanced("(a[b]{c})"), "\n")
cat(is_balanced("(a[b)]"), "\n")

✍️ Your code

Type your code, then press "Run"

🧪 This site can't compile or run R directly, so it checks on the spot whether what you typed matches the reference code (scoring happens entirely in your browser — nothing is sent anywhere).