¿Es posible escribir una función inversa de cadena generalizada que funcione para todas las localizaciones y tipos de cadena?

16

Estaba viendo la presentación de Jon Skeet (con Tony the Pony) de Dev-Days.

Aunque "escribir una función inversa de cadena" codifica la entrevista 101, no estoy seguro de que sea posible escribir una función general inversa de cadena, ciertamente no una que funcione en todas las localizaciones y todos los tipos de cadena.

Además de detectar si la cadena de entrada es ascii, UTF8, UTF16 (longitud fija y variable) etc.
Existe el código 'aplicar acento al siguiente carácter' (U + 0301) que Jon resaltó. Luego hay ligaduras que pueden mostrarse o no, o codificarse como caracteres dobles.

¡Parece que "invertir una cadena" es en realidad una de las tareas más difíciles de la informática!

Martin Beckett
fuente
No, intente el problema de detención para algo un paso más difícil pero más sencillo de explicar a la gente.
JB King
Siendo una pregunta técnica no subjetiva, me aventuraría a decir que esto encajaría mejor en StackOverflow (sin embargo, no lo vuelva a publicar allí, se automatizará si suficientes personas votan para cerrarlo aquí).
Péter Török
1
Depende del lenguaje de programación. Por ejemplo, en Ruby es tan fácil como "stressed".reverse: p
Marcelo
Gran pregunta filosófica. FWIW, StringBuilder de Java obtiene sustitutos correctos pero no combinadores
kdgregory
2
"Invertir esta cadena en su lugar usando Java" es una buena pregunta capciosa. :)
Scott C Wilson

Respuestas:

5

Si. Si obtenemos una cadena, definitivamente podemos revertir cada carácter.

El problema, como señala Jon, es que la inversión tiene sentido y se ajusta al lenguaje y las reglas culturales, los caracteres y la codificación. El agua se vuelve turbia cuanto más profundo vas.

Si está haciendo algún tipo de manipulación de cadenas en C #, use la cultura Invariante al escribir y leer, de esa manera puede manipularlos de manera segura. De lo contrario, prepárese para el fallo de la llamada de soporte turco.

ToUpper () se ve tan inocente, pero es un error épico que espera suceder.

Jon Raynor
fuente
2
La otra pregunta es: ¿para qué utiliza alguien la secuencia inversa (aparte de la entrevista Q)? Solo lo he necesitado para la manipulación de búfer de bajo nivel de puertos de E / S, e incluso entonces casi nunca con cadenas
Martin Beckett
@ Martin - De acuerdo. ¿Tal vez para un programa en inglés para encontrar palidromos? No creo que lo haya usado más que para resolver una pregunta de prueba.
Jon Raynor
@Martin cierto. Creo que solo se hace irónicamente. :)
Scott C Wilson
2

En general, cuando se hace esta pregunta, está asumiendo US-ASCII. El punto no es tanto para probar el conocimiento de la persona sobre Unicode (aunque esto sería un seguimiento interesante), como para ver si entienden cómo funcionan los punteros. Un sorprendente número de personas no puede hacer este tipo de aritmética de punteros.

Scott C Wilson
fuente
2
"¿Cómo fallaría esto con Unicode?" es una buena pregunta de seguimiento
Martin Beckett
Bueno, pero quizás algo avanzado: después de todo, "invertir esta cadena en su lugar" es una pregunta de entrevista de nivel de entrada. Probablemente no le preguntarías a una persona experimentada algo tan simple, a menos que tal vez fueran muy tímidos y trataras de calentarlos.
Scott C Wilson
1

Como una pregunta de la entrevista, por lo general se pregunta sobre los aspectos técnicos de hacer un intercambio in situ de elementos de 8 bits para revertir su orden (independientemente de los caracteres que realmente puedan representar).

Al mismo tiempo, especialmente si está entrevistando a una persona relativamente mayor, al menos podría esperar escuchar algunas preguntas sobre la especificación y la forma exacta de la entrada. Incluso si los dirige de vuelta al simple caso de simplemente intercambiar elementos de 8 bits, saber si piensan o no en términos más amplios que eso puede ser valioso.

Si tiene que lidiar con una amplia gama de entradas, debe pensar en términos de una "pila", un poco como una pila de red. Debe construir su software en varias capas, cada una de las cuales aplica un conjunto bastante específico de transformaciones en un orden específico. Esto le permite mantener cada parte de la transformación lo suficientemente simple como para mantenerla bajo control y tener una oportunidad razonable de cumplir con sus requisitos.

Esbozaré una posibilidad que he encontrado al menos algo viable. Sin embargo, soy el primero en admitir que puede haber otros que tengan mejores ideas. Al menos para mí, esto parece un poco como ingeniería de fuerza bruta, con poca elegancia real.

Normalmente desea comenzar convirtiendo cualquier otra representación a UCS-4 (también conocido como UTF-32). Para esto, generalmente preferiría confiar en la información del usuario que intentar resolverlo usted mismo. En algunos casos, puede estar seguro de que una secuencia particular de octetos no sigue las reglas de un esquema de codificación particular, pero rara vez (si alguna vez) puede estar seguro de que sigue un esquema de codificación particular.

El siguiente paso es opcional. Puede normalizar la entrada a uno de los cuatro formularios de normalización Unicode. En este caso, es probable que desee aplicar la transformación "NFKC": descomposición de compatibilidad seguida de composición canónica. Esto (cuando sea posible) convertirá la combinación de formas diacríticas (como el U + 301 que Jon mencionó) en puntos de código único (por ejemplo, una "A" con un "U + 301" se convertiría en "A latino mayúscula con agudo" , U + 00C1).

Luego, recorre todos los caracteres de principio a fin, separando la cadena en caracteres reales, y si hay (todavía) combinaciones de signos diacríticos, manteniéndolos con los caracteres que modifican. El resultado de esto generalmente será un índice de los caracteres reales en la cadena, como la posición y la longitud de cada uno.

Usted invierte el orden de esos caracteres completos, generalmente utilizando el índice que creó en el paso anterior.

Luego (de nuevo, opcionalmente) aplica otro proceso de normalización Unicode, como NFD (descomposición canónica). Esto convertirá el mencionado "A latino con agudo" de nuevo en dos puntos de código: un "A mayúscula latino" y un "agudo combinado". Si su entrada pasó a contener una U + 00C1, para empezar, sin embargo, también se convertiría que en dos puntos de código también.

Luego codifica la secuencia de puntos de código UCS-4 en la codificación deseada (UTF-8, UTF-16, etc.)

Tenga en cuenta que los pasos de normalización Unicode pueden / cambiarán la cantidad de puntos de código necesarios para almacenar la cadena, por lo que si los incluye, ya no puede planificar el ajuste de la cadena de resultados en el almacenamiento original. Obviamente, los puntos de código resultantes pueden no corresponder directamente a los puntos de código de entrada tampoco.

Jerry Coffin
fuente
No me había encontrado con U + 301 antes de que Jon lo mencionara. No puedo ver por qué se necesita en unicode con glifos para todos los caracteres acentuados. Me imagino que es compatibilidad con versiones anteriores
Martin Beckett
@ Martin: En realidad, hay un buen número de diacríticos combinados (todo el rango de U + 0300 a U + 036F, aunque de U + 0363 a U + 036F son obsoletos en el mejor de los casos). Se proporcionan caracteres precompuestos para algunas de las posibilidades más comunes, y se combinan los signos diacríticos para cualquier otra cosa necesaria.
Jerry Coffin
Demasiado almacenamiento adicional, normalización y conversión. Simplemente itere los caracteres e invierta el orden de las unidades de código constituyentes en el lugar. Luego invierta el orden de todas las unidades de código en el lugar.
Deduplicador