Valid Parentheses in Ruby: A Comprehensive Guide

Parentheses are fundamental elements in programming and mathematics, used to group and structure expressions. In many coding scenarios, it’s essential to determine if a given string of parentheses is valid. Validity is defined by whether all parentheses are correctly closed in the proper order. In this article, we’ll explore how to create a robust Ruby function to tackle this problem, complete with examples and outputs.

Understanding the Problem

Before we dive into coding, let’s establish a clear understanding of the problem. Valid parentheses require each opening parenthesis to have a corresponding closing parenthesis, and they must be closed in the correct order. For example, the following strings are valid:

• ()
• ()[]{}
• {[()]}

However, these strings are not valid:

• (]
• ([)]
• ([)

Approach and Algorithm

To determine whether a given string of parentheses is valid, we can use a stack data structure. The stack will help us keep track of the opening parentheses as we encounter them and ensure that they are closed in the correct order.

Here’s the algorithm we’ll follow:

1. Initialize an empty stack to store opening parentheses.
2. Iterate through each character in the input string.
3. If the character is an opening parenthesis ((, [, or {), push it onto the stack.
4. If the character is a closing parenthesis (), ], or }):
   • Check if the stack is empty. If it is, the string is invalid because there’s no matching opening parenthesis.
   • Pop the top element from the stack and check if it matches the current closing parenthesis. If they don’t match, the string is invalid.
5. After iterating through the entire string, if the stack is empty, the string is valid. Otherwise, it’s invalid.

Implementing the Ruby Function

Now, let’s implement the algorithm in Ruby:

def is_valid(s)
  stack = []
  parentheses_map = { ')' => '(', ']' => '[', '}' => '{' }

  s.each_char do |char|
    if parentheses_map.values.include?(char)
      stack.push(char)
    elsif parentheses_map.keys.include?(char)
      return false if stack.empty? || stack.pop != parentheses_map[char]
    end
  end

  return stack.empty?
end