Manipulação de strings

[scissors cut tape]

Este capítulo trata da conversão de strings em números e das operações básicas sobre strings implementadas na biblioteca string.

Strings que representam números

Uma cadeia de caracteres decimal é qualquer sequências de dígitos decimais (caracteres 09) possivelmente precedida dos caracteres + ou .  Uma string decimal é qualquer string ASCII que representa uma cadeia de caracteres decimal.  Como converter uma string decimal no correspondente número do tipo int?

A função atoi (o nome é uma abreviatura de alphanumeric to int) da biblioteca stdlib recebe uma string decimal e devolve o correspondente int. Infelizmente, a função não verifica se a string representa um int válido (em particular, não verifica se a string é longa demais) e assim abre as portas para o seu mau uso, especialmente com argumentos na linha de comando.  Diante isso, é melhor usar da função strtol, embora ela seja mais complexa.

A função  strtol  (o nome é uma abreviatura de string to long) da biblioteca stdlib converte uma string decimal no correspondente long int.  A função aceita não apenas strings decimais mas também strings que representam números em outras bases; o terceiro argumento especifica a base.  Por exemplo,

strtol ("-9876", NULL, 10)

devolve o número −9876. (Vamos ignorar, por ora, o significado do segundo argumento.) 

Exercícios 1

  1. A-to-i.  Escreva uma função que imite comportamento de atoi. Sua função deve verificar se a string dada é válida. Se a string for longa demais, descarte os últimos dígitos.) 
  2. I-to-a.  Escreva uma função itoa (o nome é uma abreviatura de int to alphanumeric) que receba um inteiro n e devolva a string decimal que represente n. Por exemplo, o inteiro −123 deve ser convertido na string "-123".
  3. De string binária para int.  Escreva uma função que receba uma string ASCII de 0s e 1s, interprete essa string como um número natural em notação binária e devolva o correspondente int. Por exemplo, a string "1111011" deve ser convertida no inteiro 123. (Se a string for longa demais, descarte os últimos dígitos.)
  4. De int para string binária.  Escreva uma função que receba um número natural n e devolva a string ASCII de 0s e 1s que represente n em notação binária. Por exemplo, o número 123 deve ser convertido na string "1111011".
  5. Escreva uma função para converter uma string decimal na correspondente string hexadecimal.  Para testar a função, escreva um programa que receba uma cadeia de caracteres decimal pela linha de comando e imprima a correspondente cadeia hexadecimal.  Repita o exercício para converter hexadecimal em decimal, decimal em octal, octal em decimal, etc.

Ordem lexicográfica

Um byte b é menor que um byte c se o número representado por b em notação binária é menor que o número representado por c.  Por exemplo, 01000001 é menor que 01011010.  No caso de bytes cujo primeiro bit é 0, essa relação de ordem entre bytes é consistente com a ordem usual ('A' < 'B' < ... < 'Z') das letras no alfabeto ASCII (conforme a tabela ASCII).

Agora que definimos a relação de ordem entre bytes, podemos tratar da relação de ordem entre strings.  Dizemos que uma string  s  é lexicograficamente menor que uma string  t  se o primeiro byte de s que difere do correspondente byte de t é menor que o byte de t.  Mais precisamente, para decidir se s é lexicograficamente menor que t basta fazer o seguinte. Procure a primeira posição, digamos k, em que as duas strings diferem. Se s[k] < t[k] então s é lexicograficamente menor que t.  Se s[k] > t[k] então t é lexicograficamente menor que s.  Se k não está definido então s e t são iguais ou uma é prefixo próprio da outra; no segundo caso, a string mais curta é lexicograficamente menor que a mais longa.

Uma lista de strings está em ordem lexicográfica se cada string da lista é lexicograficamente menor que todas as seguintes. (Há quem diga ordem alfabética em lugar de ordem lexicográfica, mas isso não está correto.)  No caso de strings ASCII, a ordem lexicográfica é análoga à ordem em que palavras aparecem em um dicionário (embora coloque todas as letras maiúsculas antes de todas as minúsculas).  Por exemplo, a seguinte lista de strings está em ordem lexicográfica:

a
ab
abc
abcd
abd
ac
acd
ad
b
bc
bcd
bd
c
cd
d

Exercícios 2

  1. Escreva uma função que receba duas strings digamos st, e decida se s é lexicograficamente menor que t.
  2. O seguinte fragmento de programa pretende decidir se abacate é lexicograficamente menor que banana. O que está errado?
    char *a, *b;
    a = "abacate"; b = "banana";
    if (a < b) 
       printf ("%s é menor que %s\n", a, b);
    else       
       printf ("%s é maior que %s\n", a, b);
    
  3. O seguinte fragmento de programa pretende decidir se abacate é lexicograficamente menor que amora. O que está errado?
    char *a, *b;
    a = "abacate"; b = "amora";
    if (*a < *b) 
       printf ("%s é menor que %s\n", a, b);
    else         
       printf ("%s é maior que %s\n", a, b);
    

A biblioteca string

A biblioteca string (não confunda com a biblioteca obsoleta strings) contém várias funções de manipulação de strings.  Segue uma descrição das funções mais importantes da biblioteca.

String length.  A função strlen recebe uma string e devolve o seu comprimento.  Essa função poderia ser escrita assim:

unsigned int strlen (char *s) {
   int k;
   for (k = 0; s[k] != '\0'; ++k) ;
   return k;
}

String copy.  A função strcpy recebe duas strings e copia a segunda (inclusive o byte nulo final) para o espaço ocupado pela primeira. O conteúdo original da primeira string é perdido. Não invoque a função se o comprimento da primeira string for menor que o da segunda.  (Buffer overflow é uma das mais comuns origens de bugs de segurança!)  Essa função poderia ser escrita assim:

void strcpy (char *s, char *t) {
   int i;
   for (i = 0; t[i] != '\0'; ++i) 
      s[i] = t[i];
   s[i] = '\0';
}

(Na verdade, a função strcpy não é do tipo void: ela devolve o seu primeiro argumento. Isso é útil em algumas situações, mas em geral o usuário só está interessado no efeito da função e não no que ela devolve.)

A função strcpy pode ser usada da seguinte maneira para obter um efeito semelhante ao do exemplo no início do capítulo Strings e cadeias de caracteres:

char s[10];
strcpy (s, "ABC");

String compare.  A função strcmp recebe duas strings e compara as duas lexicograficamente. Ela devolve um número estritamente negativo se a primeira string for lexicograficamente menor que a segunda, devolve 0 se as duas strings são iguais e devolve um número estritamente positivo se a primeira string for lexicograficamente maior que a segunda.  Essa função poderia ser escrita assim:

int strcmp (char *s, char *t) {
   int i;
   for (i = 0; s[i] == t[i]; ++i)
      if (s[i] == '\0') return 0;
   unsigned char si = s[i], ti = t[i];
   return si - ti;
}

(Vale lembrar que o valor da expressão  si - ti  é calculado em aritmética int e não módulo 256.)

Se as strings s e t são ASCII, elas representam cadeias de caracteres ASCII. Nesse caso, a ordem lexicográfica entre as strings coincide com a ordem em que as cadeias apareceriam em um dicionário (pois a ordem  ... 0 .. 9 .. A B .. Z .. a b .. z ...  em que os caracteres aparecem na tabela ASCII é consistente com a ordem alfabética usual). Por exemplo, a seguinte sequência de palavras está em ordem lexicográfica:

abacaXi
abacate
abacates
abacaxi

Se as strings não são ASCII (ou seja, se têm bytes maiores que 127), a situação é mais complexa. Nesse caso, cada string representa uma cadeia de caracteres em código UTF-8, e portanto cada caractere é representado por 1, 2, 3 ou 4 bytes consecutivos. Felizmente, o código UTF-8 foi construído de tal maneira que ⚠ a ordem lexicográfica entre as strings coincide com a ordem em que as cadeias apareceriam em um dicionário se os caracteres fossem colocados em ordem crescente dos seus números Unicode, ou seja,  ... 0 .. 9 .. A B C .. Z .. a b c .. z .. À Á .. Ç È .. à á .. ç è ...  (veja a ordenação na página UTF-8 encoding table and Unicode characters). Por exemplo, a seguinte sequência de palavras está em ordem lexicográfica:

abocanhar
abrir
abóbora
academia
acordar
acácia
adaptar
aço
açucarado
ação

(Essa ordem lexicográfica parece estranha pois deixa as letras acentuadas longe das correspondentes letras sem acentos. Para corrigir isso, veja a função strcoll num dos exercício abaixo.)

Exercícios 3

  1. Qual a diferença entre as expressões  strcpy (s, t)  e  s = t ?
  2. Qual a diferença entre as expressões  if (strcmp (s, t) < 0)  e  if (s < t) ?
  3. Discuta as diferenças entre os três fragmentos de programa a seguir:
    char a[8], b[8];
    strcpy (a, "abacate"); strcpy (b, "banana");
    
    char *a = malloc (8), *b = malloc (8); 
    strcpy (a, "abacate"); strcpy (b, "banana");
    
    char *a, *b; 
    a = "abacate"; b = "banana";
    
  4. Estude a documentação da função strncpy da biblioteca string.
  5. Escreva uma função que receba uma string s e devolva uma cópia de s.  (Compare sua função com a função strdup da biblioteca string. Qual a diferença entre essa função e strcpy?)
  6. Escreva uma função que receba uma string ASCII s e um caractere ASCII c e devolva o índice da primeira posição em s que é igual a c.  (Compare sua função com a função strchr da biblioteca string.  Agora faça uma versão mais geral da função para procurar c a partir de uma dada posição i.
  7. Número de caracteres.  Escreva uma função que receba uma string e calcule o comprimento da cadeia de caracteres que a string representa em código UTF-8.
  8. Escreva uma função que decida se um vetor vs[0..n-1] de strings está em ordem lexicográfica.
  9. ★ Suponha dado um vetor vs[0..n-1] de strings, em ordem lexicográfica, e uma string s.  Problema: se vs não contém uma string igual a s, inserir s no vetor de modo a manter a ordem lexicográfica. Escreva uma função que resolva o problema e devolva 1 se a inserção tiver sido feita e 0 em caso contrário.
  10. ⚠ Suponha que strings s e t representam, em código UTF-8, as cadeias de caracteres S e T respectivamente. Prove que a ordem lexicográfica entre st (dada por strcmp (s, t)) coincide com a ordem em que as cadeias ST estariam num dicionário se o conjunto de caracteres estivesse em ordem crescente de números Unicode.
  11. Ordem lexicográfica em português.  A ordem lexicográfica calculada pela função strcmp compara duas strings byte-a-byte, ignorando as características do eventual esquema de codificação. Se as strings representam cadeias de caracteres em código UTF-8, a ordem lexicográfica é consistente com a ordem crescente dos números Unicode dos caracteres. Infelizmente, essa não é a ordem usual de um dicionário de português, pois as letras maiúsculas ficam longe das correspondentes minúsculas e longe das correspondentes letras com diacríticos (por exemplo, A, a e á ficam longe umas das outras). Para contornar esse inconveniente, use a variante strcoll de strcmp. ⚠ A ordem lexicográfica calculada por strcoll (o nome da função é uma abreviatura de string collate) usa a ordenação dos caracteres determinada pela variável de ambiente LC_COLLATE do seu sistema. Se o valor de LC_COLLATE é pt_BR.UTF-8, por exemplo, a ordem dos caracteres é  ... a A á Á à À â Â .. b B c C ç Ç d D .. z Z ...

    Use a função strcoll para escrever um programa que ordene lexicograficamente uma sequência de palavras em português codificada em UTF-8. As palavras são digitadas no terminal e a lista ordenada deve ser exibida na tela, uma por linha. Faça testes. Se o valor de LC_COLLATE no seu sistema não for pt_BR.UTF-8, você pode fazer algo assim:

    #include <locale.h>
    void main (void) {
       setlocale (LC_COLLATE, "pt_BR.UTF-8");
       ... código da ordenação ...
    }
    

    (Também pode mudar o valor de LC_COLLATE, temporariamente, antes de invocar o seu programa: ~$ LC_COLLATE="pt_BR.UTF-8" ./meuprograma.)