Considere uma pilha que armazene caracteres. Faça uma função para determinar se uma string é da forma XY, onde X é uma cadeia formada por caracteres arbitrários e Y é o reverso de X. Por exemplo, se x=A B C D, então y=D C B A. Considere que x e y são duas strings distintas.

Passo 1

A ideia aqui é usar uma pilha (estrutura LIFO) para guardar a primeira metade da string e depois comparar, na ordem inversa, com a segunda metade. O conteúdo envolve operações de pilha (push e pop) e manipulação de índices de string.

Passo 2

Primeiro, calculamos o tamanho da string S e verificamos se |S| é par. Se |S| for ímpar, não dá para dividir em duas metades iguais, então já retornamos falso.
Em seguida, definimos m = |S|/2. Fazemos um laço de i = 0 até m-1 e damos push de S[i] na pilha. Isso empilha exatamente os caracteres de X.

Passo 3

Agora fazemos outro laço de i = m até |S|-1. A cada iteração, verificamos se a pilha está vazia (se estiver, retornamos falso por segurança), então damos pop e comparamos com S[i]. Se eles forem diferentes, retornamos falso imediatamente.

Passo 4

Se conseguirmos percorrer toda a segunda metade sem mismatches e a pilha esvaziar corretamente, concluímos que a segunda metade é o reverso da primeira e retornamos verdadeiro.

Resposta

Função isReverso(S):
  1. n ← |S|
  2. Se n mod 2 ≠ 0 então retorne falso
  3. m ← n/2
  4. Pilha P vazia
  5. Para i de 0 até m-1 faça
    • P.push(S[i])
  6. Para i de m até n-1 faça
    • Se P estiver vazia então retorne falso
    • c ← P.pop()
    • Se c ≠ S[i] então retorne falso
  7. Retorne verdadeiro

Exercícios relacionados