83 votes

Est-il possible d'incrémenter des nombres à l'aide d'une substitution d'expressions rationnelles ?

Est-il possible d'incrémenter des nombres à l'aide d'une substitution d'expressions rationnelles ? Pas en utilisant substitution évaluée/fonctionnelle bien sûr.

Cette question a été inspirée par un autre, où le demandeur voulait incrémenter des nombres dans un éditeur de texte . Il y a probablement plus d'éditeurs de texte qui prennent en charge la substitution par des expressions rationnelles que d'éditeurs qui prennent en charge des scripts complets, de sorte qu'une expression rationnelle peut être pratique à utiliser, si elle existe.

Par ailleurs, j'ai souvent appris des choses intéressantes grâce à des solutions intelligentes à des problèmes pratiquement inutiles, alors je suis curieux.

Supposons que nous ne parlions que d'entiers décimaux non négatifs, c'est-à-dire \d+ .

  • Est-ce possible en une seule substitution ? Ou en un nombre fini de substitutions ?

  • Si ce n'est pas le cas, est-il au moins possible étant donné une borne supérieure par exemple, les chiffres jusqu'à 9999 ?

Bien sûr, c'est faisable avec une boucle while (en remplaçant while par matched), mais nous optons ici pour une solution sans boucle.

49voto

DKATyler Points 792

Le sujet de cette question m'a amusé en raison d'une mise en œuvre particulière que j'ai effectuée précédemment. Il se trouve que ma solution consiste en deux substitutions et je vais donc la publier.

Mon environnement de mise en œuvre est solaris, exemple complet :

echo "0 1 2 3 7 8 9 10 19 99 109 199 909 999 1099 1909" |
perl -pe 's/\b([0-9]+)\b/0$1~01234567890/g' |
perl -pe 's/\b0(?!9*~)|([0-9])(?=9*~[0-9]*?\1([0-9]))|~[0-9]*/$2/g'

1 2 3 4 8 9 10 11 20 100 110 200 910 1000 1100 1910

Il faut le démonter pour l'expliquer :

s/\b([0-9]+)\b/0$1~01234567890/g

Pour chaque chiffre (#), remplacez-le par 0#~01234567890. Le premier 0 est utilisé au cas où il serait nécessaire d'arrondir 9 à 10. Le bloc 01234567890 sert à l'incrémentation. L'exemple de texte pour "9 10" est le suivant :

09~01234567890 010~01234567890

Les différents éléments de la prochaine expression rationnelle peuvent être décrits séparément ; ils sont reliés par des tuyaux afin de réduire le nombre de substitutions :

s/\b0(?!9*~)/$2/g

Sélectionnez le chiffre "0" devant tous les nombres qui n'ont pas besoin d'être arrondis et rejetez-le.

s/([0-9])(?=9*~[0-9]*?\1([0-9]))/$2/g

(?=) est une anticipation positive, \1 est le groupe de correspondance n° 1. Cela signifie qu'il faut faire correspondre tous les chiffres suivis d'un 9 jusqu'à la marque '~', puis aller dans le tableau de recherche et trouver le chiffre qui suit ce numéro. Remplacez-le par le chiffre suivant dans le tableau de correspondance. Ainsi, "09~" devient "19~" puis "10~" au fur et à mesure que le moteur regex analyse le numéro.

s/~[0-9]*/$2/g

Cette expression rationnelle supprime la table de recherche ~.

47voto

Martin Büttner Points 26511

Wow, il s'avère que c'est possible (même si c'est moche) !

Si vous n'avez pas le temps ou l'envie de lire toute l'explication, voici le code qui permet de le faire :

$str = '0 1 2 3 4 5 6 7 8 9 10 11 12 13 19 20 29 99 100 139';
$str = preg_replace("/\d+/", "$0~", $str);
$str = preg_replace("/$/", "#123456789~0", $str);
do
{
$str = preg_replace(
    "/(?|0~(.*#.*(1))|1~(.*#.*(2))|2~(.*#.*(3))|3~(.*#.*(4))|4~(.*#.*(5))|5~(.*#.*(6))|6~(.*#.*(7))|7~(.*#.*(8))|8~(.*#.*(9))|9~(.*#.*(~0))|~(.*#.*(1)))/s",
    "$2$1",
    $str, -1, $count);
} while($count);
$str = preg_replace("/#123456789~0$/", "", $str);
echo $str;

Commençons maintenant.

Donc, tout d'abord, comme les autres l'ont mentionné, ce n'est pas possible en un seul remplacement, même si vous le bouclez (parce que comment inséreriez-vous l'incrément correspondant à un seul chiffre). Mais si vous préparez d'abord la chaîne, il y a un remplacement unique qui peut être bouclé. Voici ma démonstration en PHP.

J'ai utilisé cette chaîne de test :

$str = '0 1 2 3 4 5 6 7 8 9 10 11 12 13 19 20 29 99 100 139';

Tout d'abord, marquons tous les chiffres que nous voulons incrémenter en ajoutant un caractère de marquage (j'utilise ~ mais vous devriez probablement utiliser un caractère Unicode ou une séquence de caractères ASCII qui n'apparaîtra certainement pas dans votre chaîne cible.

$str = preg_replace("/\d+/", "$0~", $str);

Comme nous remplacerons un chiffre par numéro à la fois (de droite à gauche), nous ajouterons simplement le caractère de marquage après chaque numéro complet.

C'est là qu'intervient la principale difficulté. Nous ajoutons un petit "lookup" à la fin de notre chaîne (également délimitée par un caractère unique qui n'apparaît pas dans votre chaîne ; pour plus de simplicité, j'ai utilisé # ).

$str = preg_replace("/$/", "#123456789~0", $str);

Nous l'utiliserons pour remplacer les chiffres par leurs successeurs correspondants.

C'est maintenant qu'intervient la boucle :

do
{
$str = preg_replace(
    "/(?|0~(.*#.*(1))|1~(.*#.*(2))|2~(.*#.*(3))|3~(.*#.*(4))|4~(.*#.*(5))|5~(.*#.*(6))|6~(.*#.*(7))|7~(.*#.*(8))|8~(.*#.*(9))|9~(.*#.*(~0))|(?<!\d)~(.*#.*(1)))/s",
    "$2$1",
    $str, -1, $count);
} while($count);

D'accord, que se passe-t-il ? Le modèle de correspondance a une alternative pour chaque chiffre possible. Les chiffres sont ainsi associés à des successeurs. Prenons par exemple la première alternative :

0~(.*#.*(1))

Cela correspondra à n'importe quel 0 suivi de notre marqueur d'incrémentation ~ puis il fait correspondre le tout à notre délimiteur de triche et au successeur correspondant (c'est la raison pour laquelle nous avons placé chaque chiffre ici). Si vous jetez un coup d'œil au remplacement, celui-ci sera remplacé par $2$1 (qui sera alors 1 et ensuite tout ce que nous avons fait correspondre après le ~ pour le remettre en place). Notez que nous laissons tomber le ~ dans le processus. Incrémenter un chiffre de 0 a 1 suffit. Le nombre a été incrémenté avec succès, il n'y a pas de report.

Les 8 alternatives suivantes sont exactement les mêmes pour les chiffres 1 à 8 . Nous nous occupons ensuite de deux cas particuliers.

9~(.*#.*(~0))

Lorsque nous remplaçons le 9 Nous ne laissons pas tomber le marqueur d'incrémentation, mais nous le plaçons à gauche du marqueur d'incrémentation résultant. 0 au lieu de cela. Ceci (combiné avec la boucle environnante) est suffisant pour mettre en œuvre la propagation par report. Il reste maintenant un cas particulier. Pour tous les nombres constitués uniquement de 9 nous nous retrouverons avec le ~ devant le numéro. C'est à cela que sert la dernière alternative :

(?<!\d)~(.*#.*(1))

Si nous rencontrons un ~ qui n'est pas précédé d'un chiffre (d'où le lookbehind négatif), il doit avoir été porté tout au long d'un nombre, et nous le remplaçons donc simplement par un 1 . Je pense que nous n'avons même pas besoin du lookbehind négatif (parce que c'est la dernière alternative qui est cochée), mais c'est plus sûr ainsi.

Une brève note sur la (?|...) autour de l'ensemble du modèle. Cela permet de s'assurer que nous trouvons toujours les deux correspondances d'une alternative dans les mêmes références $1 y $2 (au lieu de chiffres de plus en plus grands dans la chaîne).

Enfin, nous ajoutons le DOTALL ( s ), pour que cela fonctionne avec les chaînes de caractères qui contiennent des sauts de ligne (sinon, seuls les nombres de la dernière ligne seront incrémentés).

Il s'agit donc d'une chaîne de remplacement assez simple. Il suffit d'écrire d'abord $2 (dans lequel nous capturons le successeur, et éventuellement le marqueur de report), puis nous remettons en place tout ce que nous avons apparié avec $1 .

C'est tout ! Il ne nous reste plus qu'à retirer notre hack de la fin de la chaîne, et nous aurons terminé :

$str = preg_replace("/#123456789~0$/", "", $str);
echo $str;
> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 20 21 30 100 101 140

Nous pouvons donc le faire entièrement à l'aide d'expressions régulières. Et la seule boucle que nous avons utilise toujours la même expression régulière. Je pense que c'est le plus proche que nous puissions obtenir sans utiliser de preg_replace_callback() .

Bien sûr, cela aura des conséquences horribles si nous avons des nombres avec des points décimaux dans notre chaîne. Mais cela pourrait probablement être pris en charge par la toute première préparation-remplacement.

Mise à jour : Je viens de réaliser que cette approche s'étend immédiatement à des incréments arbitraires (et pas seulement aux +1 ). Il suffit de modifier le premier remplacement. Le nombre de ~ que vous ajoutez est égal à l'incrément que vous appliquez à tous les nombres. Ainsi, le

$str = preg_replace("/\d+/", "$0~~~", $str);

incrémenterait chaque entier de la chaîne par 3 .

12voto

Andrew Cheong Points 11331

J'ai réussi à le faire fonctionner en 3 substitutions (pas de boucles).

tl;dr

s/$/ ~0123456789/

s/(?=\d)(?:([0-8])(?=.*\1(\d)\d*$)|(?=.*(1)))(?:(9+)(?=.*(~))|)(?!\d)/$2$3$4$5/g

s/9(?=9*~)(?=.*(0))|~| ~0123456789$/$1/g

Explication

Laisser ~ un caractère spécial pas n'est censé apparaître nulle part dans le texte.

  1. Si un caractère ne figure nulle part dans le texte, il n'est pas possible de le faire apparaître par magie. Nous commençons donc par insérer les personnages qui nous intéressent à la toute fin du texte.

    s/$/ ~0123456789/

    Par exemple,

    0 1 2 3 7 8 9 10 19 99 109 199 909 999 1099 1909

    devient :

    0 1 2 3 7 8 9 10 19 99 109 199 909 999 1099 1909 ~0123456789
  2. Ensuite, pour chaque nombre, nous (1) incrémentons le dernier non 9 (ou ajouter un 1 si tous sont 9 ), et (2) "marquer" chaque groupe suivant de 9 s.

    s/(?=\d)(?:([0-8])(?=.*\1(\d)\d*$)|(?=.*(1)))(?:(9+)(?=.*(~))|)(?!\d)/$2$3$4$5/g

    Par exemple, notre exemple devient :

    1 2 3 4 8 9 19~ 11 29~ 199~ 119~ 299~ 919~ 1999~ 1199~ 1919~ ~0123456789
  3. Enfin, nous (1) remplaçons chaque groupe "marqué" de 9 avec 0 (2) retirer les ~ et (3) supprimer le jeu de caractères à la fin.

    s/9(?=9*~)(?=.*(0))|~| ~0123456789$/$1/g

    Par exemple, notre exemple devient :

    1 2 3 4 8 9 10 11 20 100 110 200 910 1000 1100 1910

Exemple PHP

$str = '0 1 2 3 7 8 9 10 19 99 109 199 909 999 1099 1909';
echo $str . '<br/>';
$str = preg_replace('/$/', ' ~0123456789', $str);
echo $str . '<br/>';
$str = preg_replace('/(?=\d)(?:([0-8])(?=.*\1(\d)\d*$)|(?=.*(1)))(?:(9+)(?=.*(~))|)(?!\d)/', '$2$3$4$5', $str);
echo $str . '<br/>';
$str = preg_replace('/9(?=9*~)(?=.*(0))|~| ~0123456789$/', '$1', $str);
echo $str . '<br/>';

O

0 1 2 3 7 8 9 10 19 99 109 199 909 999 1099 1909
0 1 2 3 7 8 9 10 19 99 109 199 909 999 1099 1909 ~0123456789
1 2 3 4 8 9 19~ 11 29~ 199~ 119~ 299~ 919~ 1999~ 1199~ 1919~ ~0123456789
1 2 3 4 8 9 10 11 20 100 110 200 910 1000 1100 1910

6voto

Bart Kiers Points 79069

Est-ce possible en une seule substitution ?

Non.

Si ce n'est pas le cas, est-il au moins possible de procéder à une substitution unique en fonction d'une limite supérieure, par exemple pour les nombres allant jusqu'à 9999 ?

Non.

On ne peut même pas remplacer les chiffres entre 0 et 8 par leur successeur respectif. Une fois que vous avez fait correspondre et regroupé ce nombre :

/([0-8])/

vous devez le remplacer. Cependant, les expressions rationnelles n'opèrent pas sur les nombres, mais sur les chaînes de caractères. Vous pouvez donc remplacer le "nombre" (ou mieux : le chiffre) par deux fois ce chiffre, mais le moteur regex ne sait pas qu'il duplique une chaîne de caractères contenant une valeur numérique.

Même si vous faites quelque chose (de stupide) comme ça :

/(0)|(1)|(2)|(3)|(4)|(5)|(6)|(7)|(8)/

de manière à ce que le moteur des expressions rationnelles "sache" que si le groupe 1 correspond, le chiffre '0' est apparié, il ne peut toujours pas effectuer de remplacement. Vous ne pouvez pas demander au moteur de regex de remplacer le groupe 1 par le chiffre '1' , groupe '2' avec le chiffre '2' , etc. Bien sûr, certains outils comme PHP vous permettent de définir quelques modèles différents avec les chaînes de remplacement correspondantes, mais j'ai l'impression que ce n'est pas ce à quoi vous pensiez.

2voto

user1598390 Points 1047

Cela n'est pas possible par la seule recherche et substitution d'expressions régulières.

Vous devez utiliser quelque chose d'autre pour y parvenir. Vous devez utiliser le langage de programmation à votre disposition pour incrémenter le nombre.

Editer :

La définition des expressions régulières, dans le cadre de Spécification unique d'Unix ne mentionne pas les expressions régulières prenant en charge l'évaluation des expressions arithmétiques ou les possibilités d'effectuer des opérations arithmétiques.


Néanmoins, je sais que certains éditeurs (TextPad, éditeur pour Windows) permettent d'utiliser \i comme terme de substitution qui est un compteur incrémental du nombre de fois que la chaîne de recherche a été trouvée, mais il n'évalue pas ou n'analyse pas les chaînes trouvées en un nombre et ne permet pas d'y ajouter un nombre.

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X