Citation : shareman

unsigned int* incr(unsigned int* i)
{
    (*i)++; return i;
}

#include <stdio.h>
#include <time.h>

unsigned int* incr(unsigned int* i)
{
    (*i)++; return i;
}

int pth(const char* str, unsigned int* i)
{
    if(   (str[*i] == '\0')
       || (str[*i] == '(' && pth(str, incr(i)) && str[*i] == ')' && pth(str, incr(i)))
       || (str[*i] != ')' && pth(str, incr(i)))  )
        return 1;
    return 1;
}

int shareman(const char* str)
{
    unsigned int i = 0;
    pth(str, &i);
    if(i != strlen(str))
        return 0;
    return 1;
}


int parentheses(const char *chaine){
    int i = 0;

    int p = 0;

    while(chaine[i] != '\0'){
        if(chaine[i] == '(')        p++;
        else if(chaine[i] == ')')   p--;
        if(p < 0) return 0;
        i++;
    }

    if(p > 0)
        return 0;

    return 1;
}

int main(void){

    char chaine[] = "Je suis une (grande) chaine avec (plein(s)) de parenthese(s)";

    time_t t1, t2;

    time(&t1);

	int a = 0;
    while(a < 10000000){
        /*parentheses(chaine);*/ /* 2 ou 3 secondes */
        shareman(chaine); /* 11 ou 12 secondes */
        a++;
    }

    time(&t2);

    printf("%.0f secondes\n", difftime(t2, t1));

    /*printf("Chaine: %d\n", parentheses(chaine));*/
    printf("Chaine: %d\n", shareman(chaine));

	return 0;
}

Citation

Quand le maître montre la lune, le disciple regarde le doigt

Citation : shareman

"Gueule de bois" ? Bon, si tu es là pour venger d'une façon ou d'une autre zx-spectrum, premièrement c'est con (car il doit parfaitement savoir qu'il s'est un peu comporté de manière idiote, surtout sur le topic if/else) et deuxièmement, ça ne sert à rien, car ça ne m'intéresse pas trop. Et hum 21, sans pointeurs et sans récursivité, la technique ne serait plus présentable.

Citation : shareman

Faire ça directement dans le if, c'est moche et c'est encore plus compliqué.

#include <stdio.h>
#include <time.h>

/* <shareman> */
unsigned int* incr(unsigned int* i)
{
    (*i)++; return i;
}

int pth(const char* str, unsigned int* i)
{
    if(   (str[*i] == '\0')
       || (str[*i] == '(' && pth(str, incr(i)) && str[*i] == ')' && pth(str, incr(i)))
       || (str[*i] != ')' && pth(str, incr(i)))  )
        return 1;
    return 1;
}

int shareman(const char* str)
{
    unsigned int i = 0;
    pth(str, &i);
    if(i != strlen(str))
        return 0;
    return 1;
}
/* </shareman> */




/* <shareman 2> */
int pth2(const char* str, unsigned int* i)
{
    if(   (str[*i] == '\0')
       || (str[*i] == '(' && ++(*i) && pth2(str, i) && str[*i] == ')' && ++(*i) && pth2(str, i))
       || (str[*i] != ')' && ++(*i) && pth2(str, i))  )
        return 1;
    return 1;
}

int shareman2(const char* str)
{
    unsigned int i = 0;
    pth2(str, &i);
    if(i != strlen(str))
        return 0;
    return 1;
}
/* </shareman 2> */




int parentheses(const char *chaine){
    int i = 0;

    int p = 0;

    while(chaine[i] != '\0'){
        if(chaine[i] == '(')
            p++;
        else if(chaine[i] == ')'){
            p--;
            if(p < 0) return 0;
        }
        i++;
    }

    if(p > 0)
        return 0;

    return 1;
}

int main(void){

    char chaine[] = "Je suis une (grande) chaine avec (plein(s)) de parenthese(s)";

    time_t t1, t2;

    time(&t1);

	int a = 0;
    while(a < 10000000){
        /*parentheses(chaine);*/ /* 2 ou 3 secondes */
        /*shareman(chaine);*/ /* 11 ou 12 secondes */
        shareman2(chaine); /* 8 ou 9 secondes */
        a++;
    }

    time(&t2);

    printf("%.0f secondes\n", difftime(t2, t1));

    /*printf("Chaine: %d\n", parentheses(chaine));*/
    /*printf("Chaine: %d\n", shareman(chaine));*/
    printf("Chaine: %d\n", shareman2(chaine));

	return 0;
}

Citation : shareman

Je crois qu'un code vaut mieux qu'un long discours :

// 1 : bien
// 0 : pas bien

/** pth -> ( pth ) pth | l pth | RIEN **/

unsigned int* incr(unsigned int* i)
{
    (*i)++; return i;
}

int pth(const char* str, unsigned int* i)
{
    if(   (str[*i] == '\0')
       || (str[*i] == '(' && pth(str, incr(i)) && str[*i] == ')' && pth(str, incr(i)))
       || (str[*i] != ')' && pth(str, incr(i)))  )
        return 1;
    return 1;
}

int verif(const char* str)
{
    unsigned int i = 0;
    pth(str, &i);
    if(i != strlen(str))
        return 0;
    return 1;
}

#include <stdio.h>
#include <string.h>

// 1 : bien
// 0 : pas bien

/** pth -> ( pth ) pth | l pth | RIEN **/

unsigned int* incr(unsigned int* i)
{
    (*i)++; return i;
}

int pth(const char* str, unsigned int* i)
{
printf("i=%u\n",*i);
    if(   (str[*i] == '\0')
       || (str[*i] == '(' && pth(str, incr(i)) && str[*i] == ')' && pth(str, incr(i)))
       || (str[*i] != ')' && pth(str, incr(i)))  )
        return 1;
    return 1;
}

int verif(const char* str)
{
    unsigned int i = 0;
    pth(str, &i);
    if(i != strlen(str))
        return 0;
    return 1;
}

int main(void)
{
char *str="((";
printf("\n%d\n",verif(str));

  return 0;
}

i=0
i=1
i=2
i=3
i=4
i=5
i=6
i=7
i=8

0

int pth(const char* str, unsigned int* i, unsigned int size)
{
    if((*i) >= size) {
        return 1;
    }
    if(   (str[*i] == '\0')
       || (str[*i] == '(' && pth(str, incr(i), size) && str[*i] == ')' && pth(str, incr(i), size))
       || (str[*i] != ')' && pth(str, incr(i), size))  )
        return 1;
    return 1;
}

Citation : shareman

Bon, normalement là c'est bon :

#include <stdio.h>
#include <string.h>


// 1 : bien
// 0 : pas bien

/** pth -> ( pth ) pth | l pth | RIEN **/

unsigned int* incr(unsigned int* i)
{
    (*i)++; return i;
}

int pth(const char* str, unsigned int* i, unsigned int size)
{
printf("i=%u\n",*i);
    if((*i) >= size) {
        return 1;
    }
    if(   (str[*i] == '\0')
       || (str[*i] == '(' && pth(str, incr(i), size) && str[*i] == ')' && pth(str, incr(i), size))
       || (str[*i] != ')' && pth(str, incr(i), size))  )
        return 1;
    return 1;
}



int verif(const char* str)
{
    unsigned int i = 0;
    pth(str, &i, strlen(str));
    if(i != strlen(str))
        return 0;
    return 1;
}

int main(void)
{
char *str="((";
printf("\n%d\n",verif(str));

  return 0;
}

i=0
i=1
i=2
i=3
i=4

0

Citation : shareman

L'idée et l'algorithme restent les-mêmes.

#include <stdio.h>

int estBienPar(char *s)
{
  int po = 0;                   /* parenthèses ouvertes */
  char c;                       /* pour éviter les indirections multiples */

  while ((c = *s++) && po >= 0)
    if (c == '(')
      po++;
    else if (c == ')')
      po--;
  /* 
     Les 4 lignes précédentes peuvent être remplacées par : 
       po += (c == '(') - (c == ')');
     C'est plus court mais peu lisible et moins
     efficace. */
  return po == 0;
}

int main(void)
{
  char *str = "((((nnnn)n))zero(o)ooo))";

  printf(estBienPar(str) == 1 ? "OK\n" : "KO\n");
  /* Un peu compliqué pour les débutants, désolé ! */

  return 0;
}

KO

Citation : candide

Salut !

int check(const char *str, int *i)
{
    switch(str[(*i)++]) {
    case '\0': return 0;
    case ')': return 1;
    case '(':
        if (check(str, i) != 1)
            return (-1);
        return check(str, i);
    default: return check(str, i);
    }
}

int valide(const char *str)
{
    int i = 0;
    return check(str, &i);
}

int check(const char *str, int *i)
{
    char c;
    switch(c = str[(*i)++]) {
    case '\0': return '\0';
    case ']': return '[';
    case ')': return '(';
    case '(':
    case '[':
        if (check(str, i) != c)
            return (-1);
        return check(str, i);
    default: return check(str, i);
    }
}

Citation : bluestorm

Pour ce qui est des performances, on peut écrire cet algorithme de manière efficace. J'ai fait une version pour voir, qui (bien que je ne l'aie pas spécialement optimisée) est presque aussi performante que l'algorithme naïf :

int check(const char *str, int *i)
{
    switch(str[(*i)++]) {
    case '\0': return 0;
    case ')': return 1;
    case '(':
        if (check(str, i) != 1)
            return (-1);
        return check(str, i);
    default: return check(str, i);
    }
}

int valide(const char *str)
{
    int i = 0;
    return check(str, &i);
}

#include <stdio.h>

int check(const char *str, int *i)
{
  switch (str[(*i)++])
    {
    case '\0':
      return 0;
    case ')':
      return 1;
    case '(':
      /* si un parenthèse ouverte n'est pas refermée, on renvoie -1 */
      if (check(str, i) != 1)
        return (-1);
      /* sinon on continue après la parenthèse fermante */
      return check(str, i);
    default:
      return check(str, i);
    }
}

int valide(const char *str)
{
  int i = 0;

  return check(str, &i);
}

int main(void)
{
  printf((valide("x(xx(xx)xx)xxxx") == 0) ? "OK\n" : "KO\n");
  printf((valide("x(x)x(xx)xx)xxxx") == 0) ? "OK\n" : "KO\n");
  printf((valide("cccccccccc") == 0) ? "OK\n" : "KO\n");

  return 0;
}

OK
KO
OK

zzz(rr(gg((hhhh)jjjjj)pppp)ooo)hhh

zzz(rr(gg(hhhhhhjjjjj)pppp)ooo)hhh

zzz(rr(gg(jjjjj)pppp)ooo)hhh

Citation : bluestorm

Pour voir son intérêt, on peut par exemple se poser la question suivante : comment vérifier si une expression pouvant utiliser plusieurs délimiteurs différents est bien parenthésée ? Par exemple si on autorise les parenthèses et les crochets, "([])" est bien parenthésée mais pas "([)]".

Citation : bluestorm

Avec la méthode de compteur, c'est à ma connaissance infaisable, ou du moins très difficile.

Citation : candide

Je n'ai pas vu quel algorithme tu voulais utiliser. Pour moi, fondamentalement il n'y en a qu'un : il s'agit de parcourir la chaîne de gauche à droite et de voir si l'écart entre les nombres de parenthèses ouvrantes et fermantes reste toujours positif ou nul et s'il est nul à la fin de la chaîne. À partir de là, on obtient le code itératif que presque tout le monde à trouvé, à des détails prêts près. La version récursive est de peu d'intérêt selon moi et elle est triviale à écrire.

Citation : candide

S'il fallait montrer quelque chose de savant (ce qui n'aurait a priori pas sa place dans ce topic destiné aux débutants), je pense que ce serait une implémentation via Flex et Bison. Je pense en effet que c'est sur des exemples simples comme celui-ci que l'on peut apprendre à utiliser ces puissants outils pour être capable de les adapter à des programmes beaucoup complexes.

Citation : frager50

Hors-Sujet : A quand l'exercice du mois de juillet ??