ruby - 在 Ruby 中编写 "matching balanced parenthesis"程序的更好方法

Question

这个方法应该接受一个字符串并检测字符串中的方括号 '(' '{' '[' 是否正确地关闭了相应的(相反的)方括号。

首先，是否有一种更优雅、更紧凑的方式来编写这个位而不使用所有的“或”(||):

            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

任何批评将不胜感激!(另外，如果有更好的部分发布这个，请告诉我)谢谢!

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

Algorithm :

1. 声明一个字符栈S。
2. 现在遍历表达式字符串exp。
   • 如果当前字符是起始括号('(' or '{' or '[') 然后压入栈.
   • 如果当前字符是右括号 (')' 或 '}' 或 ']') 然后从堆栈中弹出并如果弹出的字符是匹配的起始括号，则很好，否则括号不平衡。
3. 遍历完成后，如果还剩下起始括号然后堆栈“不平衡”