写“匹配平衡括号"的更好方法Ruby 中的程序 [英] Better way to write "matching balanced parenthesis" program in 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.

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

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

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 

解决方案

My approach is as below :

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. Declare a character stack S.
2. 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.
3. After complete traversal, if there is some starting bracket left in stack then "not balanced"

这篇关于写“匹配平衡括号"的更好方法Ruby 中的程序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！