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

本文介绍了写“匹配平衡括号”的更好方法Ruby中的程序的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

这个方法应该接受一个字符串并检测括号'（''''''''在字符串中是否正确关闭相应的（相反）括号。

This method is supposed to take a string and detect if the brackets '(' '{' '[' in the string are closing properly with the corresponding (opposite) brackets.

首先，是否有一种更优雅，更紧凑的方式来写这个位而不使用所有的或s（||）：

First, is there a more elegant, compact way to write this bit without using all the "or"s (||):

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

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

My second question is, is this code terrible (see below)? It seems I should be able to write this in way fewer lines, but logically, I haven't come up with another solution (yet.) The code works for most tests, but it returns false for this test (see all driver tests at bottom): p valid_string?("[ ( text ) {} ]") == true

任何批评都是gr非常感谢！ （另外，如果有更好的部分发布，请告诉我）谢谢！

Any critique would be greatly appreciated! (also, if there is a better section to post this, please let me know) Thanks!

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

------- 更新：在尝试了一些不同的方法后，我的重构就是： -----------

-------Updated: After trying some different approaches, my refactor is this:-----------

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

推荐答案

我的方法如下：

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

算法：

声明一个字符堆 S 。

现在遍历表达式字符串exp。

• 如果当前字符是起始括号（'（'或'{'或'['）然后将其推送到堆栈。
• 如果当前字符是结束括号（ '）'或'}'或']' ）然后从堆栈弹出，如果弹出的字符是匹配的起始括号，那么罚款其他括号不平衡。
• Declare a character stack S.
• Now traverse the expression string exp.
  • If the current character is a starting bracket (‘(‘ or ‘{‘ or ‘[') then push it to stack.
  • If the current character is a closing bracket (')' or '}' or ']') then pop from stack and if the popped character is the matching starting bracket then fine else parenthesis are not balanced.