Πώς να ελέγξετε την εγκυρότητα των παρενθέσεων σε λάθος σειρά

ψήφοι
0

Έχω να γράψω μια μέθοδο που δέχεται μια σειρά και επιστρέφει true αν οι παρενθέσεις δεν είναι άδειο, παρενθέσεις και αγκύλες κοντά σωστά Επιστρέφει false διαφορετικά.

Εδώ είναι αυτό που έχω:

  def empty_brackets?(string)
    %w[ () [] {} ].none?(&string.method(:include?))
  end

  def valid_string?(string)
    match_count = 0

    string.each_char do |c|
      match_count += 1 if [ '[', '{', '(' ].include?(c)
      match_count -= 1 if [ ']', '}', ')' ].include?(c)
    end
    match_count == 0
  end

Νομίζω ότι μου valid_string?μέθοδος δεν είναι αρκετά σταθερή, αλλά το πιο σημαντικό δεν περάσει το τεστ, όπου παρενθέσεις είναι σε λάθος σειρά, όπως )somebrackets(. Θα μπορούσατε σας παρακαλώ να συμβουλεύσει πώς μπορεί να διορθωθεί;

Δημοσιεύθηκε 08/11/2018 στις 00:09
πηγή χρήστη
Σε άλλες γλώσσες...                            


3 απαντήσεις

ψήφοι
3

Η προσπάθειά μου, ωθώντας όλους τους ανοίγοντας παρένθεση σε μια σειρά, σκάει το κλείσιμο αυτοί αν ταιριάζουν:

BRACKET_PAIRS = { '[' => ']', '{' => '}', '(' => ')' }

def valid?(string)
  string.each_char.with_object([]) do |char, bracket_stack|
    if BRACKET_PAIRS.keys.include? char
      bracket_stack << char
    elsif BRACKET_PAIRS.values.include? char
      if char != BRACKET_PAIRS[bracket_stack.last]
        return false
      else
        bracket_stack.pop
      end
    end
  end.empty?
end
Απαντήθηκε 08/11/2018 στις 00:23
πηγή χρήστη

ψήφοι
1
CLOSE_TO_OPEN = { ']'=>'[', '}'=>'{', ')'=>'(' }

def valid?(str)
  str.each_char.with_object([]) do |c,stack|
    case c
    when '[', '{', '('
      stack << c
    when ']', '}', ')'
      return false unless stack.pop == CLOSE_TO_OPEN[c]
    end
  end.empty?
end

valid? "[a]{b[c{d}e]fg}" #=> true
valid? "[a]{b[c{d]e}fg}" #=> false

Η συμπεριφορά της μεθόδου μπορεί να δει με την προσθήκη ορισμένων putsκαταστάσεων.

def valid?(str)
  str.each_char.with_object([]) do |c,stack|
    puts "c=#{c}, stack=#{stack}"
    case c
    when '[', '{', '('
      stack << c
      puts "  stack after 'stack << #{c}' = #{stack}"
    when ']', '}', ')'
      print "  stack.pop (#{stack.last||'nil'})==CLOSE_TO_OPEN[#{c}] " +
            "(#{CLOSE_TO_OPEN[c]})=>"
      puts stack.last == CLOSE_TO_OPEN[c] ? "true, so continue" :
        "false, so return false"
      return false unless stack.pop == CLOSE_TO_OPEN[c]
    end
  end.tap { |stack| puts "At end, '#{stack}.empty?` (#{stack.empty?})" }.empty?
end

valid? "[a]{b[c{d}e]fg}"
c=[, stack=[]
  stack after 'stack << [' = ["["]
c=a, stack=["["]
c=], stack=["["]
  stack.pop ([)==CLOSE_TO_OPEN[]] ([)=>true, so continue
c={, stack=[]
  stack after 'stack << {' = ["{"]
c=b, stack=["{"]
c=[, stack=["{"]
  stack after 'stack << [' = ["{", "["]
c=c, stack=["{", "["]
c={, stack=["{", "["]
  stack after 'stack << {' = ["{", "[", "{"]
c=d, stack=["{", "[", "{"]
c=}, stack=["{", "[", "{"]
  stack.pop ({)==CLOSE_TO_OPEN[}] ({)=>true, so continue
c=e, stack=["{", "["]
c=], stack=["{", "["]
  stack.pop ([)==CLOSE_TO_OPEN[]] ([)=>true, so continue
c=f, stack=["{"]
c=g, stack=["{"]
c=}, stack=["{"]
  stack.pop ({)==CLOSE_TO_OPEN[}] ({)=>true, so continue
At end, '[].empty?` (true)
  #=> true

valid? "[a]{b[c{d]e}fg}"
c=[, stack=[]
  stack after 'stack << [' = ["["]
c=a, stack=["["]
c=], stack=["["]
  stack.pop ([)==CLOSE_TO_OPEN[]] ([)=>true, so continue
c={, stack=[]
  stack after 'stack << {' = ["{"]
c=b, stack=["{"]
c=[, stack=["{"]
  stack after 'stack << [' = ["{", "["]
c=c, stack=["{", "["]
c={, stack=["{", "["]
  stack after 'stack << {' = ["{", "[", "{"]
c=d, stack=["{", "[", "{"]
c=], stack=["{", "[", "{"]
  stack.pop ({)==CLOSE_TO_OPEN[]] ([)=>false, so return false
  #=> false
Απαντήθηκε 08/11/2018 στις 04:16
πηγή χρήστη

ψήφοι
1

Εδώ είναι μια πολύ αποτελεσματική έκδοση. Χρησιμοποιεί regex και βγάζει όλα τα σιδεράκια σας ( {}[]()) σε ένα μικρό πίνακα, και στη συνέχεια να κρατά widdling κάτω από τα ζεύγη σας μέχρι εκεί μείνει τίποτα. Η δεύτερη βρίσκει μια απαράμιλλη ζευγάρι, κλείνει και επιστρέφει false. Επίσης, δεν χωρίσει την string σε μία συστοιχία char, όπως ότι θα χρησιμοποιήσει το διπλάσιο της μνήμης (μία φορά για το σύνολο της συμβολοσειράς, και για άλλη μια φορά για τη διάσπαση string σε μεμονωμένους χαρακτήρες).

BRACKET_PAIRS = { '{' => '}', '[' => ']', '(' => ')' }
BRACKET_REGEX = /#{BRACKET_PAIRS.to_a.flatten.map { |v| Regexp.escape(v) }.join('|')}/

def valid?(string)
  brackets = string.scan(BRACKET_REGEX)
  while brackets.size > 0
    first = brackets.shift
    last = brackets.pop
    return(false) unless BRACKET_PAIRS[first] == last
  end

  return(true)
end

Αυτός ο κωδικός θα επιστρέψει true αν δεν υπάρχουν στηρίγματα σε όλα.

Αν δεν σας αρέσει αυτό, να το κάνετε αυτό:

BRACKET_PAIRS = { '{' => '}', '[' => ']', '(' => ')' }
BRACKET_REGEX = /#{BRACKET_PAIRS.to_a.flatten.map { |v| Regexp.escape(v) }.join('|')}/

def valid?(string)
  brackets = string.scan(BRACKET_REGEX)
  return(false) unless brackets.size > 0 # this line is added

  while brackets.size > 0
    first = brackets.shift
    last = brackets.pop
    return(false) unless BRACKET_PAIRS[first] == last
  end

  return(true)
end

Σαν δευτερεύουσα σημείωση, θα θελήσετε να αποφύγει συστοιχίες σε βρόχους όπως κάνατε στο παράδειγμά σας:

string.each_char do |c|
  match_count += 1 if [ '[', '{', '(' ].include?(c)
  match_count -= 1 if [ ']', '}', ')' ].include?(c)
end

Αυτός ο κωδικός θα δημιουργήσει δύο συστοιχίες και 6 χορδές ανά χαρακτήρα σου στην stringμεταβλητή. Αυτό είναι πολύ αναποτελεσματική και θα χρησιμοποιούν πολύ περισσότερη μνήμη RAM και CPU ό, τι χρειάζεται. Θέλετε να τουλάχιστον να κάνει αυτές τις δύο συστοιχίες έξω από το βρόχο, δεδομένου ότι δεν αλλάζουν, και ιδανικά ακόμη και να τους μια σταθερή, έτσι ώστε να μην χρειάζεται καν να τους κάθε φορά που καλείτε τη μέθοδο. Κάντε τους ένα κατά την εκκίνηση του προγράμματος σας και να το χρησιμοποιήσετε για πάντα. Τα μικρά πράγματα όπως αυτό κάνει πραγματικά μια πολύ μεγάλη διαφορά, ειδικά όταν χρησιμοποιούνται σε ένα βρόχο.

Απαντήθηκε 08/11/2018 στις 01:33
πηγή χρήστη

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more