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.
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.
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.
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.
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.
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
.
First, let's introduce brackets mapping and implement the solution in Ruby:
Ruby1def are_brackets_balanced?(input_str) 2 bracket_map = { '(' => ')', '[' => ']', '{' => '}' } 3 open_brackets = bracket_map.keys 4 stack = [] 5 6 input_str.each_char do |char| 7 # Push all opening brackets to the stack 8 if open_brackets.include?(char) 9 stack.push(char) 10 # If closing bracket matches the last opened bracket, pop 11 elsif !stack.empty? && char == bracket_map[stack.last] 12 stack.po 13 else 14 # Return false if no match found 15 return false 16 end 17 end 18 19 # Return true if stack is empty (all brackets matched) 20 stack.empty? 21end 22 23puts are_brackets_balanced?("(){}[]") # Output: true
The function returns false
in three cases:
- A closing bracket appears when the stack of opening brackets is empty.
- A closing bracket does not match the most recent opening bracket.
- There are unmatched opening brackets left in the stack at the end.
Next, let's explore how to reverse a string using stacks. This may seem straightforward but demonstrates the effective use of data structures in computation.
Imagine building a feature where a user inputs a string, and you output the reversed string. In more complex scenarios, like network applications, stack buffers reverse packet order. Reversing the order of elements using a Stack
is a crucial skill.
Thanks to the stack's LIFO feature, it's excellent for reversing the order of elements. The strategy is straightforward: push all characters to a stack
and then pop them in reverse order, forming a reversed string.
Here's how you can implement the solution in Ruby:
Ruby1def reverse_string(str) 2 stack = [] 3 # Push each character to the stack 4 str.each_char { |c| stack.push(c) } 5 6 reversed = [] 7 # Pop characters from stack and add to reversed array 8 reversed << stack.pop until stack.empty? 9 10 reversed.join 11end 12 13puts reverse_string("hello") # Output: "olleh"
The stack-based approach effectively communicates each operation's intent, building a reversed string efficiently by stacking and unstacking characters.
Today, you've tackled two classic problems using stacks in Ruby, showcasing its practical utility. The stack's LIFO nature allows us to ensure the correctness of nested structures and simplify sequence reversal with direct and efficient code.
Well done on completing this lesson! Your understanding of stack operations in Ruby equips you to tackle real-world scenarios where you need to process data in reverse or verify correctness. Happy coding!
