Comment trouver la validité d’une chaîne de parenthèses, d’accolades et de crochets?

Je suis récemment entré en contact avec ce problème intéressant. Vous recevez une chaîne contenant uniquement les caractères '(' , ')' , '{' , '}' , '[' et ']' , par exemple, "[{()}]" , vous devez écrire un fonction qui vérifiera la validité d’une telle chaîne d’entrée, la fonction peut être comme ceci:
bool isValid(char* s);
ces parenthèses doivent se fermer dans le bon ordre, par exemple "()" et "()[]{}" sont tous valables mais "(]" , "([)]" et "{{{{" ne le sont pas!

Je suis sorti avec la solution de complexité O (n) time et O (n) suivante, qui fonctionne bien:

  1. Maintenir une stack de caractères.
  2. Chaque fois que vous trouvez des accolades, '(' , '{' OU '[' poussez-le sur la stack.
  3. Chaque fois que vous trouvez des accolades fermantes ')' , '}' OR ']' , vérifiez si le haut de la stack correspond à la parenthèse d’ouverture, si oui, ouvrez la stack, sinon casser la boucle et retourner false.
  4. Répétez les étapes 2 à 3 jusqu’à la fin de la chaîne.

Cela fonctionne, mais pouvons-nous l’optimiser pour l’espace, peut être un espace supplémentaire constant, je comprends que la complexité du temps ne peut pas être inférieure à O (n) car nous devons examiner chaque caractère.

Donc, ma question est de savoir si nous pouvons résoudre ce problème dans l’espace O (1)?

En fait, il y a un algorithme logistic -espace déterministe dû à Ritchie et à Springsteel: http://dx.doi.org/10.1016/S0019-9958(72)90205-7 (avec paywall, désolé pas en ligne). Comme nous avons besoin de bits de journal pour indexer la chaîne, cela est optimal pour l’espace.


Si vous êtes prêt à accepter une erreur unilatérale, il existe un algorithme utilisant n polylog (n) time et polylog (n) space: http://www.eccc.uni-sortinger.de/report/2009/119 /

En référence à l’excellente réponse de Matthieu M. , voici une implémentation en C # qui semble fonctionner à merveille.

 ///  /// Checks to see if brackets are well formed. /// Passes "Valid parentheses" challenge on www.codeeval.com, /// which is a programming challenge site much like www.projecteuler.net. ///  /// Input ssortingng, consisting of nothing but various types of brackets. /// True if brackets are well formed, false if not. static bool IsWellFormedBrackets(ssortingng input) { ssortingng previous = ""; while (input.Length != previous.Length) { previous = input; input = input .Replace("()", Ssortingng.Empty) .Replace("[]", Ssortingng.Empty) .Replace("{}", Ssortingng.Empty); } return (input.Length == 0); } 

Essentiellement, tout ce qu’il fait, c’est d’éliminer les paires de crochets jusqu’à s’il rest quelque chose, les crochets ne sont pas bien formés.

Exemples de brackets bien formés:

 ()[] {()[]} 

Exemple de crochets mal formés:

 ([)] {()[}] 

Si l’entrée est en lecture seule, je ne pense pas que nous puissions faire de l’espace O (1). C’est un fait bien connu que tout langage décidable de l’espace O (1) est régulier (c’est-à-dire inscriptible en tant qu’expression régulière). L’ensemble de chaînes que vous avez n’est pas un langage normal.

Bien sûr, il s’agit d’une machine de Turing. Je m’attendrais à ce que ce soit vrai pour les machines RAM à mot fixe aussi.

Edit: Bien que simple, cet algorithme est en fait O (n ^ 2) en termes de comparaisons de caractères. Pour le démontrer, on peut simplement générer une chaîne sous la forme '(' * n + ')' * n .

J’ai une idée simple, mais peut-être erronée, que je soumettrai à vos critiques.

C’est un algorithme destructif, ce qui signifie que si vous avez besoin de la chaîne, cela ne vous aidera pas (puisque vous aurez besoin de la copier).

Sinon, l’algorithme fonctionne avec un index simple dans la chaîne en cours.

L’idée est de supprimer les paires les unes après les autres:

  1. ([{}()])
  2. ([()])
  3. ([])
  4. ()
  5. empty -> OK

Il est basé sur le simple fait que si nous avons des paires correspondantes, au moins une est de la forme () sans aucun caractère de paire entre elles.

Algorithme:

  1. i := 0
  2. Trouvez une paire correspondante à partir de i . Si aucun n’est trouvé, la chaîne n’est pas valide. Si on en trouve un, soit i soit l’index du premier caractère.
  3. Supprimer [i:i+1] de la chaîne
  4. Si i à la fin de la chaîne et que la chaîne n’est pas vide, c’est un échec.
  5. Si [i-1:i] est une paire correspondante, i := i-1 et retour à 3.
  6. Sinon, retour à 1.

L’algorithme est O(n) en complexité parce que:

  • chaque itération de la boucle supprime 2 caractères de la chaîne
  • l’étape 2, qui est linéaire, est naturellement liée ( i ne peux pas grandir indéfiniment)

Et c’est O(1) dans l’espace car seul l’index est requirejs.

Bien sûr, si vous ne pouvez pas vous permettre de détruire la chaîne, vous devrez la copier, et c’est O(n) dans l’espace, donc pas de réel avantage!

À moins, bien sûr, que je sois profondément trompé quelque part… et peut-être que quelqu’un pourrait utiliser l’idée originale (il y a une paire quelque part) pour avoir un meilleur effet.

Je doute que vous trouviez une meilleure solution, car même si vous utilisez des fonctions internes pour écrire ou compter des occurrences, elles ont toujours un coût O (…). Je dirais que votre solution est la meilleure 🙂

Pour optimiser votre espace, vous pouvez effectuer un encodage de longueur d’exécution sur votre stack, mais je doute que cela vous rapporte beaucoup, sauf dans des cas tels que {{{{{{{{{{}}}}}}}}}} .

http://www.sureinterview.com/shwqst/112007

Il est naturel de résoudre ce problème avec une stack.

Si seulement ‘(‘ et ‘)’ sont utilisés, la stack n’est pas nécessaire. Nous avons juste besoin de maintenir un compteur pour la gauche sans correspondance (‘. L’expression est valide si le compteur est toujours non négatif pendant la correspondance et est nul à la fin.

Dans le cas général, bien que la stack soit toujours nécessaire, la profondeur de la stack peut être réduite en utilisant un compteur pour les accolades inégalées.

C’est un code java fonctionnel où je filtre les parenthèses de l’expression de chaîne, puis vérifie le format en remplaçant les accolades bien formées par des nulls

Exemple d’ input = (a+{b+c}-[de])+[f]-[g] FilterBrackets affichera = ({}[])[][] Ensuite, je vérifie la forme.

Les commentaires sont les bienvenus.

 public class ParanSsortingng { public static void main(Ssortingng[] args) { Ssortingng s = FilterBrackets("(a+{b+c}-[de])[][]"); while ((s.length()!=0) && (s.contains("[]")||s.contains("()")||s.contains("{}"))) { //System.out.println(s.length()); //System.out.println(s); s = s.replace("[]", ""); s = s.replace("()", ""); s = s.replace("{}", ""); } if(s.length()==0) { System.out.println("Well Formed"); } else { System.out.println("Not Well Formed"); } } public static Ssortingng FilterBrackets(Ssortingng str) { int len=str.length(); char arr[] = str.toCharArray(); Ssortingng filter = ""; for (int i = 0; i < len; i++) { if ((arr[i]=='(') || (arr[i]==')') || (arr[i]=='[') || (arr[i]==']') || (arr[i]=='{') || (arr[i]=='}')) { filter=filter+arr[i]; } } return filter; } } 

La modification suivante de la réponse de Sbusidan est O ( n 2 ) temps complexe mais espace O (log n ) simple.

 #include  #include  #include  char opposite(char bracket) { switch(bracket) { case '[': return ']'; case '(': return ')'; } } bool is_balanced(int length, char *s) { int depth, target_depth, index; char target_bracket; if(length % 2 != 0) { return false; } for(target_depth = length/2; target_depth > 0; target_depth--) { depth=0; for(index = 0; index < length; index++) { switch(s[index]) { case '(': case '[': depth++; if(depth == target_depth) target_bracket = opposite(s[index]); break; case ')': case ']': if(depth == 0) return false; if(depth == target_depth && s[index] != target_bracket) return false; depth--; break; } } } } void main(char* argv[]) { char input[] = "([)[(])]"; char *balanced = is_balanced(strlen(input), input) ? "balanced" : "imbalanced"; printf("%s is %s.\n", input, balanced); } 

Si vous pouvez écraser la chaîne d’entrée (ce qui n’est pas raisonnable dans les cas d’utilisation que j’envisage, mais que diable …), vous pouvez le faire dans un espace constant, bien que je pense que le temps passe à O (n 2 ) .

Comme ça:

 ssortingng s = input char c = null int i=0 do if s[i] isAOpenChar() c = s[i] else if c = isACloseChar() if closeMatchesOpen(s[i],c) erase s[i] while s[--i] != c ; erase s[i] c == null i = 0; // Not optimal! It would be better to back up until you find an opening character else return fail end if while (s[++i] != EOS) if c==null return pass else return fail 

L’essentiel est d’utiliser la première partie de l’entrée en tant que stack.

Je sais que je suis un peu en retard pour cette fête; c’est aussi mon tout premier article sur StackOverflow.

Mais quand j’ai parcouru les réponses, j’ai pensé que je pourrais peut-être trouver une meilleure solution.

Donc, ma solution consiste à utiliser quelques pointeurs.
Il n’a même pas besoin d’utiliser de mémoire vive, car des registres peuvent être utilisés pour cela.
Je n’ai pas testé le code; c’est écrit à la volée.
Vous devrez corriger mes fautes de frappe et le déboguer, mais je pense que vous en aurez l’idée.

Utilisation de la mémoire: Seuls les processeurs enregistrent dans la plupart des cas.
Utilisation du processeur: Cela dépend, mais environ deux fois le temps nécessaire pour lire la chaîne.
Modifie la mémoire: non

b: ssortingng b eginning, e: chaîne e nd.
l: l position arrière, r: position droite.
c: c har, m: m atch char

si r arrive à la fin de la chaîne, nous avons du succès.
Je reviens de r vers b.
À chaque fois que r rencontre un nouveau type de départ, définissez l = r.
quand j’atteins b, nous en avons fini avec le bloc; sauter au début du bloc suivant.

 const char *chk(const char *b, int len) /* option 2: remove int len */ { char c, m; const char *l, *r; e = &b[len]; /* option 2: remove. */ l = b; r = b; while(r < e) /* option 2: change to while(1) */ { c = *r++; /* option 2: if(0 == c) break; */ if('(' == c || '{' == c || '[' == c) { l = r; } else if(')' == c || ']' == c || '}' == c) { /* find 'previous' starting brace */ m = 0; while(l > b && '(' != m && '[' != m && '{' != m) { m = *--l; } /* now check if we have the correct one: */ if(((m & 1) + 1 + m) != c) /* cryptic: convert starting kind to ending kind and match with c */ { return(r - 1); /* point to error */ } if(l <= b) /* did we reach the beginning of this block ? */ { b = r; /* set new beginning to 'head' */ l = b; /* obsolete: make left is in range. */ } } } m = 0; while(l > b && '(' != m && '[' != m && '{' != m) { m = *--l; } return(m ? l : NULL); /* NULL-pointer for OK */ } 

Après avoir réfléchi à cette approche pendant un certain temps, j’ai réalisé que cela ne fonctionnerait pas comme il le fait actuellement.
Le problème sera que si vous avez “[() ()]”, cela échouera lorsque vous atteindrez le “]”.
Mais au lieu de supprimer la solution proposée, je vais la laisser ici, car il n’est pas impossible de la faire fonctionner, mais cela demande quelques modifications.

 /** * * @author madhusudan */ public class Main { /** * @param args the command line arguments */ public static void main(Ssortingng[] args) { new Main().validateBraces("()()()()(((((())))))()()()()()()()()"); // TODO code application logic here } /** * @Use this method to validate braces */ public void validateBraces(Ssortingng teststr) { SsortingngBuffer teststr1=new SsortingngBuffer(teststr); int ind=-1; for(int i=0;i0) { System.out.println("Invalid"); }else { System.out.println("Valid"); } } public boolean isOpen(char ch) { if("(".equals(Character.toSsortingng(ch))) { return true; }else return false; } public boolean isClose(char ch) { if(")".equals(Character.toSsortingng(ch))) { return true; }else return false; } public SsortingngBuffer deleteOpenBraces(SsortingngBuffer str,int start,int end) { char ar[]=str.toSsortingng().toCharArray(); for(int i=start;i 

Au lieu de mettre des accolades dans la stack, vous pouvez utiliser deux pointeurs pour vérifier les caractères de la chaîne. l’un part du début de la chaîne et l’autre part de la fin de la chaîne. quelque chose comme

 bool isValid(char* s) { start = find_first_brace(s); end = find_last_brace(s); while (start <= end) { if (!IsPair(start,end)) return false; // move the pointer forward until reach a brace start = find_next_brace(start); // move the pointer backward until reach a brace end = find_prev_brace(end); } return true; } 

Notez que certains casiers d'angle ne sont pas traités.

Je pense que vous pouvez implémenter un algorithme O (n). Vous devez simplement initialiser une variable de compteur pour chaque type: les crochets, les carrés et les parenthèses normales. Après cela, vous devriez itérer la chaîne et augmenter le compteur correspondant si le support est ouvert, sinon le diminuer. Si le compteur est négatif, retournez faux. Après je pense que vous pouvez implémenter un algorithme O (n). Vous devez simplement initialiser une variable de compteur pour chaque type: les crochets, les carrés et les parenthèses normales. Après cela, vous devriez itérer la chaîne et augmenter le compteur correspondant si le support est ouvert, sinon le diminuer. Si le compteur est négatif, retournez faux. Après avoir compté tous les crochets, vous devez vérifier si tous les compteurs sont à zéro. Dans ce cas, la chaîne est valide et vous devez retourner true.

Vous pouvez fournir la valeur et vérifier si elle est valide, elle affichera OUI sinon elle affichera NON

 static void Main(ssortingng[] args) { ssortingng value = "(((([{[(}]}]))))"; List jj = new List(); if (!(value.Length % 2 == 0)) { Console.WriteLine("NO"); } else { bool isValid = true; List items = new List(); for (int i = 0; i < value.Length; i++) { string item = value.Substring(i, 1); if (item == "(" || item == "{" || item == "[") { items.Add(item); } else { string openItem = items[items.Count - 1]; if (((item == ")" && openItem == "(")) || (item == "}" && openItem == "{") || (item == "]" && openItem == "[")) { items.RemoveAt(items.Count - 1); } else { isValid = false; break; } } } if (isValid) { Console.WriteLine("Yes"); } else { Console.WriteLine("NO"); } } Console.ReadKey(); } 
 var verify = function(text) { var symbolsArray = ['[]', '()', '<>']; var symbolReg = function(n) { var reg = []; for (var i = 0; i < symbolsArray.length; i++) { reg.push('\\' + symbolsArray[i][n]); } return new RegExp('(' + reg.join('|') + ')','g'); }; // openReg matches '(', '[' and '<' and return true or false var openReg = symbolReg(0); // closeReg matches ')', ']' and '>' and return true or false var closeReg = symbolReg(1); // nestTest matches openSymbol+anyChar+closeSymbol // and returns an obj with the match str and it's start index var nestTest = function(symbols, text) { var open = symbols[0] , close = symbols[1] , reg = new RegExp('(\\' + open + ')([\\s\\S])*(\\' + close + ')','g') , test = reg.exec(text); if (test) return { start: test.index, str: test[0] }; else return false; }; var recursiveCheck = function(text) { var i, nestTests = [], test, symbols; // nestTest with each symbol for (i = 0; i < symbolsArray.length; i++) { symbols = symbolsArray[i]; test = nestTest(symbols, text); if (test) nestTests.push(test); } // sort tests by start index nestTests.sort(function(a, b) { return a.start - b.start; }); if (nestTests.length) { // build nest data: calculate match end index for (i = 0; i < nestTests.length; i++) { test = nestTests[i]; var end = test.start + ( (test.str) ? test.str.length : 0 ); nestTests[i].end = end; var last = (nestTests[i + 1]) ? nestTests[i + 1].index : text.length; nestTests[i].pos = text.substring(end, last); } for (i = 0; i < nestTests.length; i++) { test = nestTests[i]; // recursive checks what's after the nest if (test.pos.length && !recursiveCheck(test.pos)) return false; // recursive checks what's in the nest if (test.str.length) { test.str = test.str.substring(1, test.str.length - 1); return recursiveCheck(test.str); } else return true; } } else { // if no nests then check for orphan symbols var closeTest = closeReg.test(text); var openTest = openReg.test(text); return !(closeTest || openTest); } }; return recursiveCheck(text); }; 

Utiliser la programmation c # OOPS … Solution simple et petite

 Console.WriteLine("Enter the ssortingng"); ssortingng str = Console.ReadLine(); int length = str.Length; if (length % 2 == 0) { while (length > 0 && str.Length > 0) { for (int i = 0; i < str.Length; i++) { if (i + 1 < str.Length) { switch (str[i]) { case '{': if (str[i + 1] == '}') str = str.Remove(i, 2); break; case '(': if (str[i + 1] == ')') str = str.Remove(i, 2); break; case '[': if (str[i + 1] == ']') str = str.Remove(i, 2); break; } } } length--; } if(str.Length > 0) Console.WriteLine("Invalid input"); else Console.WriteLine("Valid input"); } else Console.WriteLine("Invalid input"); Console.ReadKey(); 

C’est ma solution au problème. O (n) est la complexité du temps sans complexité d’espace. Code en C.

 #include  #include  #include  bool checkBraket(char *s) { int curly = 0, rounded = 0, squre = 0; int i = 0; char ch = s[0]; while (ch != '\0') { if (ch == '{') curly++; if (ch == '}') { if (curly == 0) { return false; } else { curly--; } } if (ch == '[') squre++; if (ch == ']') { if (squre == 0) { return false; } else { squre--; } } if (ch == '(') rounded++; if (ch == ')') { if (rounded == 0) { return false; } else { rounded--; } } i++; ch = s[i]; } if (curly == 0 && rounded == 0 && squre == 0){ return true; } else { return false; } } void main() { char myssortingng[] = "{{{{{[(())}}]}}}"; int answer = checkBraket(myssortingng); printf("my answer is %d\n", answer); return; }