[Exercices] Venez vous entraîner !

// BrainFuck.h
// par : MatteX
// 16 juillet 2008

/** Historique
 * 22 juillet 2008 :
 *   - AJOUT : Une constante globale TAILLE contenant la taille du tableau d'exécution.
 *	 - AJOUT : Une méthode valider_code() permettant de vérifier que le code fournis est un code BrainFuck valide.
 *   - MODIFICATION : Déplacement de tableau respecte la norme de warping au début 
 *       et à la fin du tableau d'exécution. Pour éviter les dépassement de tableau.
 *   - MODIFICATION : La méthode Préparer se nomme maintenant Initialisation
 *   - MODIFICATION : Les méthodes Interpréter et Initialisation prennent 
 *       un paramètre supplémentaire : const std::string & code
 *   - MODIFICATION : Intitialisation() ne lance plus d'exception si le code n'est pas valide. 
 *       Les caractère non valides seront simplement ignorés à l'exécution
 *   - RETRAIT : La méthode AddCode a été remplacée par un paramètre de la méthode Interpréter
 *   - RETRAIT : La variable membre m_code n'existe plus.
 *   - RETRAIT : L'opérateur >> n'est plus viable.
 */

#ifndef __EXERCICEMIJUILLET2008_MATTEX_BRAINFUCK_H__
#define __EXERCICEMIJUILLET2008_MATTEX_BRAINFUCK_H__

#include <istream>
#include <ostream>
#include <map>
#include <string>


// Interprète un code BrainFuck
class BrainFuck
{
    typedef std::string::const_iterator iterateur;
    typedef unsigned char octet_t;

    // Contient la position de début et de fin d'une paire d'opérateur de boucle.
    // Sera initialisé au début de la méthode Interpréter()
    std::map<iterateur,iterateur> m_blocs;

    // Valide le code et les boucles.
    void Initialisation( const std::string & code );

    // Interprete les boucles avec leur condition d'arrêt
    void Boucle( iterateur & it, const octet_t * const p ) const;

public:
   
    // Execute le code fournis et gère les entrée/sortie lorsque nécessaire
    void Interpreter( std::ostream & ostr, const std::string & code );
};

#endif // #ifndef __EXERCICEMIJUILLET2008_MATTEX_BRAINFUCK_H__

// BrainFuck.cpp
// par : MatteX
// 16 juillet 2008

#include <algorithm>
#include <iostream>
#include <limits>
#include <stack>
#include <string>
#include <stdexcept>

#undef max

#include "BrainFuck.h"

// ----------------------------------------------------------------------------------------------

// Liste des caractères de début et fin de boucles.
const std::string BOUCLES = "[]";
// Taille du tableau d'exécution
const int TAILLE = 30000;

// ----------------------------------------------------------------------------------------------

void BrainFuck::Interpreter( std::ostream & ostr, const std::string & code )
{
    // Préparation de l'interpréteur
    Initialisation( code );

    // Création du buffer de 30 000 octets requis par la norme BrainFuck
    // Le Tableau d'exécution
    octet_t buffer[ TAILLE ] = { 0 };
    octet_t * p = buffer;
    
    // Interprétation des opérateurs
for ( iterateur it_code = code.begin(); it_code != code.end(); ++it_code )
    {
        switch (*it_code)
        {
        case '+':
            ++(*p);
            break;

        case '-':
            --(*p);
            break;

        case '>':
            if ( ++p >= buffer + TAILLE )
                p = buffer;
            break;

        case'<':
            if ( --p <= buffer - 1 )
                p = buffer + (TAILLE - 1);
            break;

        case'.':
            ostr << static_cast<std::ostream::char_type>( *p );
            break;

        case',' :
            *p = static_cast<octet_t>( std::cin.get() );
            std::cin.clear();
            std::cin.ignore( std::numeric_limits<std::streamsize>::max(), std::cin.widen( '\n' ) );
            break;

        case '[':
        case ']':
            Boucle( it_code, p );
            break;

        default:   // Si le caractère n'est pas un opérateur BrainFuck, il est tout simplement ignoré.
            break;
        }
    }
}

// ----------------------------------------------------------------------------------------------

// Valide le code et prépare l'interpréteur.
void BrainFuck::Initialisation( const std::string & code )
{
    std::stack<iterateur> pile;
    iterateur it = std::find_first_of( code.begin(), code.end(), BOUCLES.begin(), BOUCLES.end() );

    m_blocs.clear();

    while( it != code.end() )
    {
        if(pile.empty() && *it != *BOUCLES.begin())
        {
            throw std::runtime_error( "Il manque un ou plusieurs debuts de boucles." );
        }
        else if( (pile.empty()&& *it == *BOUCLES.begin()) || *pile.top() == *it )
        {
            pile.push( it );
        }
        else
        {
            m_blocs[ pile.top() ] = it;
            pile.pop();
        }

        it = std::find_first_of( it + 1, code.end(), BOUCLES.begin(), BOUCLES.end() );
    }

    if( !pile.empty() )
        throw std::runtime_error( "Il manque une ou plusieurs fins de boucles." );

}

// ----------------------------------------------------------------------------------------------

// Effectue les opérations de début et fin de boucles.
void BrainFuck::Boucle( iterateur & it, const octet_t * const p ) const
{
    typedef std::map<iterateur, iterateur>::const_iterator map_iterator;
    
    map_iterator bit;

    bit = m_blocs.find( it );

    // Si l'opérateur en cours est un début de boucle, nous devons tester la condition.
    if( bit != m_blocs.end() )
    {
        // Teste la condition de fin de boucle;
        if( ((*bit->first) == '[' && *p == 0) || (((*bit->first) == ']' && *p != 0)) )
            it = bit->second;
    }
    else
    {
        // L'opérateur est une fin de boucle ! Nous devons trouver le début de boucle associé et y retourner.
        for( map_iterator finder = m_blocs.begin(); finder != m_blocs.end(); ++finder )
        {
            if( finder->second == it )
            {
                it = finder->first - 1;
                break;
            }
        }
    }
}

/** main.cpp
 *
 * PROJET : ExerciceMiJuillet2008
 *	    Dans le cadre du sujet Exerices en C++ sur le Site du Zéro
 *	    -> http://www.siteduzero.com
 *      -> http://www.siteduzero.com/forum-83-257993-2746925-exercices-venez-vous-entrainer.html#r2746925
 *
 *	Merci à Nanoc pour l'idée originale de l'Exercice
 *
 * Par MatteX
 * Fait le 16 juillet 2008 (Une grosse heure)
 */

#include <ctime>
#include <fstream>
#include <iostream>
#include <sstream>
#include <string>
#include <stdexcept>

#include "BrainFuck.h"

// ----------------------------------------------------------------------------------------------

struct timespan
{
    time_t m_t;

    timespan( time_t t ) : m_t( t ) {}

    friend std::ostream & operator<< ( std::ostream & ostr, const timespan & ts )
    {
        std::tm * temps = std::localtime( &ts.m_t );

        if( ts.m_t >= 3600 )
            ostr << temps->tm_hour <<  "h ";

        if( ts.m_t >= 60 )
            ostr << temps->tm_min <<  "m ";

        if( ts.m_t >= 1 )
            ostr << temps->tm_sec <<  "s.";

        if( ts.m_t == 0 )
            ostr << "Moins d'une seconde.";

        return ostr;
    }
};

// ----------------------------------------------------------------------------------------------

void LireFichier( const std::string & chemin, std::string & cpntenu );

// ----------------------------------------------------------------------------------------------

int main( int argc, char* argv[] )
{
    BrainFuck bf;
    std::string code;

    std::time_t temps = 0;

    std::cout << "=========== Interpréteur BrainFuck ===========\n   Par : MatteX     version : 1.0 16.07.2008\n\n------------- Sortie du programme ------------\n"; 

    try
    {
        if( argc <= 1 )
            throw std::runtime_error( "Vous devez passer un fichier de code source BrainFuck en argument." );

        LireFichier( argv[ 1 ], code );

        temps = std::time( 0 );
        bf.Interpreter( std::cout, code );
    }
    catch( const std::exception & ex )
    {
        std::cerr << "ERREUR : " << ex.what() << std::endl;
    }

    if( temps != 0 )
        temps = std::time( 0 ) - temps;
   
    std::cout << "----------- Interprétation terminée ----------\nTemps d'exécution : " << timespan( temps ) << std::endl;

    return 0;
}

// ----------------------------------------------------------------------------------------------

void LireFichier( const std::string & chemin, std::string & contenu )
{
    std::ostringstream oss;
    std::ifstream ifstr( chemin.c_str() );

    if( !ifstr )
        throw std::runtime_error( ("Impossible d'ouvrir : " + chemin).c_str()  );

    if( !(oss << ifstr.rdbuf()) )
        throw std::runtime_error( "Impossible de lire l'intégralité du fichier." );

    contenu = oss.str();
}

#include <iostream>
#include <fstream>
#include <stdexcept>

#include "brainfuck.h"

using namespace std;

int main(int argv, char ** argc)
{
	try
	{
		if(argv < 2) throw runtime_error("Fichier d'entrée non precise");
		
		ifstream is;
		is.open(argc[1], ifstream::in);
		
		if(is.fail()) throw runtime_error("Impossible de trouver le fichier precise");
		
		nsBrainfuck::Brainfuck Resolv(is);
		is.close();
		
		Resolv.Exec();		
	}
	catch(exception & e)
	{
		cout << e.what() << endl;
	}
	
    	return 0;
}

#ifndef __BRAINFUCK_H__
#define __BRAINFUCK_H__

#include <iostream>
#include <stack>

namespace nsBrainfuck
{
    /**
	* La classe Brinfuck permet d'analyser un programme en brainfuck, afin de l'interpréter
	*/
    class Brainfuck
    {
      public:
        typedef unsigned char Octet;
	typedef std::string::iterator Iterator_code; 
	typedef Octet * Iterator_memory;

        Brainfuck(std::istream &, unsigned Taille = 30000);
	~Brainfuck();
        void Exec();

      protected:
        void FonctionIncrementer();
        void FonctionDecrementer();
        void FonctionDebut();
        void FonctionFin();
        void FonctionDeplacerGauche();
        void FonctionDeplacerDroite();
        void FonctionEntree();
        void FonctionSortie();

	Iterator_code             m_Car;
        std::string               m_Code;
	std::stack<Iterator_code> m_QWhile;

        Octet *                   m_Memoire;
        Iterator_memory           m_Current;
	unsigned                  m_Zero;
	unsigned                  m_Taille;
    };
}

#endif /* __BRAINFUCK_H__ */

#include <sstream>
#include <iostream>
#include <stdexcept>

#include "brainfuck.h"

#define BRAINFUCK nsBrainfuck::Brainfuck

using namespace std;

/**
  * Constructeur.
  * Permet d'initialiser le fichier brainfuck à analyser et la mémoire brainfuck
  * @param Flux représente le fichier à analyser
  */	
BRAINFUCK::Brainfuck(istream & Flux, unsigned Taille /* = 30000 */)
    : m_Zero(0), m_Taille(Taille)
{
	// On récupère le contenu du fichier afin de l'insérer dans un string (il est plus simple
	// de procéder de cette manière, plutôt que d'effectuer une interprétation
	// directe)
	ostringstream Buffer;
	Buffer << Flux.rdbuf();
	m_Code = Buffer.str();
	
	// On créé un tableau de taille m_Taille
	m_Current = m_Memoire = new Octet[m_Taille];	
}

/**
  * Constructeur.
  * Detruit la mémoire brainfuck
  */	
BRAINFUCK::~Brainfuck()
{
	delete [] m_Memoire;
}

/**
  * Analyse le code brainfuck, et affiche le résultat à l'écran
  */
void BRAINFUCK::Exec()
{
    	for(unsigned i(0); i < m_Taille; ++i) m_Memoire[i] = 0;
	for(m_Car = m_Code.begin(); m_Car != m_Code.end(); ++m_Car)
    	{
        	// Cette condition permet de gérer le cas où on aurait rencontré un '[' avec la valeur pointée valant 0:
		// elle passe toutes les instructions contenues dans la boucle, ainsi que les autres boucles qu'elle pourrait contenir.
		if(m_Zero) 
		{
			if(*m_Car == '[') ++m_Zero;
			else if(*m_Car == ']') --m_Zero;
		}
		else
		{	
			// Ii on traite les différentes instructions possibles.
			switch(*m_Car)
			{
		        	case '+': FonctionIncrementer();    break;
		        	case '-': FonctionDecrementer();    break;
		        	case '.': FonctionSortie();         break;
		        	case '>': FonctionDeplacerDroite(); break;
		        	case '<': FonctionDeplacerGauche(); break;
		        	case ',': FonctionEntree();         break;
		        	case '[': FonctionDebut();          break;
		        	case ']': FonctionFin();            break;
		    	}
		}

    	}
	if(m_QWhile.size()) throw runtime_error("Erreur lors de l'execution du programme:\ncaractere ']' manquant");
	cout << flush;
}

/**
  * Incrémente de 1 la valeur pointée
  */
void BRAINFUCK::FonctionIncrementer()
{
    ++(*m_Current);
}

/**
  * Décrémente de 1 la valeur pointée
  */
void BRAINFUCK::FonctionDecrementer()
{
    --(*m_Current);
}

/**
  * Permet de gérer la début d'une boucle, lorsqu'on rencontre le caractère '['
  */
void BRAINFUCK::FonctionDebut()
{
	// On regarde si la valeur pointée vaut 0, si c'est le cas il faut sauter cette boucle: la valeur
	// de m_Zero est incrémentée, ce qui permettra de sauter toutes les instructions que contient la boucle.
    	if(*m_Current == 0) ++m_Zero;
	// Si elle ne vaut pas 0, alors on ajoute la position du début de la boucle à la pile, ce qui permettra de pouvoir y revenir
	// plus tard si nécessaire.
	else m_QWhile.push(m_Car);
}

/**
  * Permet de gérer la fin de la boucle, lorsqu'on rencontre le caractère ']'
  */
void BRAINFUCK::FonctionFin()
 {  
	if(m_QWhile.empty()) throw runtime_error("Erreur lors de l'execution du programme:\ncaractere '[' manquant");
	// On regarde si la valeur courrante vaut 0, si c'est le cas, on enlève la position du début de la boucle afin 
	// de ne pas pouvoir y revenir.
	if(*m_Current == 0) m_QWhile.pop();
	// SI elle ne vaut pas 0, alors on revient au début de la boucle grace à la valeur contenue dans la pile.
	// On prend la dernière position insérée afin de gérer les cas où il y aurait plusieurs boucles dans une seule.
	else m_Car = m_QWhile.top();
}

/**
  * Demande un caractère à l'utilisateur
  */
void BRAINFUCK::FonctionEntree()
{
    	cout << flush;
	*m_Current = cin.get();
}

/**
  * Affiche le caractère courrant à l'écran
  */
void BRAINFUCK::FonctionSortie()
{
    cout << *m_Current;
}

/**
  * Déplace le pointeur mémoire vers la gauche
  */
void BRAINFUCK::FonctionDeplacerGauche()
{
	if(m_Current != m_Memoire) --m_Current;
	else m_Current = m_Memoire + m_Taille - 1;
}

/**
  * Déplace le pointeur mémoire vers la droite
  */
void BRAINFUCK::FonctionDeplacerDroite()
{
	if(m_Current != m_Memoire + m_Taille - 1) ++m_Current;
	else m_Current = m_Memoire;
}

#undef BRAINFUCK