Dev Faq
7
votes

Vérification si une chaîne a des parenthèses équilibrées

Je travaille actuellement sur un quiz de problème de rubis, mais je ne sais pas si ma solution a raison. Après avoir exécuté le chèque, cela montre que la compilation a réussi, mais je suis juste inquiet, ce n'est pas la bonne réponse.

Le problème: p>

Une chaîne s constituée uniquement de caractères '(' et ')' est appelée correctement imbriquée si: p>

  • s est vide, li>
  • s a la forme "(u)" où U est une chaîne correctement imbriquée, li>
  • s a la forme "vw" où v et w sont cordes correctement imbriquées. li> ul>

    Par exemple, "(() (() ()) ()" est correctement imbriqué et "())" n'est pas. P>

    écrire une fonction p> 

    def nesting ( s )
    # write your code here

    if s == '(()(())())' && s.length <= 1000000
        return 1
    elsif s == ' ' && s.length <= 1000000
        return 1
    elsif 
        s == '())'
        return 0
    end
end

2 commentaires

Cela n'a pas vraiment beaucoup à voir avec les mathématiques, alors j'ai supprimé la balise.

Je peux imaginer que vous avez essayé de faire une définition récursive, mais ce n'est pas le cas.

8 Réponses :

0
votes

Votre solution renvoie uniquement la bonne réponse pour les chaînes "(() (()) ())" et "())". Vous avez sûrement besoin d'une solution qui fonctionne pour n'importe quelle chaîne!

comme démarrage, que diriez-vous de compter le nombre d'occurrences de ( et ) et de voir s'ils sont égaux?

2 commentaires

')))) (((«passerait le test de comptage, mais n'est pas valide selon la spécification

Bien sûr, c'est pourquoi j'ai dit «comme un début»! Je ne voulais pas donner au jeu complètement!

2
votes

Vous avez raison d'être inquiet; Je pense que vous avez la très mauvaise fin du bâton, et vous résolvez le problème trop littéralement (l'info que la chaîne ne dépasse pas 1 000 000 caractères suffit à empêcher les gens de s'inquiéter de la ralentissement de leur code si la La longueur était de 100imes qui, et les exemples ne sont que des exemples - pas la liste définitive des chaînes que vous pouvez vous attendre à recevoir)

Je ne vais pas faire vos devoirs pour vous (en écrivant le code), mais vous donnera un pointeur à une solution qui me survient:

La chaîne est correctement imbriquée si chaque support gauche a un support de droite à droite, ou un ensemble de supports correctement imbriqués entre eux. Donc, comment diriez-vous d'une fonction récursive ou d'une boucle, qui supprime les correspondances de la chaîne »()». Lorsque vous manquez d'allumettes, vous êtes parti? Rien? C'était une corde correctement imbriquée alors. Quelque chose d'autre (comme ')' ou ') (', etc.) signifierait qu'il n'était pas correctement imbriqué à la première place.

0 commentaires
15
votes

Voici des descriptions de deux algorithmes qui devraient accomplir l'objectif. Je laisserai un exercice au lecteur pour les transformer en code (à moins que vous ne demandiez explicitement une solution de code):

  1. Démarrer avec une variable définie sur 0 et boucle via chaque caractère de la chaîne: lorsque vous voyez un '(', ajoutez-en une à la variable; quand vous voyez un ')' , Soustrayez-en une de la variable. Si la variable devient négative, vous avez déjà vu trop ») 'et peut retourner 0 immédiatement. Si vous avez fini de boucler via les caractères et que la variable n'est pas exactement 0 , alors vous avez eu trop '(' et devrait renvoyer 0

  2. Supprimez chaque occurrence de '()' dans la chaîne (remplacez-le par ''). Continuez à faire cela jusqu'à ce que vous trouviez que rien n'a été remplacé (cochez la valeur de retour de gsub! ). Si la chaîne est vide, les parenthèses étaient assorties. Si la chaîne n'est pas vide, c'était incompatible.

3 commentaires

Ajout pour # 2, supprimez d'abord tous les caractères qui ne sont pas ( ou ) .

@gnur: La description du problème ne semble pas permettre d'autres caractères de la chaîne.

@RHseeger ah, je vois, j'ai mal lu. Je pensais que cela dit que cela ne consiste en aucun caractère et ( et ) .

4
votes

Vous n'êtes pas censé énumérer les exemples donnés. Vous êtes censé résoudre le problème généralement. Vous n'êtes pas non plus censé vérifier que la longueur est inférieure à 1000000, vous êtes autorisé à supposer cela.

La solution la plus simple à l'avant à ce problème est de parcourir la chaîne et de garder une trace du nombre de parenthèses ouvertes en ce moment. Si vous voyez une parenthèse de fermeture lorsque aucune parenthèses n'est actuellement ouverte, la chaîne n'est pas bien équilibrée. Si des parenthèses sont toujours ouvertes lorsque vous atteignez la fin, la chaîne n'est pas bien équilibrée. Sinon c'est.

Vous pouvez également transformer la spécification directement en un motif de regex à l'aide de la fonction de regex récursive de Ruby 1.9 si vous étiez tellement enclin.

1 commentaires

Pour la route des regex, check media.pragprrog.com/tities/ruby3/...<

1
votes

Définir la méthode: xxx

et testez-le: xxx

6 commentaires

Notez que cela peut être fait beaucoup plus bien par A) à l'aide d'un littéral à chaîne au lieu d'une regex et b) Vérification de la valeur de retour de gsub! (peut-être avec un DUP à l'avance préserver l'original)

@Yar, non je n'ai pas :) La seule chose qui n'est pas traitée dans mon code est à la vérification de la chaîne vide au début de Check_Nest. Mais ce n'est qu'une ligne de code: si str.empty? retourne vrai

@Yar, lisez la question: une chaîne s constituée uniquement de caractères '(' et ')' ... TOUTES QUESTIONS?

Pas de questions et +1 (déjà éteint lorsque j'ai quitté le premier commentaire).

@Yar, merci. En outre, la regex de votre type de quiz avec des lettres dans le commentaire précédent peut être motif = / ([^ (^)] *) /

@HCK à quoi ressemblerait la regex récursive? ;)

3
votes

Vous pouvez résoudre ce problème théoriquement. En utilisant une grammaire comme ceci: xxx

La grammaire doit être facilement résolvable par algorithme récursif. Ce serait la solution la plus élégante. Sinon comme déjà mentionné ici compter les parenthèses ouvertes.

0 commentaires
3
votes

Voici une solution soignée de le faire à l'aide d'injecter: xxx

0 commentaires
4
votes

Mon algorithme utiliserait des piles à cette fin. Les piles sont destinées à résoudre ces problèmes

Algorithme
  1. Définissez un hachage qui détient la liste des supports équilibrés pour instance {"(" => ")" "," {"=>"} ", et ainsi de suite ...}
  2. Déclarez une pile (dans notre cas, une matrice) I.e. Sharelets = []
  3. boucle à travers la chaîne en utilisant chaque_char et comparez chaque caractère avec des clés du hachage et poussez-la sur les crochets
  4. Dans la même boucle, comparez-la avec les valeurs du hachage et faites apparaître le caractère des crochets

  5. à la fin, si la pile de supports est vide, les crochets sont équilibrés.

    Def Sharkets_balancé? (String) renvoyer false si string.length <2 brackets_hash = {"(" => ")" "," {"=>"} "," ["=>"] "} crochets = [] string.each_char do | x | Supports.Push (x) Si BriquesTS_HASH.KEYS.Include? (x) Supports.pop si des crottes_hash.values.include? (x) finir Les crochets de retour.empty? fin

1 commentaires

Cela donnera un résultat incorrect si string est égal à ') ()' . Les premières parenthèses apparaîtront à une matrice vide, laissant des crochets inchangés et les parenthèses suivantes passeront le test.

Articles qui pourrait vous intéresser :

Problème lors de l'installation de ruby-2.7.1
commande pry introuvable après l'installation de gem
nokogiri ne s'installe pas dans ruby 2.7.1 centos 7.2
Comment masquer le titre du formulaire qui apparaît à l'intérieur d'une balise de légende lors de la génération de cases à cocher pour une association à l'aide de simple-form?