Guia: Expressões

Pois é, como eu prometi a um tempinho, esse post será um mini tutorial sobre como resolver um exercício, nesse caso, o exercício Expressões.
Tenho em mente não entregar o código do exercício resolvido, porém apenas a ideia, deixando assim a implementação por conta do leitor. Acredito que a ideia já é suficiente, e a implementação por si próprio é um bom treino.
Bom, chega de papo, vamos ao exercício.

Exercício: 11014 - Expressões
Link: http://br.spoj.pl/problems/EXPRES11/
Clique em mais informações para ver o post completo.



Bom, vamos deixar claro que a ideia que irei expor não é necessariamente a 'melhor', visto que existem inúmeras maneiras de resolver inúmeros exercícios. Trata-se do modo como eu resolvi, e que acredito que ajudaria vocês a resolver.

Primeiro irei apresentar o conceito de pilha. Pra quem não sabe, pilha se trata de uma estrutura de dado onde você insere e retira valores como se estivesse colocando e tirando um cd de uma pilha de cd's. Pense assim, você coloca um cd com uma capa azul em cima da mesa, e logo após coloca um cd com capa vermelha. Quando você for retirar um cd da pilha, qual você irá retirar? O que está por cima, ou seja, o da capa vermelha. Essa é a ideia central da estrutura de dados pilha, o famoso First In Last Out, que numa tradução livre seria, o primeiro a entrar, último a sair. Para exemplos com pilhas, busquem algo na internet.

Agora voltar nossa atenção ao exercício. O exercício consiste em verificar se a sequência de caracteres é uma cadeia 'bem definida'. Trata-se de verificar se a abertura e fechamento das chaves, colchetes e parênteses atendem às propriedades que definem uma cadeia 'bem definida'. Antes de continuar a leitura recomendo que se tenha ciência dessas propriedades, lendo o enunciado do exercício aqui.

Tá, mas como verificar se a cadeia de caracteres atende as propriedades usando pilhas?
Simples. Vamos por parte.
Imagine que você coloca o parêntese '( ' numa pilha. Para que essa sequência agora esteja correta, será preciso que nessa sequência, em algum momento, se encontre o fechamento do parêntese ' ) '. Porém, o próximo caractere que aparece é a abertura da colcheia '[ '. Para que a sequência esteja correta, será preciso encontrar o fechamento da colcheia ' ]' antes do fechamento do parêntese ' )'. Espero que isso esteja claro.

Agora vamos a lógica.
A lógica será dividida em duas partes: A parte que uma expressão é aberta, tal como quando o caractere é uma abertura, e a parte que uma expressão é fechada, quando o caractere é um fechamento.
Na parte da abertura, você irá inserir o caractere na pilha, e na parte do fechamento você irá verificar se esse fechamento é válido.

Vamos ver um exemplo com os cd's. Digamos que você coloca um cd de capa azul em cima da mesa, e só pode retirá-lo se encontrar outro cd com capa azul. No momento que você coloca o primeiro cd, você inicia ali uma pilha, até então com apenas um cd. Em seguida você coloca um cd com capa vermelha, com a mesma regra do primeiro. A pilha então tem 2 cd's, o de capa azul embaixo, e o de capa vermelha em cima. Pela lógica, que cd eu precisaria colocar ali para que a regra não fosse quebrada? O vermelho, pois é o que está no topo de pilha. Então quando eu coloco o cd vermelho, eu retiro ambos os vermelho da pilha, ficando agora com apenas o azul. Agora para poder retirar o azul, que agora está no topo da pilha, basta colocar outro cd azul.

A lógica com o exercício não é muito distante. As diferenças são que, para adicionar um elemento a pilha, este deve ser um caractere de abertura. E para retirar algum, deverá ser encontrado um caractere de fechamento que coincida com o de abertura no topo da pilha.
Digamos que a sequência é '( [ ] )'.
O primeiro caractere é uma abertura, portanto irei adicioná-lo a pilha, até então vazia. Vamos agora ao segundo caractere, que é também uma abertura, e vamos adicioná-lo à pilha, em cima do primeiro caractere. Até agora temos a pilha nesta sequência: '( [ '.
O terceiro caractere entra na segunda parte da lógica, a parte do fechamento. Vemos que o terceiro caractere é um ' ]'. Vejamos agora se o último caractere inserido na pilha bate com o caractere de fechamento encontrado. No nosso caso está correto, então vamos retirar o caractere '[ ' da pilha. ficando só com o '( '. O próximo caractere é também de fechamento, portanto vamos conferir se o elemento mais a cima da pilha bate com o caractere de fechamento. Vemos então que mais uma vez está correto, e retiramos o último elemento da pilha '( ', que agora fica vazia.
Visto que não encontramos nenhum problema com a sequência, ela está correta, e a resposta seria 'S'.

Quais são os momentos em que podem definir que a sequência está incorreta?
Simples. Quando um caractere de fechamento não coincidir com o caractere no topo da pilha de abertura. Vale ressaltar que quando ambos coincidirem, deverão ser retirados da pilha, para que o que está abaixo seja verificado em seguida.
Também está incorreta a sequência quando o número de caracteres de fechamento não bate com o de aberturas, tal como no exemplo '( ( ) '.

Com uma lógica bem parecida, é possível resolver o exercício Ácido ribunocléico.

Bom, acho que já escrevi demais.
Espero que a minha ideia tenha ficado clara, caso contrário eu peço que deixem um comentário com sua dúvida, que responderei assim que puder.
Boa sorte na implementação, até a próxima.