如何以错误的顺序检查括号的有效性

Question

我必须编写一个方法，该方法接受字符串，如果括号不为空，括号和大括号正确闭合，则返回true。否则返回false。

这是我得到的：

def empty_brackets?(string)
%w[ () [] {} ].none?(&string.method(:include?))
end
def valid_string?(string)
match_count = 0
string.each_char do |c|
match_count += 1 if [ '[', '{', '(' ].include?(c)
match_count -= 1 if [ ']', '}', ')' ].include?(c)
end
match_count == 0
end

我认为我的valid_string?方法不是很稳定，但最重要的是，它没有通过括号顺序错误的测试，比如)somebrackets(。你能告诉我怎么修吗？

Answer 1

我的尝试，推送数组中所有的左括号，如果匹配则弹出右括号：

BRACKET_PAIRS = { '[' => ']', '{' => '}', '(' => ')' }
def valid?(string)
string.each_char.with_object([]) do |char, bracket_stack|
if BRACKET_PAIRS.keys.include? char
bracket_stack << char
elsif BRACKET_PAIRS.values.include? char
if char != BRACKET_PAIRS[bracket_stack.last]
return false
else
bracket_stack.pop
end
end
end.empty?
end

Answer 2

这里有一个非常高效的版本。它使用regex，并将所有的大括号({}[]()(拉出到一个小数组中，然后不断缩小对，直到什么都没有了。当它找到一个不匹配的对时，它就会退出并返回false。它也不会将字符串拆分为char数组，因为这将使用两倍的内存(一次用于整个字符串，另一次用于拆分为单个字符的字符串(。

BRACKET_PAIRS = { '{' => '}', '[' => ']', '(' => ')' }
BRACKET_REGEX = /#{BRACKET_PAIRS.to_a.flatten.map { |v| Regexp.escape(v) }.join('|')}/
def valid?(string)
brackets = string.scan(BRACKET_REGEX)
while brackets.size > 0
first = brackets.shift
last = brackets.pop
return(false) unless BRACKET_PAIRS[first] == last
end
return(true)
end

如果根本没有大括号，则此代码将返回true。

如果你不喜欢，可以这样做：

BRACKET_PAIRS = { '{' => '}', '[' => ']', '(' => ')' }
BRACKET_REGEX = /#{BRACKET_PAIRS.to_a.flatten.map { |v| Regexp.escape(v) }.join('|')}/
def valid?(string)
brackets = string.scan(BRACKET_REGEX)
return(false) unless brackets.size > 0 # this line is added
while brackets.size > 0
first = brackets.shift
last = brackets.pop
return(false) unless BRACKET_PAIRS[first] == last
end
return(true)
end

附带说明一下，您将希望避免像在示例中那样在循环中创建数组

string.each_char do |c|
match_count += 1 if [ '[', '{', '(' ].include?(c)
match_count -= 1 if [ ']', '}', ')' ].include?(c)
end

此代码将在string变量中创建两个数组和每个字符6个字符串。这是非常低效的，您将使用比必要的更多的RAM和CPU。你至少想让这两个数组在循环之外，因为它们不会改变，理想情况下甚至让它们成为一个常量，这样你就不会每次调用方法时都让它们成为常量。当你的程序启动时，让它们成为一个，并永远使用它。像这样的小事实际上会产生很大的不同，尤其是在循环中使用时。

Answer 3

CLOSE_TO_OPEN = { ']'=>'[', '}'=>'{', ')'=>'(' }
def valid?(str)
str.each_char.with_object([]) do |c,stack|
case c
when '[', '{', '('
stack << c
when ']', '}', ')'
return false unless stack.pop == CLOSE_TO_OPEN[c]
end
end.empty?
end
valid? "[a]{b[c{d}e]fg}" #=> true
valid? "[a]{b[c{d]e}fg}" #=> false

通过添加一些puts语句可以看出该方法的行为。

def valid?(str)
str.each_char.with_object([]) do |c,stack|
puts "c=#{c}, stack=#{stack}"
case c
when '[', '{', '('
stack << c
puts "  stack after 'stack << #{c}' = #{stack}"
when ']', '}', ')'
print "  stack.pop (#{stack.last||'nil'})==CLOSE_TO_OPEN[#{c}] " +
"(#{CLOSE_TO_OPEN[c]})=>"
puts stack.last == CLOSE_TO_OPEN[c] ? "true, so continue" :
"false, so return false"
return false unless stack.pop == CLOSE_TO_OPEN[c]
end
end.tap { |stack| puts "At end, '#{stack}.empty?` (#{stack.empty?})" }.empty?
end

valid? "[a]{b[c{d}e]fg}"
c=[, stack=[]
stack after 'stack << [' = ["["]
c=a, stack=["["]
c=], stack=["["]
stack.pop ([)==CLOSE_TO_OPEN[]] ([)=>true, so continue
c={, stack=[]
stack after 'stack << {' = ["{"]
c=b, stack=["{"]
c=[, stack=["{"]
stack after 'stack << [' = ["{", "["]
c=c, stack=["{", "["]
c={, stack=["{", "["]
stack after 'stack << {' = ["{", "[", "{"]
c=d, stack=["{", "[", "{"]
c=}, stack=["{", "[", "{"]
stack.pop ({)==CLOSE_TO_OPEN[}] ({)=>true, so continue
c=e, stack=["{", "["]
c=], stack=["{", "["]
stack.pop ([)==CLOSE_TO_OPEN[]] ([)=>true, so continue
c=f, stack=["{"]
c=g, stack=["{"]
c=}, stack=["{"]
stack.pop ({)==CLOSE_TO_OPEN[}] ({)=>true, so continue
At end, '[].empty?` (true)
#=> true

valid? "[a]{b[c{d]e}fg}"
c=[, stack=[]
stack after 'stack << [' = ["["]
c=a, stack=["["]
c=], stack=["["]
stack.pop ([)==CLOSE_TO_OPEN[]] ([)=>true, so continue
c={, stack=[]
stack after 'stack << {' = ["{"]
c=b, stack=["{"]
c=[, stack=["{"]
stack after 'stack << [' = ["{", "["]
c=c, stack=["{", "["]
c={, stack=["{", "["]
stack after 'stack << {' = ["{", "[", "{"]
c=d, stack=["{", "[", "{"]
c=], stack=["{", "[", "{"]
stack.pop ({)==CLOSE_TO_OPEN[]] ([)=>false, so return false
#=> false