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

Question

J'ai récemment été confronté à ce problème intéressant. On vous donne une chaîne de caractères contenant uniquement les caractères '(' , ')' , '{' , '}' , '[' et ']' par exemple, "[{()}]" vous devez écrire une 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 être fermées dans le bon ordre, par exemple "()" et "()[]{}" sont toutes valides mais "(]" , "([)]" et "{{{{" ne le sont pas !

J'ai trouvé une solution de complexité O(n) en temps et O(n) en espace, qui fonctionne bien :

1. Maintenir une pile de caractères.
2. Chaque fois que vous trouvez un appareil dentaire ouvert '(' , '{' OU '[' le pousser sur la pile.
3. Chaque fois que vous trouvez un appareil dentaire fermé ')' , '}' OU ']' Vérifiez si le sommet de la pile correspond à la parenthèse ouvrante, si oui, ouvrez la pile, sinon interrompez la boucle et retournez false.
4. Répétez les étapes 2 - 3 jusqu'à la fin de la ficelle.

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

Ma question est donc de savoir si nous pouvons résoudre ce problème dans un espace O(1).

Answer 1

En référence à l'excellente réponse de Matthieu M. Voici une mise en œuvre en C# qui semble fonctionner à merveille.

/// <summary>
/// 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.
/// </summary>
/// <param name="input">Input string, consisting of nothing but various types of brackets.</param>
/// <returns>True if brackets are well formed, false if not.</returns>
static bool IsWellFormedBrackets(string input)
{
    string previous = "";
    while (input.Length != previous.Length)
    {
        previous = input;
        input = input
            .Replace("()", String.Empty)
            .Replace("[]", String.Empty)
            .Replace("{}", String.Empty);                
    }
    return (input.Length == 0);
}

En fait, tout ce qu'il fait, c'est supprimer des paires de parenthèses jusqu'à ce qu'il n'y en ait plus aucune à supprimer ; s'il reste quelque chose, c'est que les parenthèses ne sont pas bien formées.

Exemples de parenthèses bien formées :

()[]
{()[]}

Exemple de parenthèses mal formées :

([)]
{()[}]

Answer 2

En fait, il existe un algorithme déterministe de log-space dû à Ritchie et Springsteel : http://dx.doi.org/10.1016/S0019-9958(72)90205-7 ( paywalled, sorry pas en ligne). Comme nous avons besoin de bits logarithmiques pour indexer la chaîne de caractères, cette méthode est optimale en termes d'espace.

---

Si vous êtes prêt à accepter une erreur unilatérale, alors il existe un algorithme qui utilise n polylog(n) temps et polylog(n) espace : http://www.eccc.uni-trier.de/report/2009/119/

Answer 3

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

Bien sûr, il s'agit d'une machine de Turing. Je m'attendrais à ce que ce soit également vrai pour les machines RAM à mots fixes.

Answer 4

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

Il s'agit d'un algorithme destructeur, ce qui signifie que si vous avez un jour besoin de la chaîne de caractères, il ne vous sera d'aucune utilité (puisque vous devrez la recopier).

Sinon, l'algorithme fonctionne avec un simple index dans la chaîne actuelle.

L'idée est de supprimer les paires l'une après l'autre :

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

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

Algorithme :

1. i := 0
2. Trouvez une paire assortie parmi i . Si aucun n'est trouvé, alors la chaîne n'est pas valide. Si une chaîne est trouvée, alors i être l'indice du premier caractère.
3. Retirer [i:i+1] à partir de la chaîne
4. Si i est à 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 d'appariement, i := i-1 et retour à 3.
6. Sinon, retour au point 1.

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

• chaque itération de la boucle enlève 2 caractères de la chaîne de caractères
• l'étape 2., qui est linéaire, est naturellement liée ( i ne peut pas croître indéfiniment)

Et c'est O(1) dans l'espace car seul l'index est nécessaire.

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

À moins, bien sûr, que je ne me trompe profondément quelque part... et peut-être que quelqu'un pourrait utiliser l'idée originale (il y a une paire quelque part) à meilleur escient.

Answer 5

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

Pour optimiser l'espace, vous pouvez effectuer un codage de la longueur de votre pile, mais je doute que cela vous apporte beaucoup, sauf dans des cas tels que {{{{{{{{{{}}}}}}}}}} .