Compartilhe! 
Descrição dos movimentos:
4----1
ü ü
ü ü
3----2
(estado inicial)
Movimento '+' (TROCA POR CIMA): A criança que está na posição 1 troca de lugar com a criança que está na posição 2, passando sua corda por cima da dela.
Movimento '-' (TROCA POR BAIXO): A criança que está na posição 1 troca de lugar com a criança que está na posição 2, passando sua corda por baixo da dela.
Movimento '*' (GIRO): As crianças giram no sentido horário (quem está na posição 1 vai para a 2, quem está na 2 vai para a 3, quem está na 3 vai para 4, e quem está na 4 vai para 1).
Neste laboratório, devemos fazer funções para um programa que, dada sequência de movimentos acima, consiga prever o estado final das cordas. As funções devem estar em um arquivo separado.
Descrição da tarefa:
O nome da brincadeira em inglês é chamada de rational tangle dance, criada pelo matemático Jonh Conway, que nos dá algumas dicas, que justamente serão as tarefas das funções que se seguem:
1 - Você deve processar a sequência de movimentos, removendo subsequências que não afetam o resultado: "+-", "-+", "**".
2 - Se a sequêcia de movimentos começa com um GIRO ('*'), qualquer movimento de TROCA subsequente ('+' ou '-') não vai emaranhar as cordas até que um outro movimento GIRO seja executado. Sendo assim, se a sequência de movimentos começa com '*', você deve remover todos os movimentos da primeira posição da sequência até a segunda aparição de '*', inclusive.
3 - Existem duas subsequências de movimentos que mascaram o resultado. São elas: "+*+" e "-*-". Sempre que uma dessas subsequências aparecer, elas devem ser substituídas por "*-*" e "*+*", respectivamente.
Observação: As alterações 1, 2 e 3 devem ser executadas até que a sequência de movimentos não seja mais alterada. Se a sequência final obtida for vazia ou igual a "*", as cordas terminarão separadas. Caso contrário, as cordas terminarão emaranhadas.
(Obs.: a descrição da atividade e código do arquivo main são de autoria dos PEDs do IC-Unicamp.)
Arquivo com a função main:
#include <stdio.h>
#include <string.h>
int removePadrao(char str[], char padrao[], char targetStr[]);
int removeBloco(char str[], char c, char targetStr[]);
int substituiPadrao(char str[], char padrao[], char novoPadrao[], char targetStr[]);
#define MAX_MOVES 35
int main(void) {
char seq[MAX_MOVES];
char auxSeq[MAX_MOVES];
fgets(seq, 30, stdin);
int len = strlen(seq);
seq[len-1] = '\0';
while (1) {
int seqAlterada = 0;
int res = removeBloco(seq, '*', auxSeq);
if (res) {
printf("removeBloco(*): %s\n", auxSeq);
strcpy(seq, auxSeq);
seqAlterada++;
}
res = removePadrao(seq, "**", auxSeq);
if (res) {
printf("removePadrao(**): %s\n", auxSeq);
strcpy(seq, auxSeq);
seqAlterada++;
}
res = removePadrao(seq, "+-", auxSeq);
if (res) {
printf("removePadrao(+-): %s\n", auxSeq);
strcpy(seq, auxSeq);
seqAlterada++;
}
res = removePadrao(seq, "-+", auxSeq);
if (res) {
printf("removePadrao(-+): %s\n", auxSeq);
strcpy(seq, auxSeq);
seqAlterada++;
}
res = substituiPadrao(seq, "+*+", "*-*", auxSeq);
if (res) {
printf("substituiPadrao(+*+, *-*): %s\n", auxSeq);
strcpy(seq, auxSeq);
seqAlterada++;
}
res = substituiPadrao(seq, "-*-", "*+*", auxSeq);
if (res) {
printf("substituiPadrao(-*-, *+*): %s\n", auxSeq);
strcpy(seq, auxSeq);
seqAlterada++;
}
if (!seqAlterada) {
break;
}
}
len = strlen(seq);
if ( (len == 0) || ((len == 1) && (strcmp(seq, "*") == 0)) ) {
printf("Cordas terminam separadas!\n");
} else {
printf("Cordas terminam emaranhadas!\n");
}
return 0;
}
Arquivo, de minha autoria, com as funções requeridas pela main acima:
#include <stdio.h>
#include <string.h>
/* Funcao: removePadrao
*
* Processa linearmente (e uma unica vez) os carateres de uma dada sequencia de movimentos,
* removendo as ocorrencias de um dado padrao.
*
* Parametros:
* str: sequencia de movimentos '+', '-', '*'
* padrao: subsequencia de movimentos, cujas ocorrencias devem ser removidas
* targetStr: sequencia obtida apos a remocao de str de todas as ocorrencias do dado padrao.
*
*
* Retorno:
*
* 1, se as occorrencias do dado padrao foram removidas
* 0, caso contrario
*
* Exemplo:
*
* char seq1[15] = "+-*+-*-*+++";
* char seq2[15];
*
* char padrao1[3] = "+-"
* char padrao2[3] = "**"
*
* removePadrao(seq1, padrao1, seq2); // seq2 sera "**-*+++"
* removePadrao(seq1, padrao2, seq2); // seq2 sera "+-*+-*-*+++"
*
*/
int removePadrao(char str[], char padrao[], char targetStr[]) {
int k = 0, ocRemov = 0, tamPadrao, tamStr, entrou = 0;
tamPadrao = strlen(padrao);//Guarda tamanhos das strings.
tamStr = strlen(str);
for (int i = 0; i < tamStr; i++) {//Do início de str até seu final
if (str[i] == padrao[0] && tamStr - i > tamPadrao - 1) {//Se o elemento (i) de str for igual ao primeiro elemento do padrão e houver possibilidade de ali conter um padrão:
for (int j = 1; j < tamPadrao; j++)//Vá até o final do padrao comparando com str.
if (padrao[j] != str[i + j]) {//Se encontrou algo diferente, registre isso e pare o for.
entrou = 1;
break;
}
if (entrou == 0) {//Dependendo do resultado ("não entrou"), o i é incrementado de modo que ele "pule" o padrão e isso é registrado.
i += tamPadrao - 1;
ocRemov = 1;
} else {//Caso contrário, não é o padrão, a string targetStr recebe o elemento de str em i.
targetStr[k] = str[i];
k++;
entrou = 0;
}
} else {//Caso contrário, não pode ser o padrão, a string targetStr recebe o elemento de str em i.
targetStr[k] = str[i];
k++;
}
}
targetStr[k] = '\0';
return ocRemov;
}
/* Funcao: removeBloco
*
* Processa linearmente (e uma unica vez) os carateres de uma dada sequencia de movimentos,
* removendo o bloco inicial delimitado pelo dado caractere.
*
* Parametros:
* str: sequencia de movimentos '+', '-', '*'
* c: caractere delimitador do bloco a ser removido
* targetStr: se str comeca com o caractere do parametro c, targetStr contera a sequencia obtida
* apos a remocao (de str) do bloco de movimentos da primeira posicao de str ate a
* segunda ocorrencia (inclusive) do caractere do parametro c. Se nao exsitir uma segunda
* ocorrencia do caracter do parametro c, targetStr deve conter a sequencia vazia.
*
* Retorno:
*
* 1, se o bloco foi removido
* 0, caso contrario
*
* Exemplo:
*
* char seq1[15] = "+-*+-*-*+++";
* char seq2[15] = "*+-*+-*-*+++";
* char seq3[15] = "*+-+--+++";
* char seq4[15];
*
* removeBloco(seq1, '*', seq4); // seq4 sera "+-*+-*-*+++"
* removeBloco(seq2, '*', seq4); // seq4 sera "+-*-*+++"
* removeBloco(seq3, '*', seq4); // seq4 sera "" (sequencia vazia)
*
*/
int removeBloco(char str[], char c, char targetStr[]) {
int blcRemov = 0, tamStr, k = 0;
if (str[0] == c) {//Se o primeiro elemento de str for igual a c:
blcRemov = 1;//Registra que isso aconteceu.
tamStr = strlen(str);//Armazena tamanho de str.
for (int i = 1; i < tamStr; i++)//Do próximo elemento até o final de str, compare para encontrar o próximo c em str.
if (str[i] == c)//Se encontrou, começa a partir daqui até o final de str a ser elementos de targetStr.
for (int j = i + 1; j < tamStr + 1; j++) {
targetStr[k] = str[j];
k++;
}
}
targetStr[k] = '\0';
return blcRemov;
}
/* Funcao: substituiPadrao
*
* Processa linearmente (e uma unica vez) os carateres de uma dada sequencia de movimentos,
* substituindo as ocorrencias de um dado padrao por um novo padrao.
*
* Parametros:
* str: sequencia de movimentos '+', '-', '*'
* padrao: subsequencia de movimentos, cujas ocorrencias devem ser substituidas pelo novoPadrao
* novoPadrao: subsequencia de movimentos que deve substituir cada ocorrencia do dado padrao
* targetStr: sequencia obtida apos a substituicao em str de todas as ocorrencias do dado padrao
* pelo novoPadrao
*
* Voce pode assumir que as subsequencias padrao e novoPadrao tem o mesmo tamanho.
*
* Retorno:
*
* 1, se as ocorrencias do dado padrao foram substituidas pelo novoPadrao
* 0, caso contrario
*
* Exemplo:
*
* char seq1[15] = "+*+-+*+-*++";
* char seq2[15];
* char seq3[15];
*
* char padrao[5] = "+*+"
* char novoPadrao[5] = "*-*"
*
* substituiPadrao(seq1, padrao, novoPadrao, seq2); // seq2 sera "*-*-*-*-*++"
* substituiPadrao(seq2, padrao, novoPadrao, seq3); // seq3 sera "*-*-*-*-*++"
*
*/
int substituiPadrao(char str[], char padrao[], char novoPadrao[], char targetStr[]) {
int k = 0, entrou = 0, subPadrao = 0, tamStr, tamPadrao, tamNovoPadrao;
tamStr = strlen(str);//Armazena os tamanhos destas variáveis.
tamPadrao = strlen(padrao);
tamNovoPadrao = strlen(novoPadrao);
for (int i = 0; i < tamStr; i++) {//Do início até o final de str, faça:
if (str[i] == padrao[0] && tamStr - i > tamPadrao - 1) {//Se o elemento (i) de str for igual ao primeiro elemento do padrão e houver possibilidade de ali conter um padrão:
for (int j = 1; j < tamPadrao; j++) {//Verifica se há o padrão. (Mesmo método de removePadrao())
if (str[i + j] != padrao[j]) {
entrou = 1;
break;
}
}
if (entrou == 0) {
i += tamPadrao - 1;
subPadrao = 1;
//A diferença de removePadrao() está aqui. A partir do momento que o padrão foi encontrado, percorre-se a string do novo padrão copiando estes elementos para targetStr.
for (int j = 0; j < tamNovoPadrao; j++) {
targetStr[k] = novoPadrao[j];
k++;
}
} else {//Caso contrário, não é o padrão, a string targetStr recebe o elemento de str em i.
targetStr[k] = str[i];
k++;
entrou = 0;
}
} else {//Caso contrário, não pode ser o padrão, a string targetStr recebe o elemento de str em i.
targetStr[k] = str[i];
k++;
}
}
targetStr[k] = '\0';
return subPadrao;
}