Working with Stacks in Ruby: Advanced Applications

Introduction to the Lesson

Welcome back! As we dive further into stack operations using Ruby, think of how these structures serve similar functions in programming as they do in everyday tasks. Consider stacking books: the last book you place on top is the first one you would retrieve. Similarly, a computer's stack temporarily stores data, allowing you to access the most recent item first. Today, we will solve two specific problems using the Last-In, First-Out principle to enhance your understanding of stack operations in Ruby.

Problem 1: Validating Parentheses

Validating nested structures such as parentheses is common in programming, akin to ensuring that a series of opened boxes are properly closed. We will create a function to verify that a string of parentheses is properly nested and closed, effectively checking for balance.

Problem 1: Actualization

Unbalanced parentheses can cause errors in code, much like a misplaced or missing puzzle piece. Our function will act as a diligent organizer, ensuring every opened parenthesis is properly closed.

Problem 1: Naive Approach

A simple approach might involve initializing a counter for each type of bracket (parentheses, braces, and square brackets), incrementing counters for opening brackets, and decrementing for closing ones. Although this method checks for matching opening and closing brackets, it fails to verify the order, which is crucial for balanced brackets. Each closing bracket must correspond to the most recently opened bracket of the same type.

Problem 1: Efficient Approach

A stack is an efficient data structure for solving this problem, adhering to the LIFO principle. It allows us to track the order of opening and closing brackets, ensuring that the most recently opened bracket is closed first.

Problem 1: Algorithm

We create a hash that maps each opening bracket to its corresponding closing bracket and initialize an empty stack (array). We iterate through each character in the string: if it is an opening bracket, we append it to the stack . If it's a closing bracket and matches the top element of the stack, we remove the top element. If it doesn't match, we return false .

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

Ruby

def are_brackets_balanced?(input_str)
  bracket_map = { '(' => ')', '[' => ']', '{' => '}' }
  open_brackets = bracket_map.keys
  stack = []

  input_str.each_char do |char|
    # Push all opening brackets to the stack
    if open_brackets.include?(char)
      stack.push(char)
    # If closing bracket matches the last opened bracket, pop
    elsif !stack.empty? && char == bracket_map[stack.last]
      stack.po
    else
      # Return false if no match found
      return false
    end
  end

  # Return true if stack is empty (all brackets matched)
  stack.empty?
end

puts are_brackets_balanced?("(){}[]")  # Output: true

def are_brackets_balanced?(input_str)
  bracket_map = { '(' => ')', '[' => ']', '{' => '}' }
  open_brackets = bracket_map.keys
  stack = []

  input_str.each_char do |char|
    # Push all opening brackets to the stack
    if open_brackets.include?(char)
      stack.push(char)
    # If closing bracket matches the last opened bracket, pop
    elsif !stack.empty? && char == bracket_map[stack.last]
      stack.po
    else
      # Return false if no match found
      return false
    end
  end

  # Return true if stack is empty (all brackets matched)
  stack.empty?
end

puts are_brackets_balanced?("(){}[]")  # Output: true

Ruby

def reverse_string(str)
  stack = []
  # Push each character to the stack
  str.each_char { |c| stack.push(c) }

  reversed = []
  # Pop characters from stack and add to reversed array
  reversed << stack.pop until stack.empty?

  reversed.join
end

puts reverse_string("hello")  # Output: "olleh"

def reverse_string(str)
  stack = []
  # Push each character to the stack
  str.each_char { |c| stack.push(c) }

  reversed = []
  # Pop characters from stack and add to reversed array
  reversed << stack.pop until stack.empty?

  reversed.join
end

puts reverse_string("hello")  # Output: "olleh"

Ruby

def are_brackets_balanced?(input_str)
  bracket_map = { '(' => ')', '[' => ']', '{' => '}' }
  open_brackets = bracket_map.keys
  stack = []

  input_str.each_char do |char|
    # Push all opening brackets to the stack
    if open_brackets.include?(char)
      stack.push(char)
    # If closing bracket matches the last opened bracket, pop
    elsif !stack.empty? && char == bracket_map[stack.last]
      stack.po
    else
      # Return false if no match found
      return false
    end
  end

  # Return true if stack is empty (all brackets matched)
  stack.empty?
end

puts are_brackets_balanced?("(){}[]")  # Output: true

Ruby

def reverse_string(str)
  stack = []
  # Push each character to the stack
  str.each_char { |c| stack.push(c) }

  reversed = []
  # Pop characters from stack and add to reversed array
  reversed << stack.pop until stack.empty?

  reversed.join
end

puts reverse_string("hello")  # Output: "olleh"

Introduction to the Lesson

Problem 1: Validating Parentheses

Problem 1: Actualization

Problem 1: Naive Approach

Problem 1: Efficient Approach

Problem 1: Algorithm

Join the 1M+ learners on CodeSignal

Problem 1: Solution Building

Problem 2: Reverse a String using a Stack

Problem 2: Actualization

Problem 2: Approach Explanation

Problem 2: Solution Building

Lesson Summary