Recursion 003
#recursion #datastructures #devstudy #balancedparenthesis #boolean
The Problem:
Write a method that accepts a string containing open or closed parenthesis and returns true if the string has a balanced set of parenthesis. Use recursion.
Using the 10DIME approach to understanding the problem:
Input: a string of parenthesis
Output: boolean. true if balanced, false if not balanced
Definitions:
– balanced means that the string has the same amount of left brackets as right brackets
– not balanced means that there is an uneven amount of brackets
Instructions:
- make string an array and remove the commas
Planning out Iterative Function instructions:
2. IF ODD: I want to split the string into characters, check if there is an odd total amount of chars, if so, return false
3. IF EVEN: I could:
– iterate through, collect all left brackets, save the count
– collect all right brackets, save the count
– if they are the same, return true
Planning Out Recursion Function Instructions:
- I realized that I didn't need to remove the commas from the input string if my input just didn't have commas to begin with. The original problem did not say there would be commas so I need to think more carefully about the question next time.
1. Base case: there are zero elements left. arr.empty?
2. Function: What is the repetition required to solve this problem?
compare one element to the next and if they do not match, remove both:
arr.each_with_index do
`if arr[0] != arr[1] # remove both
3. Next-To-Last Case: arr[0..c-3]
4. Recursion Function: compare[0..c-3] where compare is a function that compares the first and the second item in an array. If they are not equivalent, both items are deleted.
So this is what I want to repeatedly call:
def compare(array)
if array[0] != array[1]
array.delete_at(0)
array.delete_at(1)
else
(reduce size until base case is met)
end
end
5. What does this look like when the program is running?
Given an array of elements: arr = [x0, x1, x2, x3, x4, x5]
1. The first call will compare x0 != x1, let's say this is true so those elements are removed from array.
So we can say that [x0,x1,x2,x3,x4,x5] == [x2, x3, x4, x5].push(x0,x1) where we call the recursion on [x2, x3, x4, x5] part
[x2, x3, x4, x5] == [x4, x5].push(x2, x3)
[x4, x5] == [].push(x4, x5)
[].empty? is our base case = code finished.
Methods: N/A
Edge Cases:
– if array is empty
– if array only contains one type of bracket
ITERATIVE IMPLEMENTATION:
def is_balanced?(string)
return false if string.empty?
arr = string.chars.delete_if { |s| s == "," }
if arr.count.odd?
false
else
left = []
arr.each do |bracket|
if bracket == "("
left << bracket
arr.delete(bracket)
end
end
left.count == arr.count ? true : false
end
end
p is_balanced?("") == false
p is_balanced?("(") == false
p is_balanced?("(,)") == true
p is_balanced?("(,(,(,),)") == false
p is_balanced?("(,(,(,(,(") == false
p is_balanced?("(,(,(,),),)") == true
recursion implementation: NOT COMPLETED
def is_balanced?(input)
return false if input.empty?
input.class == Array ? input : input = input.chars
count = input.count
return false if count == 1
if count == 2
if input[0] != input[1]
return true
else
false
end
elsif count > 2
return false if input.uniq.size == 1
input.each_cons(2) do | first, second |
if first != second
input.delete_at(0)
input.delete_at(1)
is_balanced?(input)
else
is_balanced?(input.shuffle)
end
end
end
end
p is_balanced?("") == false
p is_balanced?("(") == false
p is_balanced?("()") == true
p is_balanced?("((") == false
p is_balanced?("((())") == false
p is_balanced?("(((((") == false
p is_balanced?("((()))") == true