Contenu | Rechercher | Menus

Annonce

Si vous avez des soucis pour rester connecté, déconnectez-vous puis reconnectez-vous depuis ce lien en cochant la case
Me connecter automatiquement lors de mes prochaines visites.

À propos de l'équipe du forum.

#1 Le 02/05/2021, à 20:43

Tawal

Verif. couple de parenthèses - awk

Hello,

Après avoir lu cet excellent manuel de GNU awk, je me suis imposé un exercice pour mieux appréhender awk  et gawk.

Cet exercice consiste à vérifier que les parenthèses soient bien refermées dans un fichier.
Si une parenthèse (ouvrante ou fermante) isolée est repérée alors retourner le numéro de la ligne et la position en nb de caractères dans la ligne de cette parenthèse, ainsi que son type (ouvrante ou fermante).

Je ne veux pas discuter sur le fait de choisir une parenthèse ou un crochet ou une accolade, le principe reste exactement le même.
Non plus discuter sur le nombre de fichier à traiter.

Je reste dans un cas élémentaire : On ne recherche que les parenthèses ( et ). On ne traite qu'un seul fichier. Et on cherche les couples au travers tout le fichier (une parenthèse ouverte sur une ligne peut-être refermée sur une autre).

Voici la commande awk :

#!/bin/bash
#Nom : check-closed
ouv="("
ferm=")"

awk -v OUVERTE="$ouv" -v FERMEE="$ferm" '
    BEGIN{
        PROCINFO["sorted_in"]="@ind_num_asc"
        FS = ""                # Pour lire le fichier ligne par ligne, 1 caractère par champ
    }
    {
        for (i=1;i<=NF;i++){          # On note le n° de ligne, la position et le type de chaque parenthèse
            if($i==OUVERTE){
                aPar[++j]=1; aLine[j]=NR; aPos[j]=i
            }
            if($i==FERMEE){
                aPar[++j]=0; aLine[j]=NR; aPos[j]=i
            }
        }
    }
    END{
        while(!x){   # Tant qu'il y a eu un couple effacé ...
            x=1
            for(i in aPar){
                if(prev && !aPar[i]){       # Suppression des couples si exixtants
                    delete aPar[i]; delete aPar[k]
                    prev=0; x=0
                }else{
                    prev=aPar[i]
                }
                k=i
            }
        }
        for(i in aPar){       # Affichage du résultat
            if(aPar[i]){
                printf("Ligne %-5s car. %-5s : O\n",aLine[i],aPos[i])
            }else{
                printf("Ligne %-5s car. %-5s : F\n",aLine[i],aPos[i])
            }
        }
    }' "$@"

J'ai utilisé cette méthode : (exemple sur une ligne)
(  )  (  (  )  (  (  )  )  )  )
|  |   |  |  |   |  |  |  |  |  |
v v  v v v  v v  v v v v
1 0  1 1 0 1 1 0 0 0 0   J'attribue 1 pour une ouvrante et 0 pour une fermante
----   |  ---- |  ---- |  |  |     (et on note la position de chacune)
       v       v       v  v v   
      1        1      0  0 0   On élimine les couples directement formés (un 1 suivi d'un 0)
       |        --------   |  |   
      v                    v  v
      1                   0  0   Et on recommence jusqu'à il n'y ait plus aucun couple à enlever
       ------------------   |
                               v
                               0       ===> il y a 1 parenthèse fermante en trop quelque part (ici à la fin, lecture facile avec ce schéma). Ce quelque part est relevé à la 1ère lecture du fichier pour toutes les parenthèses trouvées dans les tableaux aPar, aLine et aPos contenant respectivement le type de parenthèse (ouvrante ou fermante), le numéro de ligne et la position dans la ligne.

Un exemple :

$ cat fichier.test
()
(
)
())
(()
)
() )
)
()((
)
((
(())
$ bash check-closed fichier.test
Ligne 4     car. 3     : F
Ligne 7     car. 4     : F
Ligne 8     car. 1     : F
Ligne 9     car. 3     : O
Ligne 11    car. 1     : O
Ligne 11    car. 2     : O
$

Qu'en pensez-vous ? Auriez-vous utilisé une autre méthode ? Si oui, laquelle ?

PS: awk est forcément imposé wink

Dernière modification par Tawal (Le 02/05/2021, à 21:46)


Le savoir n'a d’intérêt que si on le transmet.
Useless Use of Cat Award
Filenames and Pathnames in Shell: How to do it Correctly
À chaque problème sa solution, à chaque solution son moyen, si pas de moyen, toujours le problème !

Hors ligne

#2 Le 02/05/2021, à 22:01

MicP

Re : Verif. couple de parenthèses - awk

Bonjour

Plutôt que de lire caractère par caractère chaque ligne,
tu pourrais peut-être utiliser la fonction index() sur chaque ligne
pour récupérer le numéro de colonne correspondant à la position du caractère trouvé

Voir dans la page man d'awk
la description de la fonction index()
en lançant la ligne de commandes suivante :

man --pager='less -p "index\(s"' awk

Dernière modification par MicP (Le 02/05/2021, à 22:06)

Hors ligne

#3 Le 02/05/2021, à 22:26

Tawal

Re : Verif. couple de parenthèses - awk

Oui, j'avais commencé par là.
Mais, la fonction index() ne retourne que la position de la 1ère occurrence trouvée.
Et donc cela m'obligeais à manipuler la chaîne avec la fonction substr() dans une boucle pour trouver toutes les occurrences.
C'est donc plus lourd à écrire, mais je n'ai aucune idée sur les performances (plus rapide, moins de ressources etc ....).

C'est vrai que ce parcours caractère par caractère peut devenir long sur de grand fichier avec de longues lignes.
Je pense que les 2 méthodes de parcours ont chacune leurs avantages et leurs inconvénients :
Sur un long fichier avec de longues lignes et peu de parenthèse, la méthode caractère par caractère s'avère moins efficiente (de pensée).
Sur un fichier avec beaucoup de parenthèses par ligne, la méthode avec les fonctions index() et substr() peut s'avérer plus lente/lourde.

En plus, pour mettre un point de plus de mon coté, les fonctions de manipulation de chaîne de caractères ne peuvent pas s'imbriquer du genre substr(str, index(str1,car)+1).

Mais je vais quand même "réviser" ces fonctions pour voir si je n'aurais pas loupé une utilisation possible wink

Merci.


Le savoir n'a d’intérêt que si on le transmet.
Useless Use of Cat Award
Filenames and Pathnames in Shell: How to do it Correctly
À chaque problème sa solution, à chaque solution son moyen, si pas de moyen, toujours le problème !

Hors ligne

#4 Le 03/05/2021, à 09:26

Tawal

Re : Verif. couple de parenthèses - awk

La boucle de remplissage des tableaux devient :

do{
    o=index($0,OUVERTE); f=index($0,FERMEE)
    if(f>0 && (f<o || o==0)){
        aPar[++i]=0; aPos[i]=f
        sub("\\"FERMEE,"F",$0)
    }
    if(o>0 && (o<f || f==0)){
        aPar[++i]=1; aPos[i]=o
        sub("\\"OUVERTE,"O",$0)
    }
    aLine[i]=NR
}while(o || f)

C'est en effet un peu plus compliqué que la lecture caractère par caractère. Mais je pense que ça gagne en performance (difficile de vraiment comparer, il faudrait générer un grand fichier dont on connaît déjà les positions des parenthèses isolées).

C'est dingue de ne pas se remettre en question quand on croit tenir une bonne solution ! roll

Merci MicP.

Edit: Suppression du test inutile d'égalité entre les indexes :

if(o==f){
    break
}

aLine reste constant durant toute la boucle while.

Edit2: Intégration des caractères ( et ) par les variables OUVERTE et FERMEE

Dernière modification par Tawal (Le 03/05/2021, à 11:09)


Le savoir n'a d’intérêt que si on le transmet.
Useless Use of Cat Award
Filenames and Pathnames in Shell: How to do it Correctly
À chaque problème sa solution, à chaque solution son moyen, si pas de moyen, toujours le problème !

Hors ligne

#5 Le 03/05/2021, à 11:40

kamaris

Re : Verif. couple de parenthèses - awk

PROCINFO est spécifique à gawk (puisque si j'ai bien compris, tu veux justement différencier awk et gawk).

Hors ligne

#6 Le 03/05/2021, à 12:03

Tawal

Re : Verif. couple de parenthèses - awk

Oui Kamaris.

Mon but n'est pas de les différencier. Mais plutôt de savoir lequel utiliser à bon escient. Ce qui sous-entend que la différence entre awk et gawk est connue wink
Mon but est aussi de savoir résoudre l'énoncé ...

Je me suis donné l'énoncé sans savoir lequel des 2 j'allais utiliser.
Mais je me suis vite rendu compte que dans ce cas là, gawk serait plus pertinent.
Je ne dis pas que ce n'est pas possible de le faire avec seulement awk mais le code s’alourdirait pas mal je pense.

Merci.


Le savoir n'a d’intérêt que si on le transmet.
Useless Use of Cat Award
Filenames and Pathnames in Shell: How to do it Correctly
À chaque problème sa solution, à chaque solution son moyen, si pas de moyen, toujours le problème !

Hors ligne

#7 Le 03/05/2021, à 12:21

kamaris

Re : Verif. couple de parenthèses - awk

Je n'ai pas cherché à le programmer, mais à y penser rapidement, il me semble que j'aurais essayé aussi caractère par caractère, mais avec une logique différente de ton premier post.
Au lieu de tout stocker puis de traiter, on peut évacuer les couples ouvrant/fermant à la volée, pour qu'il ne reste que les orphelins en bout de course :
* Si une parenthèse fermante est trouvée alors qu'aucune parenthèse ouvrante n'est stockée, c'est une orpheline à rapporter à la fin.
* Sinon, elle ferme la dernière ouvrante stockée, et on évacue le couple.

À la fin, il ne reste que les ouvrantes et fermantes orphelines.

Hors ligne

#8 Le 03/05/2021, à 12:36

Tawal

Re : Verif. couple de parenthèses - awk

C'est une idée très intéressante et pour tout dire, c'était ma première approche.
Mais je ne m'en sortais pas entre l'exactitude de la démarche et les debugs de mon code (apprentissage de awk/gawk).
J'ai donc basculé sur 2 traitements distincts. Et même ainsi, j'ai encore eu du mal à obtenir les bons résultats correctement.
Puis, au final, en voyant mon code plutôt épuré, je me suis dit que je ne m'étais pas fourvoyé.
Mais un code épuré n'est pas forcément le plus performant ...

Je vais tenter de revoir tout ça avec cette approche.

Merci.


Le savoir n'a d’intérêt que si on le transmet.
Useless Use of Cat Award
Filenames and Pathnames in Shell: How to do it Correctly
À chaque problème sa solution, à chaque solution son moyen, si pas de moyen, toujours le problème !

Hors ligne

#9 Le 03/05/2021, à 12:54

MicP

Re : Verif. couple de parenthèses - awk

kamaris a écrit :

…on peut évacuer les couples ouvrant/fermant à la volée …

Oui, je pensais aussi à une pile LIFO

…Mais je ne m'en sortais pas entre l'exactitude de la démarche et les debugs de mon code (apprentissage de awk/gawk). …

Même chose pour moi, j'ai le cerveau en vrac ces jours-ci,
et puis de toutes façons, je ne connais pas assez bien awk et gawk pour pouvoir mettre en application toutes ces idées.

J'ai encore sur mon bureau la pile de feuilles imprimées de The AWK Programming Language
mais je ne le lis que par épisodes alors qu'avant, je l'aurai dévoré en une seule fois.

Dernière modification par MicP (Le 03/05/2021, à 13:04)

Hors ligne

#10 Le 03/05/2021, à 21:20

Tawal

Re : Verif. couple de parenthèses - awk

kamaris au # 7 a écrit :

une logique différente de ton premier post.
Au lieu de tout stocker puis de traiter, on peut évacuer les couples ouvrant/fermant à la volée, pour qu'il ne reste que les orphelins en bout de course :
* Si une parenthèse fermante est trouvée alors qu'aucune parenthèse ouvrante n'est stockée, c'est une orpheline à rapporter à la fin.
* Sinon, elle ferme la dernière ouvrante stockée, et on évacue le couple.

Une logique que j'avais abandonnée car mes neurones ne supportent pas une température supérieure à 21.3°C lol

MicP a écrit :

Oui, je pensais aussi à une pile LIFO

Une super info sur la méthode wink Ou plutôt, un mot très clair sur mon idée toute première.

Super, merci à vous deux, avec ça j'ai pas mal de "grattage à faire". Je vais m'y appliquer wink

Merci de ne pas soumettre de solution plus avancée wink big_smile


Le savoir n'a d’intérêt que si on le transmet.
Useless Use of Cat Award
Filenames and Pathnames in Shell: How to do it Correctly
À chaque problème sa solution, à chaque solution son moyen, si pas de moyen, toujours le problème !

Hors ligne

#11 Le 04/05/2021, à 09:02

Tawal

Re : Verif. couple de parenthèses - awk

Re,

Voici ce que j'ai obtenu en prenant en compte vos remarques :

#!/bin/bash

ouv="("
ferm=")"

gawk -v OUVERTE="$ouv" -v FERMEE="$ferm" '
    BEGIN{
        PROCINFO["sorted_in"]="@ind_num_asc"
        FS = ""
    }
    {
        do{
            o=index($0,OUVERTE); f=index($0,FERMEE)
            if(f>0 && (f<o || o==0)){
                aPar[++i]=0; aPos[i]=f
                sub("\\"FERMEE,"F",$0)
            }
                                # Ajout de la parenthèse trouvée dans les tableaux aPar et aPos
            if(o>0 && (o<f || f==0)){
                aPar[++i]=1; aPos[i]=o
                sub("\\"OUVERTE,"O",$0)
            }

            if(f==0 && o==0){
                break            # Sortie de la boucle si aucune parenthèse trouvée
            }

            aLine[i]=NR

            if(!aPar[i] && prev){                # Si un couple est formé (avec la dernière parenthèse trouvée et la parenthèse du dessus de la pile)
                delete aPar[i]; delete aPar[k]        # Suppression à la volée du couple formé
                                                                        
                while(!(--k in aPar)){        # Recherche de l'index de l'élément du dessus de la pile après suppression
                    if(k==0){
                        break                   # Sortie si plus d'élément dans la pile
                    }
                }

                if(k>0){                        # Si un élément est trouvé sur la pile, on le note pour le tour suivant
                    prev=aPar[k]
                }else{
                    prev=0
                }
            }else{
                prev=aPar[i]               # Si pas de couple formé, on retient la dernière parenthèse pour le tour suivant
                k=i
            }

        }while(o||f)

        for(i in aPar){
            if(aPar[i]){
                printf("Ligne %-5s car. %-5s : O\n",aLine[i],aPos[i])
            }else{
                printf("Ligne %-5s car. %-5s : F\n",aLine[i],aPos[i])
            }
        }
        delete aPar; delete aLine; delete aPos; prev=0
        
    }
#    END{
#        for(i in aPar){
#            if(aPar[i]){
#                printf("Ligne %-5s car. %-5s : O\n",aLine[i],aPos[i])
#            }else{
#                printf("Ligne %-5s car. %-5s : F\n",aLine[i],aPos[i])
#            }
#        }
#        delete aPar; delete aLine; delete aPos; prev=0
#    }
' "$@"

Tel que le code est commenté, les parenthèses doivent être refermées sur la ligne.
Pour "checker" au travers du fichier entier (une parenthèse pouvant se refermer sur une autre ligne), il faut dé-commenter le bloc END et commenter la dernière boucle for et la ligne delete aPar ... du corps du programme.
Donc ça ouvre pas mal de possibilité de "gestion", mais c'est une autre étape wink

Qu'en pensez-vous ? Je n'arrive pas à faire plus concis (du point de vue de la méthode), mais j'ai le sentiment qu'il est possible de faire mieux en réorganisant un peu et peaufinant les tests.

En tous cas, merci à vous, ça ne ressemble plus trop au code du #1 big_smile


Le savoir n'a d’intérêt que si on le transmet.
Useless Use of Cat Award
Filenames and Pathnames in Shell: How to do it Correctly
À chaque problème sa solution, à chaque solution son moyen, si pas de moyen, toujours le problème !

Hors ligne

#12 Le 04/05/2021, à 11:34

kamaris

Re : Verif. couple de parenthèses - awk

Que tout ça est compliqué ! big_smile
Voilà à quoi je pensais perso, dans ce que je disais en #7 :

#!/bin/bash

gawk -vo='(' -vf=')' '
  BEGIN{ FS="" }

  BEGINFILE{ m=n=0; delete os; delete fs }

  {
    for (i=1; i<=NF; i++)
    {
      if ($i==o) { os[m, 0]=FNR; os[m, 1]=i; m++ }
      else if ($i==f)
      {
        if (m==0) { fs[n, 0]=FNR; fs[n, 1]=i; n++ }
        else { m--; delete os[m, 0]; delete os[m, 1] }
      }
    }
  }

  ENDFILE{
    printf ("\n*** Fichier \"%s\" ***\n\n", FILENAME)
    printf ("%s\n", "Parenthèses ouvrantes orphelines :")
    for (i=0; i<m; i++) printf ("ligne %d, caractère %d\n", os[i, 0], os[i, 1])

    printf ("\n%s\n", "Parenthèses fermantes orphelines :")
    for (i=0; i<n; i++) printf ("ligne %d, caractère %d\n", fs[i, 0], fs[i, 1])
  }
' "$@"

C'est du gawk, surtout à cause de l'utilisation de la chaine nulle comme séparateur de champs (sinon, il faut probablement utiliser index()).
Pour l'aspect multi-fichiers, j'ai fait du gawk par facilité, mais ça pourrait évidemment être porté en awk.

Dernière modification par kamaris (Le 04/05/2021, à 12:25)

Hors ligne

#13 Le 04/05/2021, à 15:11

Tawal

Re : Verif. couple de parenthèses - awk

Oh que c'est tout simple ça ! lol

J'ai de quoi rougir roll
Je vais tenter d'intégrer la recherche des parenthèses par leur indexe car je pense que ça gagne en performance surtout s'il y a beaucoup de texte dans les parenthèses.

Merci

Edit: C'était pas trop dur smile
Il suffit d'intégrer TA logique dans ce que j'avais fait au #4.
Le corps du programme (le reste ne change pas) :

        do {
            ind_o=index($0,o); ind_f=index($0,f)

            if ( ind_o>0 && (ind_o<ind_f || ind_f==0) ) {
                os[m, 0]=FNR; os[m, 1]=ind_o
                m++
                sub("\\"o,"O",$0)
            }

            if ( ind_f>0 && (ind_f<ind_o || ind_o==0) ) {
                if (m==0) {
                    fs[n, 0]=FNR; fs[n, 1]=ind_f
                    n++
                } else {
                    m--
                    delete os[m, 0]; delete os[m, 1]
                }
                sub("\\"f,"F",$0)
            }
        } while (ind_o||ind_f)

Dernière modification par Tawal (Le 04/05/2021, à 16:21)


Le savoir n'a d’intérêt que si on le transmet.
Useless Use of Cat Award
Filenames and Pathnames in Shell: How to do it Correctly
À chaque problème sa solution, à chaque solution son moyen, si pas de moyen, toujours le problème !

Hors ligne

#14 Le 04/05/2021, à 16:21

kamaris

Re : Verif. couple de parenthèses - awk

Peut-être qu'avec index() c'est plus rapide oui, mais je ne parierais pas : ça ne recherche pas les parenthèses par leur index (elles n'en ont pas à priori), ça renvoie l'index des parenthèses.
Je suppose qu'au final, c'est aussi une recherche caractère par caractère qui est faite.

On peut supprimer les delete aussi dans le code ci-dessus : je les ai mis pour être plus propre, et pour écrire du code plus facile à maintenir ou faire évoluer, mais toute l'info dont on a besoin en l'occurrence est dans m et n.

EDIT : on s'est croisés !

Dernière modification par kamaris (Le 04/05/2021, à 16:22)

Hors ligne

#15 Le 04/05/2021, à 17:00

Tawal

Re : Verif. couple de parenthèses - awk

kamaris a écrit :

ça renvoie l'index des parenthèses.
Je suppose qu'au final, c'est aussi une recherche caractère par caractère qui est faite.

Très pertinent comme réflexion smile wink

kamaris a écrit :

On peut supprimer les delete aussi dans le code

Oui car il y a "over-write" sur les tableaux os.


Le savoir n'a d’intérêt que si on le transmet.
Useless Use of Cat Award
Filenames and Pathnames in Shell: How to do it Correctly
À chaque problème sa solution, à chaque solution son moyen, si pas de moyen, toujours le problème !

Hors ligne