在Ruby中编写“匹配平衡括号”程序的更好方法

这个方法应该采用一个字符串并检测括号’（””””在字符串中是否与相应的（相对的）括号正确关闭）。

首先，是否有更优雅，更紧凑的方式来编写此位而不使用所有“或”s（||）：

split_array.each do |i| if (i == "{" || i == "(" || i == "[") left.push(i) else (i == "}" || i == ")" || i == "]") right.push(i) end end 

我的第二个问题是，这段代码是否可怕（见下文）？ 似乎我应该能够用更少的行来编写这个，但从逻辑上讲，我还没有提出另一个解决方案（但是。）代码适用于大多数测试，但是对于这个测试它返回false（参见所有的驱动程序测试） bottom）：p valid_string？（“[（text）{}]”）== true

任何批评都将不胜感激！ （另外，如果有更好的部分发布，请告诉我）谢谢！

 def valid_string?(string) opposites = { "[" => "]", "{" => "}", "(" => ")", "]" => "[", "}" => "{", ")" => "(" } left = Array.new right = Array.new return_val = true split_array = string.split(//) split_array.delete_if { |e| e.match(/\s/) } split_array.each do |i| if (i == "{" || i == "(" || i == "[") left.push(i) else (i == "}" || i == ")" || i == "]") right.push(i) end end # p left # p right left.each_index do |i| if left[i] != opposites[right[i]] return_val = false end end return_val end p valid_string?("[ ] } ]") == false p valid_string?("[ ]") == true p valid_string?("[ ") == false p valid_string?("[ ( text ) {} ]") == true p valid_string?("[ ( text { ) } ]") == false p valid_string?("[ (] {}") == false p valid_string?("[ ( ) ") == false 

——- 更新：在尝试了一些不同的方法之后，我的重构是这样的： ———–

 def valid_string?(str) mirrored = { "[" => "]", "{" => "}", "(" => ")" } open_brackets = Array.new split_str_array = str.split("") split_str_array.each do |bracket| if bracket.match(/[\[|\{|\(]/) then open_brackets.push(bracket) elsif bracket.match(/[\]|\}|\)]/) return false if mirrored[open_brackets.pop] != bracket end end open_brackets.empty? end 

Answer 1

我的方法如下：

 def valid_string?(string) open_paren = ['[','{','('] close_paren = [']','}',')'] open_close_hash = {"]"=>"[", "}"=>"{", ")"=>"("} stack = [] regex = Regexp.union(close_paren+open_paren) string.scan(regex).each do |char| if open_paren.include? char stack.push(char) elsif close_paren.include? char pop_val = stack.pop return false if pop_val != open_close_hash[char] end end open_paren.none? { |paren| stack.include? paren } end valid_string?("[ ] } ]") # => false valid_string?("[ ]") # => true valid_string?("[ ") # => false valid_string?("[ (] {}") # => false valid_string?("[ ( ) ") # => false valid_string?("[ ( text { ) } ]") # => false valid_string?("[ ( text ) {} ]") # => true 

算法：

1. 声明一个字符堆栈S
2. 现在遍历表达式字符串exp。
   • 如果当前字符是起始括号（ '('或'{'或'[' ），则将其推入堆栈。
   • 如果当前字符是右括号（ ')'或'}'或']' ），则从堆栈弹出，如果弹出的字符是匹配的起始括号，那么罚款其他括号不平衡。
3. 完成遍历后，如果堆栈中还有一些起始括号则“不平衡”

Answer 2

最短的正则表达式解决方案可能是：

 def valid_string? orig str = orig.dup re = /\([^\[\](){}]*\)|\[[^\[\](){}]*\]|\{[^\[\](){}]*\}/ str[re] = '' while str[re] !str[/[\[\](){}]/] end 

Answer 3

其他方式：

 s = str.gsub(/[^\{\}\[\]\(\)]/, '') while s.gsub!(/\{\}|\[\]|\(\)/, ''); end s.empty? Ex 1 str = "(a ()bb [cc{cb (vv) x} c ]ss) " s = str.gsub(/[^\{\}\[\]\(\)]/, '') #=> "(()[{()}])" while s.gsub!(/\{\}|\[\]|\(\)/, '') do; end s => "([{}])" => "([])" => "()" => "" gsub!() => nil s.empty? #=> true Ex 2 str = "(a ()bb [cc{cb (vv) x] c }ss) " s = str.gsub(/[^\{\}\[\]\(\)]/, '') #=> "(()[{()]})" while s.gsub!(/\{\}|\[\]|\(\)/, '') do; end s => "([{]})" gsub!() => nil s.empty? #=> false 

Answer 4

这应该提供相同的function

 def valid_string?(string) #assume validity @valid = true #empty array will be populated inside the loop @open_characters = [] #set up a hash to translate the open character to a closing character translate_open_closed = {"{" => "}","["=>"]","("=>")"} #create an array from the string loop through each item string.split('').each do |e| #adding it to the open_characters array if it is an opening character @open_characters << e if e=~ /[\[\{\(]/ #if it is a closing character then translate the last open_character to #a closing character and compare them to make sure characters are closed in order #the result of this comparison is applied to the valid variable @valid &= e == translate_open_closed[@open_characters.pop] if e=~ /[\]\}\)]/ end #return validity and make sure all open characters have been matched @valid &= @open_characters.empty? end 

您也可以使用注入执行此操作，但它会更不透明。

Answer 5

作为模拟面试编码挑战的一部分，我得到了这个。 就我而言，还有一个在{ "(" => ")", "[" => "]" }传递的parens地图，这意味着括号的类型可能会有所不同。

 def balanced_parens(string, parens_map) # where we throw opening parens opening_parens = [] i = 0 while i < string.length # if current index is opening paren add to array if parens_map.keys.include? string[i] opening_parens << string[i] # if current index is closing paren, remove last item from opening_array elsif parens_map.values.include? string[i] popped_paren = opening_parens.pop # checking that closing parens at current index is a match for last open parens in opening_array return false if string[i] != parens_map[popped_paren] end i += 1 end # if opening_parens array is empty, all parens have been matched (&& value = true) opening_parens.empty? end 

Answer 6

怎么样：

 class Brackets def self.paired?(s) stack = [] brackets = { '{' => '}', '[' => ']', '(' => ')' } s.each_char do |char| if brackets.key?(char) stack.push(char) elsif brackets.values.include?(char) return false if brackets.key(char) != stack.pop end end stack.empty? end end Brackets.paired?("[ ] } ]") # => false Brackets.paired?("[ ]") # => true Brackets.paired?("[ ") # => false Brackets.paired?("[ (] {}") # => false Brackets.paired?("[ ( ) ") # => false Brackets.paired?("[ ( text { ) } ]") # => false Brackets.paired?("[ ( text ) {} ]") # => true