Représenter, parcourir et transformer des informations textuelles

Fiche pédagogique du chapitre

Objectifs d’apprentissage

À la fin de ce chapitre, l’étudiant devra être capable de :

• définir une chaîne de caractères et distinguer une chaîne d’un caractère isolé ;
• déterminer la longueur d’une chaîne et repérer un caractère à l’aide de son indice ;
• lire et afficher correctement une information textuelle ;
• concaténer, comparer et extraire des portions de chaînes ;
• convertir un texte en majuscules ou en minuscules ;
• parcourir une chaîne caractère par caractère ;
• compter des caractères ou des voyelles ;
• rechercher et remplacer un caractère ;
• supprimer les espaces d’une chaîne ;
• vérifier si un mot ou une phrase est un palindrome ;
• inverser une chaîne et compter ses mots ;
• valider un identifiant selon des règles données ;
• contrôler un mot de passe à l’aide de critères simples.

Prérequis

• connaître les variables, les constantes et les types de données simples ;
• maîtriser les structures conditionnelles et répétitives ;
• savoir utiliser les tableaux à une dimension ;
• savoir construire une expression logique ;
• savoir tracer manuellement l’exécution d’un algorithme.

Plan du chapitre

10.1 Définition

10.2 Opérations élémentaires

10.3 Parcours d’une chaîne

10.4 Algorithmes classiques

Applications, travaux dirigés, corrigés et synthèse

Organisation pédagogique indicative

Introduction aux chaînes de caractères

Les programmes ne manipulent pas uniquement des nombres. Ils traitent aussi des noms, des adresses, des messages, des identifiants, des mots de passe, des commandes, des réponses à des formulaires ou encore le contenu de fichiers. Toutes ces informations sont représentées sous forme de chaînes de caractères.

Une chaîne peut être considérée comme une suite ordonnée de caractères. Chaque caractère possède une position, appelée indice. Les structures répétitives permettent de visiter successivement les caractères afin de les compter, les comparer, les rechercher ou les transformer.

Les chaînes ressemblent aux tableaux à une dimension, mais elles possèdent des opérations propres au texte : concaténation, extraction, conversion de casse et comparaison lexicographique. Selon le langage utilisé, une chaîne peut être modifiable ou immuable. En pseudo-code, nous privilégierons des opérations indépendantes du langage.

10.1 Définition

10.1.1 Chaîne de caractères

Une chaîne de caractères est une suite finie et ordonnée de caractères. Elle peut contenir des lettres, des chiffres, des espaces, des signes de ponctuation et des symboles. Une chaîne est généralement placée entre guillemets afin de la distinguer du nom d’une variable.

10.1.2 Caractère et chaîne

Un caractère représente une seule unité textuelle, par exemple 'A', '7' ou '?'. Une chaîne peut contenir zéro, un ou plusieurs caractères. La distinction est importante, car certaines opérations attendent un caractère et d’autres une chaîne.

10.1.3 Longueur

La longueur d’une chaîne est le nombre de caractères qu’elle contient. Les espaces et les signes de ponctuation comptent comme des caractères. La fonction Longueur(chaine) renvoie un entier supérieur ou égal à zéro.

Calcul de la longueur

Une chaîne vide possède une longueur nulle. Avant d’accéder au premier ou au dernier caractère, il faut donc vérifier que sa longueur est strictement positive.

10.1.4 Caractère individuel

Un caractère individuel peut être lu à partir de sa position. Cette opération permet d’examiner la première lettre d’un nom, le dernier caractère d’une phrase ou chaque symbole d’un identifiant.

10.1.5 Indice d’un caractère

L’indice indique la position d’un caractère dans la chaîne. Avec la convention adoptée, le premier caractère a l’indice 1 et le dernier a l’indice Longueur(chaine).

Dans la chaîne « ALGORITHME », le caractère d’indice 4 est O. La position d’une valeur ne doit pas être confondue avec la valeur elle-même : l’indice 4 est un entier, tandis que 'O' est un caractère.

10.1.6 Sous-chaîne

Une sous-chaîne est une portion continue d’une chaîne. Elle est définie par une position de départ et une longueur, ou par deux bornes selon le langage. Par exemple, Extraire("ALGORITHME", 1, 4) renvoie "ALGO".

10.1.7 Représentation et encodage

Chaque caractère est représenté en mémoire par un code numérique. Les systèmes modernes utilisent généralement Unicode, qui permet de représenter les lettres accentuées, l’arabe, les symboles scientifiques et de nombreuses écritures. L’algorithme doit éviter de supposer que tous les caractères sont limités à l’alphabet anglais.

Dans une première approche, nous considérerons qu’un accès à chaine[i] fournit un caractère logique. Dans certains langages, les emojis ou certains symboles composés peuvent nécessiter un traitement particulier ; cette question dépend de l’encodage et dépasse le niveau introductif du chapitre.

10.2 Opérations élémentaires

10.2.1 Lecture et affichage

L’instruction Lire permet de saisir une chaîne et l’instruction Écrire permet de l’afficher. La saisie peut concerner un mot unique ou une ligne complète. Une lecture limitée au premier espace ne convient pas pour un nom complet ou une phrase.

10.2.2 Concaténation

La concaténation assemble plusieurs chaînes pour former une nouvelle chaîne. Elle est souvent notée avec l’opérateur + ou avec une fonction Concatener. Elle ne réalise aucune addition numérique.

Lorsque le résultat est construit dans une boucle, il faut initialiser la chaîne résultat à la chaîne vide avant la première concaténation.

10.2.3 Comparaison

Deux chaînes peuvent être comparées pour vérifier leur égalité ou pour établir un ordre. La comparaison d’égalité exige généralement que les caractères soient identiques et placés dans le même ordre. Elle peut être sensible à la casse.

L’ordre lexicographique compare les caractères de gauche à droite. Dès qu’une différence apparaît, l’ordre des caractères détermine le résultat. Pour classer des noms de manière conviviale, il est recommandé de normaliser la casse et de tenir compte des accents selon les règles du langage.

10.2.4 Extraction

L’extraction récupère une portion d’une chaîne sans nécessairement modifier la chaîne d’origine. Elle peut servir à isoler un préfixe, un suffixe, une année ou une partie d’un code.

10.2.5 Conversion en majuscules ou minuscules

Les fonctions Majuscule et Minuscule produisent une version normalisée du texte. Elles sont utiles pour comparer des réponses sans tenir compte de la casse, compter les voyelles ou présenter un nom de manière uniforme.

La conversion de casse ne supprime pas les espaces et ne corrige pas l’orthographe. Elle transforme seulement les lettres qui possèdent une variante majuscule ou minuscule.

10.2.6 Opérations utiles complémentaires

10.3 Parcours d’une chaîne

10.3.1 Principe général du parcours

Parcourir une chaîne consiste à examiner ses caractères dans un ordre déterminé. Le parcours complet de gauche à droite utilise une boucle allant de 1 à la longueur de la chaîne.

La variable i représente la position courante. La valeur chaine[i] est le caractère traité. Avant la boucle, il faut initialiser les compteurs, indicateurs ou chaînes résultats utilisés par le traitement.

10.3.2 Compter les caractères

La longueur fournit directement le nombre total de caractères. Un parcours devient utile lorsque l’on souhaite compter seulement les caractères répondant à une condition, par exemple les lettres, les chiffres ou les espaces.

Pour la chaîne « Salle B12 », le résultat est 2, car seuls les caractères '1' et '2' sont des chiffres.

10.3.3 Compter les voyelles

Pour compter les voyelles, on normalise d’abord la casse afin d’éviter de tester séparément les majuscules et les minuscules. On parcourt ensuite la chaîne et on incrémente un compteur lorsque le caractère appartient à l’ensemble des voyelles.

10.3.4 Rechercher un caractère

Une recherche peut répondre à plusieurs besoins : savoir si le caractère existe, trouver sa première position, sa dernière position ou toutes ses occurrences. Le traitement doit préciser le résultat attendu.

La valeur 0 sert ici de convention pour signifier « non trouvé », puisque les indices valides commencent à 1. Dans un langage utilisant des indices à partir de 0, une autre valeur spéciale, souvent -1, est fréquemment utilisée.

10.3.5 Remplacer un caractère

Le remplacement consiste à produire une chaîne dans laquelle chaque occurrence d’un caractère est remplacée par un autre. Lorsque les chaînes sont immuables, on construit progressivement une nouvelle chaîne.

Exemple : remplacer 'a' par '*' dans « banane » produit « b*n*ne ». La chaîne originale peut rester inchangée.

10.3.6 Supprimer les espaces

Pour supprimer tous les caractères espace, on copie uniquement les caractères différents de l’espace dans une chaîne résultat. Il faut distinguer cette opération du nettoyage des espaces inutiles, qui conserverait un seul espace entre les mots.

10.3.7 Parcours inverse

Le parcours inverse commence au dernier caractère et se termine au premier. Il sert notamment à inverser une chaîne ou à comparer les extrémités d’un mot.

10.3.8 Invariants et erreurs fréquentes

10.4 Algorithmes classiques

10.4.1 Vérification d’un palindrome

Un palindrome est une chaîne qui se lit de la même manière de gauche à droite et de droite à gauche. Des exemples simples sont « radar », « kayak » et « elle ». Une vérification stricte tient compte de la casse et des espaces ; une vérification normalisée peut les ignorer.

Méthode 1 : comparer les caractères symétriques. Le premier caractère est comparé au dernier, le deuxième à l’avant-dernier, et ainsi de suite jusqu’au milieu.

10.4.2 Inversion d’une chaîne

Inverser une chaîne consiste à produire une nouvelle chaîne contenant les caractères dans l’ordre opposé. La méthode la plus directe parcourt la chaîne de la fin vers le début.

10.4.3 Comptage des mots

Une définition simple considère qu’un mot est une suite non vide de caractères séparée par un ou plusieurs espaces. Pour gérer plusieurs espaces successifs, on compte le passage d’un espace vers un caractère non espace.

10.4.4 Validation d’un identifiant

Un identifiant peut être soumis à des règles simples : longueur minimale, premier caractère alphabétique, caractères suivants limités aux lettres, chiffres et trait de soulignement. Les règles exactes doivent être définies avant l’écriture de l’algorithme.

• la longueur doit être comprise entre 3 et 20 caractères ;
• le premier caractère doit être une lettre ;
• les autres caractères doivent être des lettres, des chiffres ou le caractère _ ;
• les espaces et les signes de ponctuation sont interdits.

10.4.5 Vérification d’un mot de passe

La validation d’un mot de passe consiste à vérifier des règles de forme. Elle ne mesure pas à elle seule la sécurité réelle du mot de passe. Pour l’exercice, nous imposons une longueur minimale et la présence de plusieurs catégories de caractères.

• au moins 8 caractères ;
• au moins une lettre majuscule ;
• au moins une lettre minuscule ;
• au moins un chiffre ;
• aucun espace.

Applications guidées

Application 1 — Normaliser une réponse utilisateur

On souhaite accepter les réponses « oui », « Oui », « OUI » ou toute autre combinaison de casse. La solution convertit la réponse en minuscules avant la comparaison.

Jeux d’essai : « OUI » donne une confirmation ; « Oui » donne une confirmation ; « non » donne une réponse non reconnue ; la chaîne vide doit être refusée.

Application 2 — Compter les occurrences d’un caractère

L’algorithme compte le nombre de fois qu’un caractère cible apparaît dans un texte. La comparaison peut être sensible ou insensible à la casse selon les besoins.

Application 3 — Nettoyer les espaces multiples

On souhaite supprimer les espaces au début et à la fin, puis conserver un seul espace entre deux mots. La variable espacePrecedent mémorise si le dernier caractère ajouté était un espace.

Pour l’entrée «   cours  d algorithmique   », le résultat devient « cours d algorithmique ».

Application 4 — Extraire le domaine d’une adresse électronique

À partir d’une adresse contenant exactement un caractère @, on cherche la position de @ puis on extrait la partie située après ce caractère.

Application 5 — Masquer une partie d’un identifiant

Pour protéger une information lors de l’affichage, on peut conserver les quatre derniers caractères et remplacer les précédents par des astérisques.

Exemple : « AB12345678 » devient « ******5678 ». Ce masquage est destiné à l’affichage ; il ne remplace pas la protection et le stockage sécurisé des données.

Travaux dirigés

Exercice 1 — Longueur et indices

Pour la chaîne « programmation », donner sa longueur, son premier caractère, son dernier caractère et les caractères d’indices 4 et 8. Indiquer les indices invalides parmi 0, 1, 13, 14 et 20.

Exercice 2 — Comparaison normalisée

Écrire un algorithme qui lit deux mots et indique s’ils sont identiques sans tenir compte des majuscules et des minuscules.

Exercice 3 — Compter des catégories

Écrire un algorithme qui lit une chaîne et affiche séparément le nombre de lettres, de chiffres, d’espaces et d’autres caractères.

Exercice 4 — Première et dernière occurrence

Écrire un algorithme qui recherche la première et la dernière position d’un caractère dans une chaîne. Afficher un message lorsque le caractère est absent.

Exercice 5 — Suppression ciblée

Écrire un algorithme qui supprime toutes les occurrences d’un caractère choisi par l’utilisateur.

Exercice 6 — Palindrome normalisé

Écrire un algorithme qui vérifie si une phrase est un palindrome en ignorant les espaces et la casse.

Exercice 7 — Validation d’un code étudiant

Un code étudiant doit respecter la forme deux lettres majuscules suivies de six chiffres. Écrire l’algorithme de validation et proposer au moins cinq jeux d’essai.

Exercice 8 — Fréquence des voyelles

Écrire un algorithme qui compte séparément les occurrences de a, e, i, o, u et y dans une chaîne, sans tenir compte de la casse.

Exercice 9 — Initiales d’un nom complet

Écrire un algorithme qui extrait les initiales d’un nom complet. Les mots peuvent être séparés par plusieurs espaces. Exemple : « Ahmed Ben Ali » produit « ABA ».

Exercice 10 — Mot le plus long

Écrire un algorithme qui détermine le mot le plus long d’une phrase. En cas d’égalité, conserver le premier mot rencontré.

Corrigés indicatifs

Corrigé 1 — Longueur et indices

La chaîne « programmation » contient 13 caractères. Le premier est 'p', le dernier est 'n', le caractère d’indice 4 est 'g' et celui d’indice 8 est 'm'. Les indices valides sont compris entre 1 et 13 ; 0, 14 et 20 sont donc invalides.

Corrigé 2 — Comparaison normalisée

Corrigé 3 — Compter des catégories

Corrigé 4 — Première et dernière occurrence

Corrigé 5 — Suppression ciblée

Corrigé 6 — Palindrome normalisé

Corrigé 7 — Validation d’un code étudiant

Corrigé 8 — Fréquence des voyelles

On initialise six compteurs à zéro, on convertit le texte en minuscules, puis une structure Selon incrémente le compteur associé au caractère courant.

Corrigé 9 — Initiales

Corrigé 10 — Mot le plus long

Une solution simple ajoute un espace artificiel à la fin de la phrase afin de traiter le dernier mot comme les autres. La variable motCourant est construite caractère par caractère. Lorsqu’un espace est rencontré, sa longueur est comparée à celle de motMax.

Jeux d’essai recommandés

Les algorithmes textuels doivent être testés sur des entrées variées. Une chaîne visuellement simple peut contenir des espaces, des majuscules, des accents ou des symboles qui modifient le résultat.

Erreurs fréquentes à éviter

Synthèse du chapitre

• Chaîne : suite finie et ordonnée de caractères.
• Longueur : nombre total de caractères, espaces inclus.
• Indice : position d’un caractère ; il doit rester dans les bornes.
• Concaténation : assemblage de plusieurs chaînes.
• Comparaison : égalité ou ordre, éventuellement après normalisation de la casse.
• Extraction : récupération d’une portion de chaîne.
• Parcours : visite successive des caractères à l’aide d’une boucle.
• Recherche : détection d’une présence ou d’une position.
• Transformation : construction d’un nouveau texte par remplacement, suppression ou inversion.
• Validation : vérification systématique de règles de forme.
• Robustesse : prise en compte des chaînes vides, des espaces multiples, de la casse et des caractères spéciaux.

Glossaire

Auto-évaluation

Conclusion

Les chaînes de caractères constituent une structure essentielle de l’algorithmique. Leur traitement combine les notions étudiées dans les chapitres précédents : variables, conditions, boucles, tableaux, tests et validation. Une bonne maîtrise des parcours textuels prépare à la manipulation de fichiers, aux formulaires, à la recherche d’informations et à de nombreuses applications de programmation.

Dans les chapitres suivants, les fonctions et les procédures permettront d’isoler ces traitements dans des modules réutilisables, par exemple une fonction de validation d’identifiant, une fonction de comptage ou une fonction de normalisation.