Last active
April 24, 2016 05:28
-
-
Save lrechert/9d5bc4c00bb7ef35379451bb43d3822a to your computer and use it in GitHub Desktop.
Ruby Weekly Challenge - Valid Braces
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
def valid_braces(braces) | |
BracesValidator.new(braces).valid_braces? | |
rescue | |
return false | |
end | |
# most succinct | |
def validBraces(braces) | |
while braces.gsub!(/\(\)|\{\}|\[\]/, '') do ; end | |
braces.empty? | |
end | |
class BracesValidator | |
attr_reader :braces_array | |
def initialize(braces_string) | |
fail ArgumentError unless valid_braces_string?(braces_string) | |
@braces_array = braces_string.split("") | |
end | |
def valid_braces? | |
balanced?(braces_array, []) | |
end | |
private | |
def valid_braces_string?(braces_string) | |
braces_string && !braces_string.empty? && braces_string.length % 2 == 0 | |
end | |
def balanced?(braces_array, stack) | |
return stack.empty? if braces_array.empty? | |
b = braces_array.shift | |
if(open?(b)) | |
return balanced?(braces_array, stack.push(b)) | |
elsif(closed?(b)) | |
return !stack.empty? && matching?(stack.pop, b) && balanced?(braces_array, stack) | |
end | |
end | |
def matching?(o, c) | |
lookup[o] == c | |
end | |
def open?(o) | |
lookup.keys.include? o | |
end | |
def closed?(c) | |
!open?(c) | |
end | |
def lookup | |
@lookup ||= { | |
"(" => ")", | |
"{" => "}", | |
"[" => "]" | |
} | |
end | |
end |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
require_relative '../valid_braces' | |
describe "#valid_braces" do | |
context "when valid" do | |
it "returns true" do | |
expect(valid_braces("(){}[]")).to be_truthy | |
end | |
it "return true" do | |
expect(valid_braces("([{}])")).to be_truthy | |
end | |
it "return true" do | |
expect(valid_braces("()")).to be_truthy | |
end | |
it "returns true" do | |
expect(valid_braces("(({{[[]]}}))")).to be_truthy | |
end | |
it "returns true" do | |
expect(valid_braces("({})[({})]")).to be_truthy | |
end | |
end | |
context "when invalid" do | |
it "returns false" do | |
expect(valid_braces(nil)).to be_falsey | |
end | |
it "returns false" do | |
expect(valid_braces("")).to be_falsey | |
end | |
it "returns false" do | |
expect(valid_braces("(")).to be_falsey | |
end | |
it "returns false" do | |
expect(valid_braces("(}")).to be_falsey | |
end | |
it "returns false" do | |
expect(valid_braces("[(])")).to be_falsey | |
end | |
it "returns false" do | |
expect(valid_braces("][")).to be_falsey | |
end | |
it "returns false" do | |
expect(valid_braces("({[)}]")).to be_falsey | |
end | |
end | |
end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment