What the Brainfuck !

On nous fourni:

• trois entiers: L (nombre de lignes du programme Brainfuck), S (taille du tableau de cellules), N (nombre d’entrées pour le programme);
• L lignes contenant le code du programme Brainfuck.
• N lignes contenant des entiers, qui sont les entrées du programme Brainfuck.

L’objectif de ce problème est de créer un interpréteur de Brainfuck, un langage minimaliste composé de seulement 8 instructions. Il fonctionne sur une mémoire linéaire et un pointeur, qui navigue entre différentes cellules pour modifier leurs valeurs. Ce programme devra donc exécuter un code Brainfuck, gérer les entrées/sorties, et prendre en compte les erreurs potentielles. Tout d’abord, intéressons nous au modèle Brainfuck, on verra aussi par la suite les fameuses 8 instructions qui le compose, mais tout d’abord intéressons nous au principe du modèle Brainfuck. Brainfuck repose sur trois éléments principaux :

• Un tableau de S cellules, initialisées à 0, qui stocke des valeurs modifiables.
• Un pointeur, initialisé à la première cellule, qui se déplace de gauche à droite.
• Un programme, constitué d’une séquence de 8 instructions qui permettent de manipuler la mémoire et d’effectuer des opérations.

Concernant ces fameuses instructions, les voici:

• > : Déplace le pointeur vers la cellule suivante.
• < : Déplace le pointeur vers la cellule précédente.
• + : Incrémente la valeur de la cellule pointée.
• - : Décrémente la valeur de la cellule pointée.
• . : Affiche le caractère ASCII correspondant à la valeur de la cellule.
• , : Stocke une entrée utilisateur dans la cellule pointée.
• [ : Si la cellule pointée contient `0`, saute jusqu’au `]` correspondant.
• ] : Si la cellule pointée contient une valeur différente de `0`, retourne au `[` correspondant.

On doit donc interpréter l’entrée qu’on nous fourni ce qui implique qu’il faut gérer les erreurs. On doit notamment gérer les errerus suivantes:

• "SYNTAX ERROR" : Si [ et ] ne sont pas équilibrés.
• "POINTER OUT OF BOUNDS" : Si le pointeur dépasse les limites du tableau.
• "INCORRECT VALUE" : Si une cellule dépasse 255 ou tombe sous 0.

Je dois donc:

• Lire les entrées du programme: paramètres initiaux, code Brainfuck et entrées utilisateur.
• Vérifier la syntaxe du code avant son exécution.
• Interpréter les instructions pour manipuler la mémoire et gérer les boucles correctement.
• Afficher la sortie générée ou signaler une erreur si nécessaire.

Le programme doit afficher un message d’erreur si nécessaire ou la chaine de caractères obtenus s’il n’y a pas d’erreurs.

J’ai structuré ta réflexion en plusieurs étapes claires pour répondre à la consigne. D’abord, je récupère et prépare les données nécessaires, en combinant le programme Brainfuck et les entrées utilisateur. Ensuite, je vérifie la syntaxe avant l’exécution pour éviter les erreurs liées aux boucles. Une fois cette validation faite, j’interprète le programme en suivant les instructions une par une, en manipulant la mémoire et le pointeur. À chaque étape critique, je contrôle si une erreur est détectée, interrompant immédiatement l’exécution et affichant le message d’erreur approprié. Enfin, si tout se déroule correctement, je restitue le résultat du programme en affichant la sortie générée.

Je commence d’abord par récupérer les différentes entrées: L, S et N. Ensuite, le programme vient concaténer les lignes du programme Brainfuck dans une seule chaîne program en utilisant strcat(), ce qui permet de gérer un code multi-lignes comme une seule séquence d’instructions. Vient ensuite la partie de vérification qui vérifie l’équilibre des crochets ([ ]) via la fonction verifSyntaxe(). Cette fonction parcourt le programme et compte le nombre de [ et ]. Si à un moment balance devient négatif ou n’est pas nul à la fin, il affiche "SYNTAX ERROR" et arrête immédiatement l’exécution.

On vient par la suite initialiser l’interpréteur en réalisant les tâches suivantes:

• Création du tableau mémoire cible[S], initialisé à 0.
• Définition du pointeur pointeur, qui commence à 0 et évolue selon > et <.
• Lecture des entrées utilisateur stockées dans inputs[N]. Chaque valeur est vérifiée (0 ≤ inputs[i] ≤ 255), sinon "INCORRECT VALUE" est affiché.

L’interprétation grâce au programme Brainfuck s’effectue via une boucle while (index < longueur), où index parcourt chaque caractère de program. Selon program[index], différentes opérations sont effectuées :

• Modification des cellules mémoire:
  • + : Incrémente la cellule pointée (cible[pointeur]++). Si elle dépasse 255, affiche "INCORRECT VALUE";
  • - : Décrémente la cellule (cible[pointeur]--). Si elle devient négative, affiche "INCORRECT VALUE".
• Déplacement du pointeur:
  • > : Déplace le pointeur vers la droite (pointeur++). S’il dépasse S-1, affiche "POINTER OUT OF BOUNDS".
  • < : Déplace le pointeur vers la gauche (pointeur--). S’il descend sous 0, affiche "POINTER OUT OF BOUNDS".
• Entrées et sorties:
  • . : Convertit la valeur de la cellule en caractère ASCII et l’ajoute à sortie.
  • , : Prend un entier depuis inputs[] et le stocke dans la cellule pointée.
• Gestion des boucles ([ et ]);
  • [ : Si la cellule pointée vaut 0, il recherche le ] correspondant via trouverCrochet(), et saute l’exécution.
  • ] : Si la cellule pointée est différente de 0, il remonte au [ correspondant.

À la fin du programme, on effectue l’affichage du résultat si aucune erreur n’a déjà été affiché, sortie est donc affiché pour montrer le texte généré par le programme Brainfuck.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define SIZE 1025

int trouverCrochet(char texte[], int indice, int longueur) {
    int profondeur = 1;
    while (++indice < longueur) {
        if (texte[indice] == '[') profondeur++;
        else if (texte[indice] == ']') profondeur--;
        if (profondeur == 0) return indice;
    }
    return -1;
}

void interpreteur(char texte[], int longueur, int S, int N) {
    unsigned char cible[S];
    memset(cible, 0, S * sizeof(unsigned char));
    int pointeur = 0, index = 0;
    char sortie[255] = "";
    char temp[10];
    int inputs[N];
    for (int i = 0; i < N; i++) {
        scanf("%d", &inputs[i]);
        if (inputs[i] < 0 || inputs[i] > 255) {
            printf("INCORRECT VALUE\n");
            return;
        }
    }
    int input_index = 0;
    while (index < longueur) {
        switch (texte[index]) {
            case '+':
                if (cible[pointeur] == 255) {
                    printf("INCORRECT VALUE\n");
                    return;
                }
                cible[pointeur]++;
                break;
            case '-':
                if (cible[pointeur] == 0) {
                    printf("INCORRECT VALUE\n");
                    return;
                }
                cible[pointeur]--;
                break;
            case '>':
                pointeur++;
                if (pointeur >= S) {
                    printf("POINTER OUT OF BOUNDS\n");
                    return;
                }
                break;
            case '<':
                pointeur--;
                if (pointeur < 0) {
                    printf("POINTER OUT OF BOUNDS\n");
                    return;
                }
                break;
            case '.':
                sprintf(temp, "%c", cible[pointeur]);
                strcat(sortie, temp);
                break;
            case ',':
                if (input_index >= N) {
                    printf("INCORRECT VALUE\n");
                    return;
                }
                cible[pointeur] = (unsigned char)inputs[input_index++];
                break;
            case '[':
                if (cible[pointeur] == 0) {
                    int jump = trouverCrochet(texte, index, longueur);
                    if (jump == -1) {
                        printf("SYNTAX ERROR\n");
                        return;
                    }
                    index = jump;
                }
                break;
            case ']':
                if (cible[pointeur] != 0) {
                    int back = index;
                    int profondeur = 1;
                    while (back-- >= 0) {
                        if (texte[back] == ']') profondeur++;
                        else if (texte[back] == '[') profondeur--;
                        if (profondeur == 0) {
                            index = back - 1;
                            break;
                        }
                    }
                    if (profondeur != 0) {
                        printf("SYNTAX ERROR\n");
                        return;
                    }
                }
                break;
        }
        index++;
    }
    printf("%s\n", sortie);
}

bool verifSyntaxe(char texte[], int longueur) {
    int balance = 0;
    for (int i = 0; i < longueur; i++) {
        if (texte[i] == '[') balance++;
        else if (texte[i] == ']') balance--;
        if (balance < 0) return false;
    }
    return balance == 0;
}

int main() {
    int L, S, N;
    scanf("%d%d%d", &L, &S, &N); fgetc(stdin);
    char program[2048] = "";
    for (int i = 0; i < L; i++) {
        char line[SIZE];
        scanf("%[^\n]", line); fgetc(stdin);
        strcat(program, line);
    }
    if (!verifSyntaxe(program, strlen(program))) {
        printf("SYNTAX ERROR\n");
        return 0;
    }
    interpreteur(program, strlen(program), S, N);
    return 0;
}