Comparação ‘natureba’

Você já reparou que quando você tenta colocar uma lista de strings em ordem, e essa sequência contém números, nunca consegue a ordem correta? Por exemplo: Se tentar ordenar as strings contendo números de 1 a 10 obterá: 1 10 2 3 4 5 …

Isso acontece porque as rotinas de comparação de strings assumem que uma string menor deve ser classificada como lexicamente menor. Assim, “1” é menor que “10” e, por sua vez, é menor que “2”.

Eis uma rotina que faz a comparação “natural” de strings:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

/* Typedef para facilitar a leitura do qsort(). */
typedef int (*compfptr)(const void *, const void *);

/* Protótipo da função de comparação */
int naturalstrcmp(const char **, const char **);

/* Exemplo de uso */
int main(int argc, char **argv)
{
  if (argc < 3)
  {
    fprintf(stderr, "natural num1 num2 ...\n");
    return EXIT_FAILURE;
  }

  /* Ordena strings da linha de comando */
  qsort( &argv[1], argc - 1, sizeof(char *),
         (compfptr) naturalstrcmp);

  while (--argc)
    printf("%s\n",(++argv)[0]);

  return EXIT_SUCCESS;
}

/* Compara duas strings.

   AVISO:
   As partições numéricas não podem ser superiores a LONG_MAX.
   Altere as linhas de conversão dentro do loop, se necessário. */
int naturalstrcmp(const char **ps1, const char **ps2)
{
  char *s1, *s2;
  long n1, n2;

  /* Se s1 for nula ou vazia... */
  if ((ps1 == NULL) || (*ps1 == NULL))
  {
    if ((ps2 == NULL) || (*ps2 == NULL))
      return 0;
    else
     return -1; /* Se s2 não for, s1 < s2 */
  }
  else
    if ((ps2 == NULL) || (*ps2 == NULL))
      return 1; /* Se s1 != NULL e s2 == NULL, s1 > s2 */

  /* Agora vamos varrer as strings... */
  for (s1 = (char *)*ps1, s2 = (char *)*ps2;
       *s1 != 0 && *s2 != 0;
       s1++, s2++)
  {
    /* Ambas as posições contém números? */
    if (isdigit(*s1) && isdigit(*s2))
    {
      /* Converte strings "parciais" para números.
         Altere isso de acordo com sua necessidade. */
      n1 = strtol(s1, NULL, 10);
      n2 = strtol(s2, NULL, 10);

           if (n1 > n2) return 1;
      else if (n1 < n2) return -1;
    }
    else
      if (*s1 > *s2)      return 1;
      else if (*s1 < *s2) return -1;
  }

  /* Finalmente, uma string pode ser maior que outra! */
  if (*s1 == 0 && *s2 != 0) return -1;
  else if (*s1 != 0 && *s2 == 0) return 1;

  return 0;
}

Note que, ao encontrar números em ambas as strings, a rotina obtém os números e os compara como números. A rotina é melhor que strcmp, por exemplo, mais ainda tem algumas falhas. Considere strings contendo endereços, por exemplo:

"Rua dos bobos,1"
"Rua dos bobos, 3"

A segunda string será classificada ANTES da primeira, já que “espaço” tem valor menor que números. A rotina também não leva em consideração os diversos charsets e deve falhar miseravelmente se você usar um MBCS (Multi Byte Character Set), como o UTF-8, por exemplo.

Além disso, a rotina pode ser acelerada um pouco se usarmos melhor as rotinas strtol, que devolvem, no segundo parâmetro, o ponteiro da próxima posição que não é um número. As linhas onde se encontram as chamadas a essa função podem ser substituídas por:

/* Converte strings "parciais" para números.
   Altere isso de acordo com sua necessidade. */
  char *p;

  n1 = strtol(s1, &p, 10); s1 = p - 1;
  n2 = strtol(s2, &p, 10); s2 = p - 1;
Anúncios

Deixe um comentário

Faça o login usando um destes métodos para comentar:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s