243 lines
8.1 KiB
Ada
Executable file
243 lines
8.1 KiB
Ada
Executable file
with Piles;
|
||
|
||
with Ada.Text_IO; use Ada.Text_IO;
|
||
with Ada.Integer_Text_IO; use Ada.Integer_Text_IO;
|
||
|
||
|
||
procedure Parenthesage is
|
||
|
||
|
||
-- L'indice dans la chaîne Meule de l'élément Aiguille.
|
||
-- Si l'Aiguille n'est pas dans la Meule, on retourne Meule'Last + 1.
|
||
Function Index (Meule : in String; Aiguille: Character) return Integer with
|
||
Post => Meule'First <= Index'Result and then Index'Result <= Meule'Last + 1
|
||
and then (Index'Result > Meule'Last or else Meule (Index'Result) = Aiguille)
|
||
is
|
||
begin
|
||
|
||
for i in Meule'First..Meule'Last loop
|
||
if Aiguille = Meule(i) then
|
||
return i;
|
||
end if;
|
||
end loop;
|
||
|
||
return Meule'Last + 1;
|
||
|
||
end Index;
|
||
|
||
|
||
-- Programme de test de Index.
|
||
procedure Tester_Index is
|
||
ABCDEF : constant String := "abcdef";
|
||
begin
|
||
pragma Assert (1 = Index (ABCDEF, 'a'));
|
||
pragma Assert (3 = Index (ABCDEF, 'c'));
|
||
pragma Assert (6 = Index (ABCDEF, 'f'));
|
||
pragma Assert (7 = Index (ABCDEF, 'z'));
|
||
pragma Assert (4 = Index (ABCDEF (1..3), 'z'));
|
||
pragma Assert (3 = Index (ABCDEF (3..5), 'c'));
|
||
pragma Assert (5 = Index (ABCDEF (3..5), 'e'));
|
||
pragma Assert (6 = Index (ABCDEF (3..5), 'a'));
|
||
pragma Assert (6 = Index (ABCDEF (3..5), 'g'));
|
||
end;
|
||
|
||
|
||
-- Vérifier les bon parenthésage d'une Chaîne (D). Le sous-programme
|
||
-- indique si le parenthésage est bon ou non (Correct : R) et dans le cas
|
||
-- où il n'est pas correct, l'indice (Indice_Erreur : R) du symbole qui
|
||
-- n'est pas appairé (symbole ouvrant ou fermant).
|
||
--
|
||
-- Exemples
|
||
-- "[({})]" -> Correct
|
||
-- "]" -> Non Correct et Indice_Erreur = 1
|
||
-- "((()" -> Non Correct et Indice_Erreur = 2
|
||
--
|
||
|
||
|
||
procedure Verifier_Parenthesage (Chaine: in String ; Correct : out Boolean ; Indice_Erreur : out Integer) is
|
||
|
||
Ouvrants : Constant String := "([{";
|
||
Fermants : Constant String := ")]}";
|
||
|
||
type T_container is record
|
||
char : Character;
|
||
index : Integer;
|
||
end record;
|
||
|
||
package Pile_paranthese is
|
||
new Piles (Capacite => 100, T_Element => T_container);
|
||
use Pile_paranthese;
|
||
|
||
pile : T_Pile;
|
||
elm : T_container;
|
||
|
||
begin
|
||
|
||
-- on initialise la pile
|
||
Initialiser(pile);
|
||
|
||
-- si la chaine est vide c'est correct
|
||
if Chaine = "" then
|
||
Correct := True;
|
||
else -- sinon on proc<6F>de <20> la v<>rification
|
||
|
||
-- si le premier caract<63>re est un Fermant on s'arr<72>te
|
||
if Index(Fermants, Chaine(Chaine'First)) <= Fermants'Last then
|
||
Correct := False;
|
||
Indice_Erreur := Chaine'First;
|
||
else -- sinon on continue
|
||
|
||
-- on commence la v<>rification pour les prochains caract<63>res
|
||
for i in Chaine'First..Chaine'Last loop
|
||
|
||
-- <20> chaque tour de boucle on actualise notre element
|
||
elm.char := Chaine(i);
|
||
elm.index := i;
|
||
|
||
-- si le caract<63>re est un Ouvrant, on empile
|
||
if Index(Ouvrants, elm.char) <= Ouvrants'Last then
|
||
Empiler(pile, elm);
|
||
|
||
-- si le caract<63>re est un Ferment, on cherche son correspondant
|
||
elsif Index(Fermants, elm.char) <= Fermants'Last then
|
||
|
||
-- si on ne peut pas chercher de correspondant, la chaine n'est pas correcte
|
||
if Est_Vide(Pile) then
|
||
Correct := False;
|
||
Indice_Erreur := elm.index;
|
||
return;
|
||
end if;
|
||
|
||
-- on cherche le correspondant
|
||
for j in Ouvrants'First..Ouvrants'Last loop
|
||
|
||
-- si on trouve le correspondant on continue la proc<6F>dure de v<>rification (pour les prochains caract<63>res)
|
||
if Ouvrants(j) = Sommet(Pile).char and Fermants(j) = elm.char then
|
||
Depiler(Pile);
|
||
Correct := True;
|
||
exit;
|
||
else -- sinon la chaine n'est pas correcte
|
||
Correct := false;
|
||
Indice_Erreur := elm.index;
|
||
if j = Ouvrants'Last then
|
||
return;
|
||
end if;
|
||
end if;
|
||
|
||
end loop;
|
||
|
||
end if;
|
||
|
||
end loop;
|
||
|
||
end if;
|
||
|
||
if not Est_Vide(pile) then
|
||
Correct := false;
|
||
Indice_Erreur := Sommet(pile).index;
|
||
end if;
|
||
|
||
end if;
|
||
|
||
end Verifier_Parenthesage;
|
||
|
||
|
||
-- Programme de test de Verifier_Parenthesage
|
||
procedure Tester_Verifier_Parenthesage is
|
||
Exemple1 : constant String(1..2) := "{}";
|
||
Exemple2 : constant String(11..18) := "]{[(X)]}";
|
||
|
||
Indice : Integer; -- R<>ultat de ... XXX
|
||
Correct : Boolean;
|
||
begin
|
||
Verifier_Parenthesage ("(a < b)", Correct, Indice);
|
||
pragma Assert (Correct);
|
||
|
||
Verifier_Parenthesage ("([{a}])", Correct, Indice);
|
||
pragma Assert (Correct);
|
||
|
||
Verifier_Parenthesage ("(][{a}])", Correct, Indice);
|
||
pragma Assert (not Correct);
|
||
put(Indice); new_line;
|
||
pragma Assert (Indice = 2);
|
||
|
||
Verifier_Parenthesage ("]([{a}])", Correct, Indice);
|
||
pragma Assert (not Correct);
|
||
put(Indice); new_line;
|
||
pragma Assert (Indice = 1);
|
||
|
||
Verifier_Parenthesage ("([{}])}", Correct, Indice);
|
||
pragma Assert (not Correct);
|
||
put(Indice); new_line;
|
||
pragma Assert (Indice = 7);
|
||
|
||
Verifier_Parenthesage ("([{", Correct, Indice);
|
||
pragma Assert (not Correct);
|
||
put(Indice); new_line;
|
||
pragma Assert (Indice = 3);
|
||
|
||
Verifier_Parenthesage ("([{}]", Correct, Indice);
|
||
pragma Assert (not Correct);
|
||
put(Indice); new_line;
|
||
pragma Assert (Indice = 1);
|
||
|
||
Verifier_Parenthesage ("", Correct, Indice);
|
||
pragma Assert (Correct);
|
||
|
||
Verifier_Parenthesage (Exemple1, Correct, Indice);
|
||
pragma Assert (Correct);
|
||
|
||
Verifier_Parenthesage (Exemple2, Correct, Indice);
|
||
pragma Assert (not Correct);
|
||
put(Indice); new_line;
|
||
pragma Assert (Indice = 11);
|
||
|
||
Verifier_Parenthesage (Exemple2(12..18), Correct, Indice);
|
||
pragma Assert (Correct);
|
||
|
||
Verifier_Parenthesage (Exemple2(12..15), Correct, Indice);
|
||
pragma Assert (not Correct);
|
||
put(Indice); new_line;
|
||
pragma Assert (Indice = 14);
|
||
|
||
Verifier_Parenthesage ("([{}]", Correct, Indice);
|
||
pragma Assert (not Correct);
|
||
put(Indice); new_line;
|
||
pragma Assert (Indice = 1);
|
||
|
||
Verifier_Parenthesage ("f(x) = 4(a + b) - [ 6 { 56 } ]", Correct, Indice);
|
||
pragma Assert (Correct);
|
||
|
||
Verifier_Parenthesage("f(x)) = 4(a + b) - [ 6 { 56 } ]", Correct, Indice);
|
||
pragma Assert (not Correct);
|
||
put(Indice); new_line;
|
||
pragma Assert (Indice = 5);
|
||
|
||
Verifier_Parenthesage("f(x))) = 4(a + b) - [ 6 { 56 } ]", Correct, Indice);
|
||
pragma Assert (not Correct);
|
||
put(Indice); new_line;
|
||
pragma Assert (Indice = 5);
|
||
|
||
Verifier_Parenthesage("f((x) = 4(a + b) - [ 6 { 56 } ]", Correct, Indice);
|
||
pragma Assert (not Correct);
|
||
put(Indice); new_line;
|
||
pragma Assert (Indice = 2);
|
||
|
||
Verifier_Parenthesage("f(((x) = 4(a + b) - [ 6 { 56 } ]", Correct, Indice);
|
||
pragma Assert (not Correct);
|
||
put(Indice); new_line;
|
||
pragma Assert (Indice = 3);
|
||
|
||
Verifier_Parenthesage ("( ((())) [{}{}] ) [[]] {}", Correct, Indice);
|
||
pragma Assert (Correct);
|
||
|
||
Verifier_Parenthesage ("((a a(aa(szegzse)z))ffsse [dz{dz}efsefse{zd}]fse)f [sf[d]zzd]sefs {qzd}", Correct, Indice);
|
||
pragma Assert (Correct);
|
||
|
||
end Tester_Verifier_Parenthesage;
|
||
|
||
begin
|
||
Tester_Index;
|
||
Tester_Verifier_Parenthesage;
|
||
end Parenthesage;
|