Discussion :

[Basile le disciple]

Mesdames Messieurs bonsoooir,

J’ai essayé de faire une calculatrice gérant les parenthèses à partir de ce super tuto.
Mais il y a une chose que je n’ai pas comprise : c’est l’utilité de la procedure traiter_sans_parentheses :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
 
procedure arbre.Remplit(courant: noeud; s: string; signe1, signe2: char);
var g1, d1: string;
  sig1: char;
 
  function nb_elems(s: string; var g, d: string; s1, s2: char; var sig: char): integer;
  var trouve: boolean;
    p, nb: integer;
  begin // on extrait la partie gauche et droite, séparées par s1 ou s2
    p := length(s) + 1; nb := 0; // en faisant attention aux parenthèses, s'il y en a
    repeat
      dec(p);
      if s[p] = '(' then dec(nb);
      if s[p] = ')' then inc(nb);
      trouve := (nb = 0) and ((s[p] = s1) or (s[p] = s2));
    until (p = 1) or (trouve);
    if p > 1 then // deux ou plusieurs elements; mais dans un arbre binaire il y en a 2
    begin
      d := copy(s, p + 1, length(s));
      g := copy(s, 1, p - 1);
      sig := s[p];
      nb_elems := 2;
    end
    else // un seul élément
    begin
      d := s;
      g := '';
      sig := #0;
      nb_elems := 1;
    end;
  end;
 
  procedure traiter_sans_parentheses(courant: noeud; s: string; signe1, signe2: char);
  var g2, d2: string;
       sig2: char;
  begin
    if nb_elems(s, g2, d2, signe1, signe2, sig2) = 2 then // deux termes ou plus
    begin
      courant.FilsDroit := noeud.create;
      traiter_sans_parentheses(courant.FilsDroit, d2, '*', '/');
      courant.op := sig2;
      courant.FilsGauche := noeud.create;
      traiter_sans_parentheses(courant.FilsDroit, g2, signe1, signe2);
    end
    else
      if nb_elems(s, g2, d2, '*', '/', sig2) = 2 then
        traiter_sans_parentheses(courant, s, '*', '/')
      else
      begin
        courant.op := 'c'; // c pour "chiffre"
        courant.valeur := strToInt(s);
      end;
  end;
 
begin
  if nb_elems(s, g1, d1, signe1, signe2, sig1) = 2 then // deux termes ou plus
  begin
    courant.FilsDroit := noeud.create;
    remplit(courant.FilsDroit, d1, '*', '/');
    courant.op := sig1;
    courant.FilsGauche := noeud.create;
    remplit(courant.FilsGauche, g1, signe1, signe2);
  end
  else // un seul terme
    if nb_elems(s, g1, d1, '*', '/', sig1) = 2 then // un terme pour l'addition mais
      remplit(courant, s, '*', '/') // plusieurs pour la multiplication : 2*3*(-5)
    else
      if d1[1] = '(' then // ou bien une seule parenthèse, ex : (2+3)
      begin
        courant.op := '(';
        courant.FilsDroit := noeud.create;
        d1 := copy(d1, 2, length(d1) - 2); // on supprime les parenthèses
        Remplit(courant.FilsDroit, d1, '+', '-')
      end
      else // ou bien un seul nombre
        traiter_sans_parentheses(courant, d1, '+', '-');  // --->>> je ne comprends pas ici
end;

En effet, la procédure remplit gère déjà si un des membres contient plusieurs membres, alors à quoi sert-elle ? J’avais mis à la place de

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

traiter_sans_parentheses(courant, d1, '+', '-');

ce bout de code

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
Courant.op:='c';
if d <> '' then Courant.Valeur:=strtoInt(d1) else Courant.Valeur:=0;

Après avoir fait plein d'essais, cela marche aussi bien. Cela m’étonnerait que les auteurs se soient amusés à créer une procedure pour rien… Qu’est-ce que je rate ??

[Papy214]

Son utilité vient de la récursivité qu'elle implémente.
Selon la "profondeur" du noeud et dans certains cas elle s'appelle elle-même.

Après , pour savoir très exactement son utilité, il faudrait étudier le code de plus près.

[Basile le disciple]

Son utilité vient de la récursivité qu'elle implémente.

Bas oui, mais remplit gère déjà la récursivité...

Après , pour savoir très exactement son utilité, il faudrait étudier le code de plus près.

C’est vrai. Je vais peut-être expliquer (ce que j’ai compris) pour que ce soit plus compréhensible(ou pas) :

La procedure Remplit à pour but de transformer une chaîne contenant des opérations (+ ; - ; / ;* ; ()) en un arbre binaire, on admettra que la chaîne est valide d’un point de vue syntaxique(après, il y a un automate).

La fonction nb_elems trouve si il y a 1 ou plusieurs membres dans une chaine en partant de la droite, si oui, elle renvoie 2, le membre de gauche (g1), le membre de droite(d1) et l’opérateur(sig1).

Ex :
-si 1 ou (1+1) -> la fonction renvoie 1 et d1 prend la chaine
-si 1+2-> la fonction renvoie 2 ;g1 =1 ;d1->2 ;sig1->+
-si 4-5+4-> la fonction renvoie 2 ;g1=4-5 ;d1=4 ;sig1=+

Donc, dans remplit, on regarde s’il y a 2 membres,

si oui, le fil droit du nœud est créé, et on rappelle remplit avec les opérateurs * ou / pour voir si le membre de droite contient 2 membre avec ces opérateurs (pour respecter la règle des priorités). Le nœud prend ensuite l’opérateur trouvé. Puis on créé le fil gauche, et on rappelle remplit avec les 2 opérateurs qui ont été appelés dans remplit (signe1, signe2), pour voir s’il reste des membres dans le membre de gauche.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
 if nb_elems(s, g2, d2, signe1, signe2, sig2) = 2 then // deux termes ou plus
    begin
      courant.FilsDroit := noeud.create;
      traiter_sans_parentheses(courant.FilsDroit, d2, '*', '/');
      courant.op := sig2;
      courant.FilsGauche := noeud.create;
      traiter_sans_parentheses(courant.FilsDroit, g2, signe1, signe2);
    end

Si non,

-au cas où signe1 et signe2 étaient + et -, on réessaye avec * et /, s’ils y sont, on réappelle Remplit

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
   else
      if nb_elems(s, g2, d2, '*', '/', sig2) = 2 then
        traiter_sans_parentheses(courant, s, '*', '/')

Sinon, s’il y a une parenthèse ouvrante au début, on l’enlève avec la parenthèse fermante, puis on réappelle remplit avec + et –

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
   else
      if d1[1] = '(' then // ou bien une seule parenthèse, ex : (2+3)
      begin
        courant.op := '(';
        courant.FilsDroit := noeud.create;
        d1 := copy(d1, 2, length(d1) - 2); // on supprime les parenthèses
        Remplit(courant.FilsDroit, d1, '+', '-')
      end

Sinon (et c’est là que je ne comprends pas), les auteurs du cours appellent la procedure Traiter_sans_parentheses pour voir s’il y a plusieurs membres, or on a déjà fait ces essais, je l’ai donc remplacée par

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
Courant.op:='c';
if d <> '' then Courant.Valeur:=strtoInt(d1) else Courant.Valeur:=0;

En effet, à ce stade, la chaîne ne peut être qu’un nombre. C’est même marqué en commentaire dans le cours...
Quelqu’un voit à quoi sert cette procédure?