Structure de données pour scinder plusieurs fois une chaîne en parties plus petites

Question

J'essaye d'écrire une fonction qui correspond de manière répétée aux modèles d'expression rationnelle par rapport à une chaîne d'entrée. La fonction doit prendre le modèle 1 en correspondance avec la chaîne d'entrée et la diviser en parties de segments correspondants et non correspondants. Le modèle 2 serait ensuite utilisé sur ces segments qui ne correspondent pas, jusqu'à ce que tous les modèles d'entrée soient utilisés. L'argument de retour serait alors un tableau de toutes les sous-chaînes.

Exemple simple:

input string "abcdefgh" against patterns "bc" and "f", would first split it into "a", "bc" and "defgh". Subsequently pattern "f" would be run against the "a" and "defgh" part and splitting the later into "de", "f", and "gh". Return argument {"a", "bc", "de", "f", "gh"}

(Je voudrais aussi garder un tableau associatif avec des informations de correspondance/non-appariement avec elle)

Mais mes questions sont les suivantes: Quelle est la structure de données serait le plus approprié pour effectuer ce genre de tâche? Et comment cela serait-il le mieux résolu? C'est comme si quelque chose fonctionnait de manière récursive.

Answer 1

Une liste liée vient à l'esprit où chaque fois que vous faites correspondre une regex à un nœud particulier, vous supprimez le nœud en question et insérez 3 nœuds liés à sa place.

La structure « noeud » particulier pourrait être aussi simple que d'une struct avec 3 champs, un char* pour la chaîne, un bool (char en c) pour que ce soit un match ou non, et le pointeur vers le nœud suivant.