Ruby: How to find if a parenthesis / curly / brace string is correct?
I just got this array of strings:
expressions = [ ")(){}", "[]({})", "([])", "{()[]}", "([)]" ]
I have to write a function that prints 0 for every invalid line and prints 1 for every valid line. So the output of this function, given expressions
as an argument, is0 1, 1, 1, 0
How should I do it?
def check_braces(expressions)
# ??
end
== UPDATE ==
From Peter's tip, I came up with an answer:
expressions = [ ")(){}", "[]({})", "([])", "{()[]}", "([)]" ]
# expressions = [ "[]({})" ]
def check_braces(expressions)
matchers = {
"{" => "}",
"[" => "]",
"(" => ")"
}
expressions.each do |expression|
elements = []
expression.chars.each do |char|
elements << char if elements.empty?
last_element = elements[-1]
if char == matchers[last_element]
elements.pop
end
end
puts (elements.empty? ? 1 : 0)
end
end
check_braces(expressions)
#0
#1
#1
#1
#0
source to share
Here's the basic idea and I'll leave the implementation to you. For each of these lines
- scroll through its symbols;
- when you see
{[(
, push it onto the stack (Ruby array can act like a stack); - when you see
}])
, look at the last character in the array and see if it is a match (for example, the last item in the array[
and you have]
that match). If this is a match, enter the last element in the array; anytime you see one inconsistency, the line is bad and you can stop the loop.
source to share
One potential problem with your code is that it won't catch something like this "[]({)"
.
If you add an elsif check to see if the current char is already in the array of elements and dug it out, if it isn't, this should solve it:
if char == matchers[last_element]
elements.pop
elsif !elements.include? char
elements << char
end
source to share
Go for a case where it doesn't work {([)]}
, which I attached to the end of the expressions array.
Here is my solution and I have shortened it a bit.
expressions = [ ")(){}", "[]({})", "([])", "{()[]}", "([)]", "{([)]}" ]
def check_braces(exps)
m = { "{" => "}", "[" => "]", "(" => ")" }
exps.each do |ex|
el = []
ex.chars.each do |char|
char == m[el[-1]] ? el.pop : el.push(char)
end
puts (el.empty? ? 1 : 0)
end
end
check_braces(expressions)
source to share