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

Vous pouvez seulement réduire la complexité spatiale à O( n /2) comme vous vous attendez toujours à avoir paires d'accolades et d'abandonner si vous avez atteint cette limite. Mais c'est toujours O( n ).

Answer 2

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

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

Si seuls '(' et ')' sont utilisés, la pile n'est pas nécessaire. Nous avons juste besoin de maintenir un compteur pour les '(' de gauche non appariés. L'expression est valide si le compteur est toujours non négatif pendant la correspondance et est égal à zéro à la fin.

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

Answer 3

Voici un code java fonctionnel dans lequel je filtre les parenthèses de l'expression de la chaîne de caractères, puis je vérifie si elles sont bien formées en remplaçant les parenthèses bien formées par des zéros.

Echantillon input = (a+{b+c}-[d-e])+[f]-[g] FilterBrackets produira = ({}[])[][] Ensuite, je vérifie si la forme est bonne.

Les commentaires sont les bienvenus.

public class ParanString {

    public static void main(String[] args) {

        String s = FilterBrackets("(a+{b+c}-[d-e])[][]");

        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 String FilterBrackets(String str)
    {
        int len=str.length();
        char arr[] = str.toCharArray();
        String 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;
    }

}

Answer 4

Si vous pouvez écraser la chaîne de caractères d'entrée (ce qui n'est pas raisonnable dans les cas d'utilisation que j'envisage, mais que diable...), vous pouvez le faire en espace constant, bien que je pense que le temps requis augmente jusqu'à O(n 2 ) .

Comme ça :

string 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

Il s'agit essentiellement d'utiliser la première partie de l'entrée comme pile.

Answer 5

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

Mais en regardant les réponses, j'ai pensé que je pourrais trouver une meilleure solution.

Ma solution consiste donc à utiliser quelques pointeurs.
Il n'est même pas nécessaire d'utiliser de la mémoire vive, puisque des registres peuvent être utilisés à cet effet.
Je n'ai pas testé le code ; il a été écrit à la volée.
Vous devrez corriger mes fautes de frappe, et le déboguer, mais je pense que vous aurez l'idée.

Utilisation de la mémoire : Seulement les registres du CPU dans la plupart des cas.
Utilisation du CPU : Cela dépend, mais environ deux fois le temps nécessaire à la lecture de la chaîne.
Modifie la mémoire : Non.

b : chaîne b e commencement, e : chaîne e nd.
l : l position gauche, r : r position droite.
c : c har, m : m atch char

si r atteint la fin de la chaîne, nous avons un succès.
L va à l'envers de r vers b.
Chaque fois que r rencontre un nouveau type de départ, on définit l = r.
lorsque l atteint b, nous avons terminé le bloc ; sautez 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é qu'elle ne fonctionnera pas telle qu'elle est actuellement.
Le problème est 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, elle nécessite cependant quelques modifications.