É possível escrever uma função reversa de string generalizada que funcione para todas as localizações e tipos de string?

16

Eu estava assistindo a apresentação de Jon Skeet (com Tony the Pony) da Dev-Days.

Embora "escrever uma função de reversão de cadeia de caracteres" esteja codificando a entrevista 101 - não tenho certeza de que seja realmente possível escrever uma função geral de reversão de cadeia de caracteres, certamente não uma que funcione em todas as localizações e em todos os tipos de cadeia de caracteres.

Além de detectar se a sequência de entrada é ascii, UTF8, UTF16 (comprimento fixo e variável) etc.
Há o código 'aplicar acento ao próximo caractere' (U + 0301) que Jon destacou. Depois, existem ligaduras que podem ou não ser exibidas ou codificadas como caracteres duplos.

Parece que "reverter uma string" é realmente uma das tarefas mais difíceis da ciência da computação!

Martin Beckett
fonte
Não, tente o problema da parada para algo que um passo em dificuldade, mas mais simples de explicar às pessoas.
JB rei
Sendo uma questão técnica não subjetiva, eu arriscaria dizer que isso se encaixaria melhor no StackOverflow (por favor, não o repita lá, ele será automigrado se houver pessoas suficientes para votar aqui).
Péter Török
1
Depende da linguagem de programação. Por exemplo, em Ruby, é tão fácil quanto "stressed".reverse: p
Marcelo
Grande questão filosófica. FWIW, StringBuilder de Java recebe surrogates direito, mas não combinadores
kdgregory
2
"Inverter essa string no lugar usando Java" é uma boa questão de truque. :)
Scott C Wilson

Respostas:

5

Sim. Se obtivermos uma string, podemos definitivamente reverter cada caractere.

O problema, como aponta Jon, é que a reversão faz sentido e está em conformidade com as regras de linguagem e cultura, caracteres e codificação. A água fica escura quanto mais fundo você vai.

Se você estiver executando algum tipo de manipulação de seqüência de caracteres em C #, use a cultura Invariant ao escrever e ler, dessa forma, poderá manipulá-las com segurança. Caso contrário, prepare-se para a falha na chamada de suporte turco.

ToUpper () parece tão inocente, mas é uma falha épica esperando para acontecer.

Jon Raynor
fonte
2
A outra pergunta é: para que alguém usa o string reverse (exceto a entrevista Q)? Eu só precisava de manipulação tampão baixo nível de portas I / O - e mesmo assim quase nunca realmente com cordas
Martin Beckett
@ Martin - De acordo. Talvez para um programa de inglês encontrar palidromes? Acho que não o usei além de resolver uma pergunta do questionário.
Jon Raynor 26/07
@Martin true. Eu acho que é feito apenas ironicamente. :)
Scott C Wilson
2

Em geral, quando essa pergunta é feita, ela assume o US-ASCII. A questão não é tanto testar o conhecimento da pessoa sobre Unicode (embora isso seja uma continuação interessante), como ver se eles entendem como os ponteiros funcionam. Um número surpreendente de pessoas não pode fazer esse tipo de aritmética de ponteiro.

Scott C Wilson
fonte
2
"Como isso falharia com o unicode?" é uma boa pergunta de acompanhamento
Martin Beckett
Bom, mas talvez um pouco avançado - afinal, "inverter essa cadeia de caracteres" é uma pergunta de entrevista básica. Você provavelmente não perguntaria a uma pessoa experiente algo tão simples, a menos que eles fossem muito tímidos e você estivesse tentando aquecê-los.
23911 Scott C Wilson
1

Como uma pergunta de entrevista, geralmente é perguntado sobre os bits técnicos de uma troca no local de itens de 8 bits para reverter sua ordem (independentemente de quais caracteres eles realmente representam).

Ao mesmo tempo, especialmente se você estiver entrevistando uma pessoa relativamente sênior, pode esperar pelo menos ouvir algumas perguntas sobre a especificação e a forma exata da entrada. Mesmo se você direcioná-los de volta ao simples caso de trocar itens de 8 bits, saber se eles pensam ou não em termos mais amplos do que isso pode ser valioso.

Se você precisar lidar com uma ampla variedade de entradas, precisará pensar em termos de uma "pilha", um pouco como uma pilha de rede. Você precisa criar seu software em várias camadas, cada uma das quais aplica um conjunto de transformações bastante específico em uma ordem específica. Isso permite que você mantenha cada parte da transformação simples o suficiente para mantê-la sob controle e tenha uma chance razoável de fazê-la atender aos seus requisitos.

Esboçarei uma possibilidade que achei pelo menos um pouco viável. Eu sou o primeiro a admitir que pode haver outros que têm idéias melhores. Pelo menos para mim, isso parece um pouco com a engenharia de força bruta, com pouca elegância real.

Você normalmente deseja começar convertendo qualquer outra representação para UCS-4 (também conhecido como UTF-32). Para isso, geralmente você prefere confiar nas informações do usuário do que tentar descobrir por conta própria. Em alguns casos, você pode ter certeza de que uma sequência específica de octetos não segue as regras de um esquema de codificação específico, mas raramente (se alguma vez) pode ter certeza de que ela segue um esquema de codificação específico.

O próximo passo é opcional. Você pode normalizar a entrada para um dos quatro formulários de normalização Unicode. Nesse caso, você provavelmente desejaria aplicar a transformação "NFKC": decomposição de compatibilidade seguida por composição canônica. Isso (sempre que possível) converterá formas diacríticas combinadas (como o U + 301 mencionado por Jon) em pontos de código único (por exemplo, um "A" com um "U + 301" seria convertido em "capital latina A com agudo" , U + 00C1).

Você então percorre todos os caracteres do começo ao fim, dividindo a string em caracteres reais - e se houver (ainda) combinando marcas diacríticas, mantendo-os com os caracteres que eles modificam. O resultado disso normalmente será um índice dos caracteres reais da string, como a posição e o comprimento de cada um.

Você inverte a ordem desses caracteres completos, geralmente usando o índice criado na etapa anterior.

Você então (novamente, opcionalmente) aplica outro processo de normalização Unicode, como NFD (decomposição canônica). Isso transformará o mencionado "Latin A com agudo" de volta em dois pontos de código - um "Latim maiúsculo A" e um "combinando Agudos". No entanto, se sua entrada contivesse um U + 00C1, ela também converteria esse em dois pontos de código também.

Em seguida, você codifica a sequência dos pontos de código UCS-4 na codificação desejada (UTF-8, UTF-16, etc.)

Observe que as etapas de normalização Unicode podem / irão alterar o número de pontos de código necessários para armazenar a sequência, portanto, se você incluí-los, não poderá mais planejar o ajuste da sequência de resultados no armazenamento original. Obviamente, os pontos de código resultantes também podem não corresponder diretamente aos pontos de código de entrada.

Jerry Coffin
fonte
Eu não havia encontrado o U + 301 antes de Jon mencioná-lo. Eu não posso ver porque ela é necessária em unicode com glifos para todos os caracteres acentuados - Imagino que de compatibilidade com versões anteriores
Martin Beckett
@ Martin: Na verdade, existe um número razoável de diacríticos combinados (toda a faixa de U + 0300 a U + 036F, embora de U + 0363 a U + 036F seja obsoleta, na melhor das hipóteses). Caracteres pré-compostos são fornecidos para algumas das possibilidades mais comuns e combinam diacríticos para qualquer outra coisa necessária.
Jerry Coffin
Excesso de armazenamento extra, normalização e conversão. Apenas itere os caracteres e inverta a ordem das unidades de código constituintes no local. Em seguida, inverta a ordem de todas as unidades de código no local.
Deduplicator