Est-il possible d'écrire une fonction inverse de chaîne généralisée qui fonctionne pour toutes les localisations et tous les types de chaînes?

16

Je regardais juste la présentation de Jon Skeet (avec Tony le poney) de Dev-Days.

Bien que "écrire une fonction inverse de chaîne" soit une interview de codage 101 - je ne suis pas sûr qu'il soit réellement possible d'écrire une fonction inverse de chaîne générale, certainement pas une qui fonctionne dans toutes les localisations et tous les types de chaînes.

En plus de détecter si la chaîne d'entrée est ascii, UTF8, UTF16 (longueur fixe et variable), etc.
Il y a le code «appliquer l'accent au caractère suivant» (U + 0301) que Jon a mis en évidence. Ensuite, il y a des ligatures qui peuvent être affichées ou non, ou encodées en caractères doubles.

Semble que "inverser une chaîne" est en fait l'une des tâches informatiques les plus difficiles!

Martin Beckett
la source
Non, essayez le problème d'arrêt pour quelque chose d'un cran en difficulté mais plus simple à expliquer aux gens.
JB King
Étant une question technique non subjective, j'ose dire que cela conviendrait mieux sur StackOverflow (veuillez ne pas le republier là-bas, cependant, il sera automatisé si suffisamment de personnes votent pour le fermer ici).
Péter Török
1
Dépend du langage de programmation. Par exemple, dans Ruby, c'est aussi simple que "stressed".reverse: p
Marcelo
Grande question philosophique. FWIW, StringBuilder de Java obtient les bons substituts mais pas les combineurs
kdgregory
2
"Inverser cette chaîne en place en utilisant Java" est une bonne question piège. :)
Scott C Wilson

Réponses:

5

Oui. Si nous obtenons une chaîne, nous pouvons définitivement inverser chaque caractère.

Le problème, comme le souligne Jon, est que l'inversion a un sens et est-elle conforme aux règles linguistiques et culturelles, aux personnages et à l'encodage. L'eau devient trouble plus vous allez profondément.

Si vous effectuez n'importe quel type de manipulation de chaîne en C #, utilisez la culture invariante lors de l'écriture et de la lecture, de cette façon vous pouvez les manipuler en toute sécurité. Sinon, préparez-vous à l'échec de l'appel de support turc.

ToUpper () a l'air si innocent, mais c'est un échec épique qui attend de se produire.

Jon Raynor
la source
2
L'autre question est - pour quoi utilise-t-on jamais l'inverse de chaîne (autre que l'interview Q)? Je n'en ai jamais eu besoin que pour la manipulation de tampon de bas niveau des ports d'E / S - et même alors presque jamais réellement avec des chaînes
Martin Beckett
@Martin - D'accord. Peut-être pour un programme en anglais pour trouver des palidromes? Je ne pense pas l'avoir utilisé autre que la résolution d'une question de quiz.
Jon Raynor
@Martin true. Je pense que ce n'est fait qu'ironiquement. :)
Scott C Wilson
2

En général, lorsque cette question est posée, elle suppose US-ASCII. Il ne s'agit pas tant de tester les connaissances de la personne sur Unicode (bien que ce soit une suite intéressante) que de voir si elles comprennent comment fonctionnent les pointeurs. Un nombre surprenant de personnes ne peuvent pas faire ce type d'arithmétique de pointeur.

Scott C Wilson
la source
2
"Comment cela échouerait-il avec unicode?" est une bonne question de suivi
Martin Beckett
Bon mais peut-être un peu avancé - après tout, "inverser cette chaîne en place" est une question d'entrevue d'entrée de gamme. Vous ne demanderiez probablement pas quelque chose d'aussi simple à une personne chevronnée, à moins qu'elle ne soit très timide et que vous essayiez de la réchauffer.
Scott C Wilson
1

En tant que question d'entrevue, elle est généralement posée sur les aspects techniques de l'échange sur place d'éléments 8 bits pour inverser leur ordre (quels que soient les personnages que ceux-ci pourraient réellement représenter).

Dans le même temps, surtout si vous interviewez une personne relativement âgée, vous pouvez au moins espérer entendre des questions sur les spécifications et la forme exacte de l'entrée. Même si vous les renvoyez au cas simple de l'échange d'éléments 8 bits, sachant s'ils pensent ou non en termes plus larges que cela peut être utile.

Si vous devez gérer une large gamme d'entrées, vous devez penser à peu près en termes de "pile", un peu comme une pile réseau. Vous devez créer votre logiciel en plusieurs couches, chacune appliquant un ensemble de transformations assez spécifique dans un ordre spécifique. Cela vous permet de garder chaque partie de la transformation suffisamment simple pour que vous puissiez la garder sous contrôle et avoir une chance raisonnable de la faire répondre à ses besoins.

Je vais décrire une possibilité que j'ai trouvée au moins quelque peu réalisable. Je suis le premier à admettre que d'autres peuvent avoir de meilleures idées. Au moins pour moi, cela ressemble un peu à l'ingénierie par force brute, avec peu d'élégance réelle.

Vous voulez normalement commencer par convertir toute autre représentation en UCS-4 (alias UTF-32). Pour cela, vous préférez généralement compter sur les commentaires de l'utilisateur plutôt que d'essayer de le découvrir par vous-même. Dans certains cas, vous pouvez être sûr qu'une séquence d'octets particulière ne suit pas les règles d'un schéma de codage particulier, mais vous pouvez rarement (voire jamais) être sûr qu'elle suit un schéma de codage particulier.

L'étape suivante est facultative. Vous pouvez normaliser l'entrée à l'un des quatre formulaires de normalisation Unicode. Dans ce cas, vous auriez probablement voudrez appliquer la transformation "NFKC": décomposition de compatibilité suivie d'une composition canonique. Cela convertira (si possible) la combinaison des formes diacritiques (comme le U + 301 que Jon a mentionné) en points de code uniques (par exemple, un "A" avec un "U + 301" serait converti en "A majuscule latin avec aigu"). , U + 00C1).

Vous parcourez ensuite tous les caractères du début à la fin, divisant la chaîne en caractères réels - et s'il existe (toujours) des signes diacritiques, en les conservant avec les caractères qu'ils modifient. Le résultat sera généralement un index des caractères réels de la chaîne, tels que la position et la longueur de chacun.

Vous inversez l'ordre de ces caractères complets, généralement en utilisant l'index que vous avez créé à l'étape précédente.

Vous appliquez ensuite (à nouveau, éventuellement) un autre processus de normalisation Unicode, tel que NFD (décomposition canonique). Cela transformera le "Latin A avec aigu" susmentionné en deux points de code - un "Latin A majuscule" et un "Combinaison aiguë". Si votre entrée est arrivé à contenir un U + 00C1 pour commencer, cependant, il serait également convertir que en deux points de code.

Vous encodez ensuite la séquence de points de code UCS-4 dans l'encodage souhaité (UTF-8, UTF-16, etc.)

Notez que les étapes de normalisation Unicode peuvent / changeront le nombre de points de code nécessaires pour stocker la chaîne, donc si vous les incluez, vous ne pouvez plus planifier l'ajustement de la chaîne de résultat dans le stockage d'origine. De toute évidence, les points de code résultants peuvent ne pas correspondre directement non plus aux points de code d'entrée.

Jerry Coffin
la source
Je n'avais pas rencontré U + 301 avant que Jon n'en parle. Je ne vois pas pourquoi il est nécessaire en unicode avec des glyphes pour tous les caractères accentués - j'imagine que c'est une compatibilité descendante
Martin Beckett
@Martin: Il existe en fait un bon nombre de combinaisons de signes diacritiques (toute la gamme allant de U + 0300 à U + 036F, bien que de U + 0363 à U + 036F soient au mieux obsolètes). Des caractères précomposés sont fournis pour certaines des possibilités les plus courantes, et combinant les signes diacritiques pour tout ce qui est nécessaire.
Jerry Coffin
Trop de stockage supplémentaire, de normalisation et de conversion. Il suffit d'itérer les caractères et d'inverser l'ordre des unités de code constituantes en place. Inversez ensuite l'ordre de toutes les unités de code en place.
Déduplicateur