Autor da análise: natan_lima
Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=2849
Resumo
Este é um pouco difícil fugir da estória. É um problema de simulação, basta seguir os passos dados na descrição do problema.
Você tem um vetor de caracteres com 32768 posições, que começa com zero(zero mesmo, não '0') em todas as suas posições e um ponteiro inicialmente no zero que indica o começo do vetor.
A entrada é uma combinação de comandos na forma de caracteres, e o algoritmo tem apenas que simular esses comandos e imprimir algo quando o comando for de impressão.
Solução
A solução é simples de pensar mas meio chata de escrever, basta obedecer o que cada operação dentre {<,>,+,-,.,[,]} faz.
Sugiro que a leitura das linhas dadas no problema seja feita utilizando o fgets, pois fica mas fácil tratar o caso do caractere '%' onde é preciso ignorar as letras e/ou comandos que vem após ele nas linhas.
A parte mais difícil do problema são os laços, representados pelos caracteres {[,]}, pois quando eles aparecem, há a necessidade de ter o programa em brainfuck todo acessível, pois o laço não necessariamente fecha na mesma linha que abriu.
Para resolver este problema, usei uma string do c++ da seguinte maneira:
string program = "";
fgets(buffer,MAXL,stdin);
while(strcmp(buffer,"end\n") != 0){
int tam = strlen(buffer);
for(int i = 0;i < tam;i++){
if(islegal(buffer[i])) // islegal(x) devolve true se x pertence a {<,>,+,-,.,[,]}
if(buffer[i] == '%')
break;
}
fgets(buffer,MAXL,stdin);
}
Assim eu tinha contido na string program o programa do brainfuck inteiro, bastando a partir daí usar apenas a simulação.
Ainda assim o problema do laço continua sendo o mais difícil de resolver, uma maneira fácil para achar onde um determinado laço fecha é com uma pilha. quando vier um '[' você empilha, enquanto que quando vier um ']' você desempilha, até o momento que venha um ']' e sua pilha fique vazia, neste momento você achou onde seu laço fecha.
Os outros comando são mais fáceis de implementar, e deixo a cargo do leitor.
Dica:
comando brainfuck , equivalente em C
> , ++ptr;
< , --ptr;
+ , ++*ptr;
- , --*ptr;
. , putchar(*ptr);
[ , while (*ptr) {
] , }
Com um switch case o programa fica até bonitinho.
Boa sorte.
Problemas relacionados:
http://br.spoj.pl/problems/BRAIN/
Testes
Entrada
Aqui tem exemplo de entrada para brainfuck de verdade, para mudar um pouco para o seu programa ler não é muito difícil.
Discuta o problema
Adorei a citação de um problema parecido com este!
Parabéns pela iniciativa.
Tentei melhorar um pouco!
=P
Critique partes específicas que eu tento melhorar o texto.
Alguém andou lendo o Guidorizzi :p