写“匹配平衡括号"的更好方法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.

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 :

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.

After complete traversal, if there is some starting bracket left in stack then "not balanced"