Comment vérifier si les parenthèses sont identiques

Question

Je voudrais vérifier si la chaîne d'entrée contient la même quantité de parenthèses d'ouverture/fermeture. Si oui, imprimez vrai sinon faux. J'ai écrit ce code mais il y a un bug que quelqu'un peut aider?

See My Code Cela fonctionne bien si j'entre une chaîne «() » qui commence avec le support ouvert et se termine avec le support proche, mais si je rentre «) (» il imprime toujours sur une vraie sortie ?. doit être:

() = true 
(())=true 
()) = false 
(() = false 
)(= false 
)(() = false 
etc... 

Merci pour l'aide

EDIT:

using System; 

public class Program 
{ 
    public void Main() 
{ 

    CheckParentheses ("()"); 
} 

public void CheckParentheses (string inputParentheses){ 

int openParentheses = 0; 
int closeParentheses = 0; 
for (int i = 0; i < inputParentheses.Length; i++) 
{ 
    if (inputParentheses[i] == '(') 
    { 
     openParentheses++; 
    } 

    if (inputParentheses[i] == ')') { 
     closeParentheses++; 
    } 


    if (openParentheses == closeParentheses) 

     Console.WriteLine("true"); 

    } 

} 

} 

Answer 1

Si jamais il y a un plus grand nombre de fermé qu'Open, il devrait re tourner un faux, non? Ainsi, vous pouvez simplement ajouter au milieu de la boucle:

 if (closeParentheses > openParentheses) { 
     Console.WriteLine("false"); 
    } 

Answer 2

Au lieu de compter les parenthesys ouvrir/fermer, vous pouvez vérifier leur ordre

public void CheckParentheses(string inputParentheses) 
{ 
    // Level counter 
    int parenLevel = 0; 
    for (int i = 0; i < inputParentheses.Length; i++) 
    { 
     // Open always good, increment the level 
     if (inputParentheses[i] == '(') 
      parenLevel++; 
     else if (inputParentheses[i] == ')') 
      parenLevel--; 

     // Closing good, but only if the level doesn't drop under zero 
     if (parenLevel < 0) 
     { 
      Console.WriteLine("false"); 
      return; 
     } 
    } 
    // At the end of the loop, the level should always be zero 
    if(parenLevel != 0) 
     Console.WriteLine("false"); 
    else 
     Console.WriteLine("true"); 
} 

Answer 3

public static bool CheckParentheses(string inputParentheses) 
{ 
    if ((inputParentheses.Length % 2) != 0 || inputParentheses[0] ==')' || inputParentheses[inputParentheses.Length-1] == '(') 
     return false; 

    for(int i = 0; i < inputParentheses.Length/2; i++) 
    { 
     if(inputParentheses[i] != '(' || inputParentheses[inputParentheses.Length-i-1] != ')') 
      return false; 
    } 
    return true; 
} 

Answer 4

D'abord, nous devons comprendre clairement ce que propriétés que nous essayons de prouver à propos de la chaîne. Cela demande du temps, de la réflexion et de l'imagination.

Nous pourrions dire que la chaîne doit être une phrase du langage décrit par S → "(" S ")" S | ε, auquel cas notre tâche est de créer un analyseur. La chaîne est valide si et seulement si l'analyseur l'accepte.

Une autre approche consiste à interpréter « (» comme pousser et «) » comme pop pour une pile, en ordre de gauche à droite. Ensuite, la chaîne est valide si et seulement si le programme indiqué ne fait pas apparaître une pile vide et se termine également avec une pile vide. Nous pouvons tester cela simplement en exécutant le programme et en observant l'état. Une autre approche consiste à interpréter une chaîne de "(" et ")" comme une séquence de "1" et "-1" respectivement. Ceci est similaire à l'interprétation de la pile - la similarité peut être vue à travers les nombres de Peano. Ensuite, la chaîne est valide si et seulement s'il n'existe pas une somme de préfixe inférieure à zéro et que la somme totale est nulle.

Je vais expliquer comment implémenter l'interprétation des nombres entiers en C#. Commencez par définir la fonction, avec la chaîne en entrée et notre réponse booléenne en sortie.

bool AreParensBalanced(string input) { … }

D'abord interpréter les parenthèses comme entiers.

var interpreted = input.Select(c => c == '(' ? 1 : -1);

Suivant trouver les sommes préfixe. Ici, je parcours vers un IObservable car Scan n'est pas défini pour IEnumerable - vous pouvez définir Scan pour IEnumerable mais je préfère utiliser l'implémentation existante.

var prefixSums = interpreted.ToObservable().Scan(0, (a, b) => a + b).ToEnumerable()

trouver maintenant la somme totale.

var totalSum = interpreted.Aggregate(0, (a, b) => a + b);

Connaître les sommes de préfixe et la somme totale, la réponse peut être trouvée.

return prefixSums.All(x => x >= 0) && totalSum == 0;

Notez que « il n'existe pas un x tel que P (x) est vrai » est le même que « pour tout x, non P (x) est vrai », ce qui est de savoir comment je suis avec All(x => x >= 0) à partir de la spécification.