trab2.2013.1-v01

Prévia do material em texto

Universidade Federal da Bahia
Graduação em Ciência da Computação
MATA54 - Estruturas de Dados e Algoritmos II
Segundo Trabalho Prático
Prof. Flávio Assis
Semestre 2013.1 - 5 de agosto de 2013
Casamento Parcial de Padrões e Busca por Palavras
1 Descrição Geral do Trabalho
Neste trabalho, os alunos se organizarão em equipes para fazer um programa
para verificar se palavras dadas estão corretas ou não. Se uma palavra não es-
tiver correta, o programa deve propor correções para esta palavra. Uma palavra
é considerada correta se e somente se estiver em uma base de palavras, man-
tida pelo programa. O programa deve armazenar a classe morfológica de cada
palavra, além de informações específicas de cada classe.
As classes consideradas serão apenas substantivos, adjetivos, preposições e
verbos. As informações específicas de cada classe são:
• substantivo: gênero (masculino ou feminino), número (singular ou plural)
• adjetivo: gênero (masculino, feminino ou neutro)
• preposições: não há informações específicas
• verbos: pessoa (primeira, segunda ou terceira), número (singular ou plu-
ral), conjugação (primeira, segunda ou terceira)
Deve-se considerar que a quantidade de palavras é muito grande, de forma
que é incorreto assumir que todas as palavras podem ser armazenadas ao mesmo
tempo na memória principal. Uma palavra pode pertencer a mais de uma classe
morfológica.
A equipe deve procurar desenvolver a solução mais eficiente possível.
2 Formato da Entrada
A entrada será formada por uma sequência de operações, terminada pela
operação de término de sequência. As operações que devem ser suportadas
pelo programa são:
1. insere palavra: esta operação deve inserir a palavra no dicionário.
Esta operação terá duas ou três linhas. Na primeira linha haverá a letra
’i’. Na segunda linha haverá uma palavra, seguida por um espaço, seguido
1
por uma das seguintes letras: ’s’ (para substantivo), ’a’ (para adjetivo),
’p’ (para preposição) ou ’v’ (para verbo).
Se a palavra a ser inserida for um substantivo, haverá uma terceira linha,
contendo a letra ’m’ (masculino) ou ’f’ (feminino), seguida de um espaço,
seguido da letra ’s’ (singular) ou ’p’ (plural).
Se a palavra a ser inserida for um adjetivo, haverá uma terceira linha,
contendo apenas a letra ’m’ (masculino), ’f’ (feminino) ou ’n’ (neutro).
Se a palavra a ser inserida for uma preposição, não haverá terceira linha.
Se a palavra a ser inserida for um verbo, a terceira linha terá o digito ’1’
(primeira pessoa), ’2’ (segunda pessoa) ou ’3’ (terceira pessoa), seguido de
um espaço, seguido da letra ’s’ (singular) ou ’p’ (plural), seguida de um
espaço, seguido do digito ’1’ (primeira conjugação), ’2’ (segunda conju-
gação) ou ’3’ (terceira conjugação).
Uma mesma palavra pode ser inserida em classes diferentes. Por exemplo,
casa pode ser inserida como substantivo e, mais tarde, como verbo.
2. sugestões por troca: esta operação terá duas linhas. Na primeira linha
ocorrerá a letra ’t’. Na segunda linha ocorrerá uma palavra. Esta operação
listará todas as palavras que podem ser obtidas a partir da palavra digitada
na segunda linha, trocando-se apenas um dos caracteres desta palavra por
outro. As palavras obtidas devem ser apresentadas em ordem alfabética.
Por exemplo, se a palavra digitada for capa e o dicionário contiver apenas
as palavras capas, cara e casa, esta operação deve gerar, como saída, as
palavras cara e casa (nesta ordem).
3. sugestões por inserção: esta operação terá duas linhas. Na primeira
linha ocorrerá a letra ’a’. Na segunda linha ocorrerá uma palavra. Esta
operação listará todas as palavras que podem ser obtidas a partir da
palavra digitada na segunda linha, inserindo-se um caractere (mantendo-
se a ordem dos caracteres na palavra original). As palavras obtidas devem
ser apresentadas em ordem alfabética.
Por exemplo, se a palavra digitada for capa e o dicionário contiver apenas
as palavras capas, cara e casa, esta operação deve gerar, como saída, a
palavra capas.
4. sugestões por remoção: esta operação terá duas linhas. Na primeira
linha ocorrerá a letra ’r’. Na segunda linha ocorrerá uma palavra. Esta
operação listará todas as palavras que podem ser obtidas a partir da
palavra digitada na segunda linha, removendo-se um caractere (mantendo-
se a ordem dos caracteres na palavra original). As palavras obtidas devem
ser apresentadas em ordem alfabética.
Por exemplo, se a palavra digitada for capas e o dicionário contiver apenas
as palavras capa, cara e casa, esta operação deve gerar, como saída, a
palavra capa.
2
5. dados de palavra: esta operação terá duas linhas. A primeira conterá
a letra ’f’. A segunda linha conterá uma palavra. Esta operação deve
imprimir as informações referentes à palavra solicitada.
6. palavras em ordem: esta operação terá uma linha. Esta linha con-
terá a letra ’o’. Esta operação listará todas as palavras armazenadas no
dicionário, em ordem alfabética crescente.
7. imprime estrutura: esta operação terá uma linha, contendo a letra
’p’. Esta operação deve gerar uma impressão da estrutura utilizada pelo
programa para armazenar os dados.
8. remove palavra: esta operação terá duas linhas. A primeira linha terá
a letra ’d’. A segunda linha conterá uma palavra. Esta operação remove
a ocorrência desta palavra da árvore.
9. término da sequência de comandos: a sequência de comandos será
terminada por uma linha com a letra ’e’.
A entrada conterá apenas caracteres minúsculos.
3 Formato da Saída
As operações terão o seguinte formato de saída:
1. insere palavra: esta operação não gera saída.
2. sugestões por troca: esta operação listará uma palavra por linha. Caso
a operação não gere palavras, nenhuma saída deve ser gerada.
3. sugestões por inserção: esta operação listará uma palavra por linha.
Caso a operação não gere palavras, nenhuma saída deve ser gerada.
4. sugestões por remoção: esta operação listará uma palavra por linha.
Caso a operação não gere palavras, nenhuma saída deve ser gerada.
5. dados de palavra: caso a palavra não exista no dicionário, esta operação
deve gerar na saída a sequência de caracteres ’palavra:’, seguida de um
espaço, seguido da palavra indicada na operação, seguida por um espaço,
seguido pela sequência de caracteres ’nao existe no dicionario’.
Caso a palavra exista, a saída deve conter a sequência de caracteres
’palavra:’, seguida de um espaço, seguido da palavra indicada na
operação. Na linha seguinte, será apresentada a classe da palavra:
substantivo, adjetivo, preposicao ou verbo. Deve-se escrever o nome da
classe, não apenas a primeira letra do nome da classe. Se a classe for
preposição, não haverá terceira linha. Se não, os dados da palavra serão
apresentados, dependendo de sua classe morfológica, como a seguir:
3
(a) se a palavra for um substantivo, será impresso seu gênero (masculino)
ou (feminino), seguido de uma vírgula, seguida de um espaço, seguido
do seu número (singular) ou (plural);
(b) se a palavra for um adjetivo, será impresso o seu gênero (masculino),
(feminino) ou (neutro);
(c) se a palavra for um verbo, será impressa sua pessoa (primeira
pessoa), (segunda pessoa) ou (terceira pessoa), seguida de uma vír-
gula, seguida de um espaço, seguido do seu número (singular) ou
(plural), seguido de uma vírgula, seguida de um espaço, seguido de
sua conjugação (primeira conjugação), ’2’ (segunda conjugação) ou
’3’ (terceira conjugação).
6. palavras em ordem: esta operação listará uma palavra por linha.
7. imprime estrutura: esta operação imprime a estrutura utilizada para
armazenar as palavras e seus dados. O formato da impressão deve ser
decidido pela equipe. O formato deve ser tal, no entanto, que permita o
completo entendimento de como os dados estão armazenados.
8. remove palavra: esta operação não gera saída.
9. término da sequência de comandos: esta operação não gera saída.
Não deve haver espaço entre linhas na saída. A saída deve conter apenas
caracteres em minúsculo.
4 Observações
Trabalho em equipe de 4 alunos (obs.: provavelmente haverá uma equipecom
5 alunos).
Além do código do trabalho, a equipe deve entregar um texto de, no
máximo, duas páginas, descrevendo, de maneira sucinta, a forma como o pro-
grama armazena os dados e realiza as operações.
O código e o texto devem ser armazenados na página da disciplina, protegidos
por senha. A equipe deve enviar a senha para o email do professor (o aluno deve
utilizar zip).
Data de entrega: 03/09/2013
Linguagens de programação permitidas: C, C++, Java ou Python.
Observação Importante: Para as linguagens C, C++ e Java, somente tra-
balhos feitos utilizando-se os seguintes compiladores serão aceitos:
• C: gcc ou djgpp
• C++: g++ ou djgpp
4
• Java: compilador java do JDK (mais recente)
Não serão compilados trabalhos em outros compiladores! Erros oca-
sionados por uso de diferentes compiladores serão considerados erros
do trabalho!
5