Solving the common Well-Formed-Strings technical challenge using stacks in Ruby

Jonathan Patterson — Mon, 20 Apr 2020 00:38:44 +0000

Like it or not, technical challenges are a common part of today's interview process for developers.

One of the most common technical challenges you might encounter is sometimes referred to as 'Well Formed Strings'. It challenges you to take a string of assorted brackets "({(([]))})" and validate whether or not the opening brackets are closed in the same order they were opened.

For example:

Well-Formed Strings

A string of characters like "({12}[34(56){67}])" is said to be well-formed
if every opening bracket (square, curly, or parentheses) has a matching
close AND the closing bracket comes in the opposite order of the opening.*

* Valid: "({12}[34(56){67}])"
* Invalid "({12)"
* Invalid "({12)}"

Write a validator that can determine the well-formed-ness of an input string.

Stacks

This challenge can be solved using a Stack.
Stacks are Last In First Out (LIFO) data structures that follow simple rules. Elements in a stack are added or removed from the top of the stack.

You can think of a stack like an empty pringles can.
You start by adding pringles one at a time to the can. When you decide to start removing them, you begin with the pringle at the top. eg: The last pringle you added.
You keep removing them in order until finally you remove the last pringle, which was the first one you added.

In our solution we are going to use an Array to signify the stack.

Pseudocode

Start by creating a Hash with Key/Value pairs. Each Key will represent an opening bracket. Each Value will represent the corresponding closing bracket. We will use this to evaluate the characters in the input string.
Next iterate over the input string's characters.
- If the Character is an opening bracket (represented by a Key in the valid_pairs hash) then we will push that Character into our Stack.
- If the Character matches the last character pushed into the stack, then remove the last character in the stack.
- If neither of these are true, but the Character is a closing bracket, then the string is not 'well-formed' and our validation fails.
By the end of this process, we should have a Stack that is empty. Since all the matching pairs will have been removed from the stack. If the Stack is Not empty, then we haven't matched all pairs and the string is not 'well-formed'.

Solution

def validate(input_string)
  # Establish valid key/value pairs #
  valid_pairs = { '(' => ')',
                  '{' => '}',
                  '[' => ']' 
                }
  # Establish the array which will be our stack #
  stack = []

  # Iterate over each character in the input_string argument #
  input_string.chars.each do |character|

    # If the character is an opening bracket, #
    ## represented as one of the 'keys' in the valid_pairs hash ##
    if valid_pairs.has_key?(character)
      ### Then push that character onto the end of the stack ###
      stack.push(character)

    # If the last character on the stack is a key in the valid_pairs hash, # 
    ## whose matching value is == to the current character ##
    elsif valid_pairs[stack.last] == character
      ### Then remove the last character from the stack, ###
      #### since the current character forms a perfect match to the last character ####
      stack.pop

    # If neither of the above conditions are true, #
    ## yet the character is a value in our valid_pairs hash, ##
    ### then the character is a closing bracket, ###
    #### that doesn't match an open bracket in our stack ####
    elsif valid_pairs.has_value?(character)
      ##### Meaning our string isn't matching and fails #####
      return false
    end
  end

  # The string is well formed if the stack is left with no characters, # 
  ## since we removed all matched characters, ##
  ### if the stack array isn't empty it means unmatched characters are left ###
  return stack.count.zero?
end

Solution without comments

def validate(input_string)
  valid_pairs = { '(' => ')',
                  '{' => '}',
                  '[' => ']' 
                }
  stack = []

  input_string.chars.each do |character|
    if valid_pairs.has_key?(character)
      stack.push(character)
    elsif valid_pairs[stack.last] == character
      stack.pop
    elsif valid_pairs.has_value?(character)
      return false
    end
  end

  return stack.count.zero?
end

By using this method of Key/Value pairs and a First-In-Last-Out Stack that tracks your matches, you could expand the valid_pairs hash to handle all kinds of match validations.

DEV Community: Jonathan Patterson

Solving the common Well-Formed-Strings technical challenge using stacks in Ruby

Stacks

Pseudocode

Solution

Solution without comments