用Ruby编写，测试匹配的括号、大括号和大括号

Question

问题是编写一个函数，该函数接受一个大括号字符串，并确定大括号的顺序是否有效。如果字符串有效，则返回true；如果字符串无效，则返回false。

所有输入字符串都将是非空的，并且仅由括号、大括号和大括号组成：(([]｛｝。

测试应该给出以下内容：

"(){}[]"   =>  True
"([{}])"   =>  True
"(}"       =>  False
"[(])"     =>  False
"[({})](]" =>  False

我写的代码是：

def validBraces(braces)
revBraces = braces.reverse
arr = []

i = -1
loop do
i += 1
if braces[i] == "(" && revBraces[i] == ")"
arr << 1
else 
arr << 0
end
if braces[i] == ")" && revBraces[i] == "("
arr << 1
else 
arr << 0
end
if braces[i] == "{" && revBraces[i] == "}"
arr << 1
else 
arr << 0
end
if braces[i] == "}" && revBraces[i] == "{"
arr << 1
else 
arr << 0
end
if braces[i] == "[" && revBraces[i] == "]"
arr << 1
else 
arr << 0
end
if braces[i] == "]" && revBraces[i] == "["
arr << 1
else 
arr << 0
end
break if i <= braces.length 
end
if arr.include? 0
puts false
else 
puts true
end
end

我不知道我哪里出了问题，为什么它不起作用。

Answer 1

我会使用堆栈来解决这个问题。将找到的大括号添加到堆栈中，对于大括号，将其与堆栈顶部的大括号进行比较。

def validBraces(braces)
matches = { '(' => ')', '{' => '}', '[' => ']' }
stack = []
braces.chars.each do |char|
case char
when *matches.keys
stack.push(char)
when *matches.values
return false if matches[stack.pop] != char
else
raise ArgumentError, "Unexpected char `#{char}`"
end
end
stack.empty?
end
validBraces("(){}[]")   #=> true       
validBraces("([{}])")   #=> true       
validBraces("(}")       #=> false   
validBraces("[(])")     #=> false        
validBraces("[({})](]") #=> false            
validBraces("[A]")      #=> Unexpected char `A` (ArgumentError)

或以下OOP:

class Balancer
MATCHES = { '(' => ')', '{' => '}', '[' => ']' }
OPENING = MATCHES.keys
CLOSING = MATCHES.values
def initialize(string)
@chars = string.chars
end
def valid?
stack = []
chars.each do |char|
case char
when *OPENING
stack.push(char)
when *CLOSING
return false if MATCHES[stack.pop] != char
else
raise ArgumentError, "Unexpected char `#{char}`"
end
end
stack.empty?
end
private
attr_reader :chars
end
Balancer.new("(){}[]").valid?    #=> true       
Balancer.new("([{}])").valid?    #=> true       
Balancer.new("(}").valid?        #=> false   
Balancer.new("[(])").valid?      #=> false        
Balancer.new("[({})](]").valid?  #=> false            
Balancer.new("[A]").valid?       #=> Unexpected char `A` (ArgumentError)

Answer 2

逻辑错误。你带背带和反向背带。你不会想到大括号嵌套的情况。但是，即使没有嵌套，通过字符串的方式也是不对的。最好有一本"；("，"{"，"["，"("，"}"，"]"；并计算它们的频率(使最后括号的计数为负数(，看看它们是否通过构建一个和来抵消自己——应该是0。

def freqs(l)
h = Hash.new(0)
l.each do |e|
h[e] += 1
end
return h
end
def balanced(braces)
fr = freqs(braces.split(""))
return fr["("] - fr[")"] == 0 && fr["{"] - fr["}"] == 0 && fr["["] - fr["]"] == 0 
end

Answer 3

一种方法是依次删除字符串'()'、'[]'和'{}'，直到该字符串为空，在这种情况下，该字符串被发现为平衡，或者在某些迭代中，没有找到字符串'()'、'[]'或'{}'，在这种情况下，该串被发现为不平衡

RGX = /()|[]|{}/

def valid_braces(str)
s = str.dup
until s.empty?
return false if s.gsub!(RGX, '').nil?
end
true
end

valid_braces '(){}[]'          #=> true
valid_braces '([{}])'          #=> true
valid_braces '([[{[]}]{}]())'  #=> true
valid_braces '(}'              #=> false
valid_braces '[(])'            #=> false
valid_braces '[({})](]'        #=> false
valid_braces('[A]')            #=> false

---

正则表达式读取；匹配"(("或"[]"或"｛｝"；。注意字符串#gsub！如果没有执行替换，则返回nil。

---

我可以插入一个puts语句来说明每次迭代中发生的情况。

def valid_braces(str)
s = str.dup
until s.empty?
puts s
return false if s.gsub!(RGX, '').nil?
end
true
end

valid_braces '([[{[]}]{}]())'
([[{[]}]{}]())  full string
([[{}]])        '[]', '{}' and '()' removed
([[]])          '{}' removed
([])            '[]' removed
()              '[]' removed
'()' removed 
#=> true      as `str` is empty

---

这可能不如@spickermann所做的那样使用堆栈有效。我会以不同的方式来实现这一点。

CLOSE_TO_OPEN = { ')'=>'(', ']'=>'[', '}'=>'{' }
OPENS = CLOSE_TO_OPEN.values
#=> ["(", "[", "{"]

def valid_braces(str)
stack = []  
str.each_char do |c|
if OPENS.include?(c)
stack << c
else
return false unless CLOSE_TO_OPEN[c] == stack.pop
end
end
return stack.empty?
end

valid_braces '(){}[]'          #=> true
valid_braces '([{}])'          #=> true
valid_braces '([[{[]}]{}]())'  #=> true
valid_braces '(}'              #=> false
valid_braces '[(])'            #=> false
valid_braces '[({})](]'        #=> false
valid_braces('[A]')            #=> false

---

我们可以添加puts语句来查看发生了什么。

def valid_braces(str)
stack = []  
str.each_char do |c|
print "stack = #{stack}, c = '#{c}', "
if OPENS.include?(c)
stack << c
puts "pushed '#{c}'"
else
return false unless CLOSE_TO_OPEN[c] == stack.pop
puts "popped '#{CLOSE_TO_OPEN[c]}'"
end
end
puts "stack at end = #{stack}"
return stack.empty?
end

valid_braces '([[{[]}]{}]())'
stack = [], c = '(', pushed '('
stack = ["("], c = '[', pushed '['
stack = ["(", "["], c = '[', pushed '['
stack = ["(", "[", "["], c = '{', pushed '{'
stack = ["(", "[", "[", "{"], c = '[', pushed '['
stack = ["(", "[", "[", "{", "["], c = ']', popped '['
stack = ["(", "[", "[", "{"], c = '}', popped '{'
stack = ["(", "[", "["], c = ']', popped '['
stack = ["(", "["], c = '{', pushed '{'
stack = ["(", "[", "{"], c = '}', popped '{'
stack = ["(", "["], c = ']', popped '['
stack = ["("], c = '(', pushed '('
stack = ["(", "("], c = ')', popped '('
stack = ["("], c = ')', popped '('
stack at end = []
#=> true