Martin VIDAL
22/12/2024

//////////////////////////////////////////////
///Interpréteur d'évaluations arithmétiques///
//////////////////////////////////////////////


Arborescence du projet :
.
├── Doxyfile
├── Graph
│   ├── Graph.cc
│   └── Graph.h
├── Main.cc
├── Parser.cc
├── Parser.h
├── Queue
│   ├── ChainedQueue.h
│   └── QueueNode.h
├── README.txt
├── Stack
│   ├── ChainedStack.h
│   └── StackNode.h
└── makefile


Si vous souhaitez avoir la documentation du code en détail, 
il faut installer "Doxygen" avec la commande suivante : 
    
    Linux : "sudo apt install doxygen".
    MacOS : "brew install doxygen".

Ensuite créer le répertoire "build/doc" : 
    
    "mkdir -p build/doc"

Pour générer la documentation :

    "doxygen Doxyfile"

Une fois la documentation générée, il vous suffit de vous rendre dans "build/doc/html/index.html",
et ouvrir le fichier "index.html". Vous allez normalement être dans votre navigateur sur la documentation.

    "x-www-browser build/doc/index.html"


Problématiques rencontrées :
    - Saisie par les utilisateurs dans le terminal : problème invisible avec "std::cin", les expressions se stockaient mal,
      du coup seul possibilité d'utiliser le calculateur par le biais d'un tableau de string.

    - Quand j'ai voulu "templater" mes structures de données (pile chaînée / file chaînée), j'ai trouvé comme seule
      alternative de mettre à la fois la déclaration des méthodes et leur définition dans le fichier d'entête.

    - Pour ordonner mes expressions avec un graphe, déjà trouver la méthode pour décider de quelle expression mettre en premier,
      et ensuite j'ai eu des problèmes de fuite mémoire avec mon opérateur "=". 


Pour essayer le calculateur :

(A faire dans le fichier Main.cc)

1) Créer une liste d'expressions

    ///////////////////////////////////////////////////////////////////////////////////////////////////////
    ///Attention: pour affecter un unique chiffre / nombre à une variable, il ne faut pas le parenthéser///
    ///                                   Exemple : "a = 33"                                            ///
    ///       Sinon, tout le reste doit lui être parenthésé correctement (une erreur sera lancée)       ///
    ///////////////////////////////////////////////////////////////////////////////////////////////////////

    a) Créer un tableau d'expressions à la volée : 
        
        string tabExp[] = {
            "a = ((5*59)+(3-(5*97)))",
            "b = ((66*0)%3)",
            "e = 699",
            "k = ((a+9)*(686/8))",
            "d = ((k*k)-(5*b))",
            "z = ((b-(d/e))+8)"
        };

        ou bien :

        string tabExp[] = {
            "d = (b + c * 2)",
            "a = (5 + 3)",
            "c = (a * 2)",
            "b = (a - 4)",
            "e = (d / 2)"
        };
    
    b) Créer un objet Parser avec votre tableau créé précédemment et sa taille (son nombre d'élément à l'intérieur) :
       !-- Si la taille ne correspond pas, le programme plantera --!
        Parser expression(tabExp, 6);
    
    c) Appeler la méthode "evaluateExpressions()" :

        expression.evaluateExpressions();

Une fois le fichier Main.cc complété sauvegardez et lancez dans votre terminal la commande suivante :

    "make && ./a.out"

Cette commande permet de compiler le projet, générer les fichiers objets et exécuter l'exécutable "a.out".


Explications de l'algorithme générale :

    1) Stockage des expressions données par l'utilisateur.
    2) Trouver les variables différentes et créer un graphe da la taille du nombre de variables.
    3) Analyser chaque expression pour trouver les dépendances entre les expressions.
    4) Fermeture transitive du graphe.
    5) Détermination de l'ordre dans lequel vont être évaluées les expressions.
    6) Evaluation de chaque expression.
    7) Affichage du résultat.


Point sur les algorithme les plus complexes à mon sens et qui méritent une explication : 


    Analyser chaque expression et trouver les dépendances :

    - Je trouve la position du signe "=" dans l'expression.
    
    - Si "=" trouvé alors :
        - Je récupère la variable à laquelle on affecte l'expression
        
        - Si cette variable est bien mappée :
            - Je récupère son indice
        
        - J'associe l'indice de la variable à l'expression en cours d'analyse
        - Je parcours la partie droite de mon expression (Tout ce qui se trouve après le "=") :
            - Si mon charactère est une lettre :
                - Je vérifie si ce caractère est bien mappé :
                    - Je récupère son indice.
                - Si j'ai un indice valide :
                    - J'ajoute un arc dans mon graphe entre la variable avant le signe "=" et le caractère en cours d'analyse.


    Fermeture transitive du graphe : 

    - Je crée une copie du graphe initial dans trois variables différentes : result | previous | poweredGraph.
    - Je définis une variable power à 2 pour commencer à calculer les puissances du graphe.
    - Je définis une variable sameGraph à false pour vérifier si le graphe précédent est identique au graphe actuel.

    - Tant que sameGraph est false et que power est inférieur ou égal au nombre de sommets du graphe :
        - Je calcule la puissance power du graphe result et je stocke le résultat dans poweredGraph.
        - J'ajoute les valeurs de la matrice d'adjacence de poweredGraph à la matrice d'adjacence de result.
        - Si une valeur dans result dépasse 1
            - Je la ramène à 1 pour garantir que la matrice reste une matrice booléenne.
        - Je vérifie si le graphe result est identique au graphe previous en utilisant la méthode areSameGraph.
        - Si les graphes sont identiques
            - Je mets sameGraph à true.
        - Je mets à jour previous avec le graphe result.
        - J'incrémente power de 1.
    - Une fois la boucle terminée, je mets à jour le graphe courant avec le graphe result.

    
    Tri topologique des expressions :
    
    - Si le graphe est cyclique
        - Je lance une exception car le tri topologique est impossible sur un graphe cyclique.
    
    Calcul les degrés entrants :
    - Je crée un tableau inDegree pour stocker le nombre de degrés entrants de chaque sommet.
    - Pour chaque sommet i du graphe :
        - J'initialise inDegree[i] à 0.
        - Pour chaque sommet j du graphe :
        - Si il existe une arête de j vers i (c'est-à-dire si adjacencyMatrix[j][i] == 1)
            - J'incrémente inDegree[i].
    
    Initialisation de la file :
    - Je crée une file pour stocker les sommets avec un degré entrant de 0.
    - Je définis deux indices queueStart et queueEnd pour gérer les opérations de la file.
    - Pour chaque sommet i du graphe :
    - Si inDegree[i] est égal à 0
        - J'ajoute i à la file en le plaçant à la position queueEnd et j'incrémente queueEnd.

    - Je crée un tableau pour stocker l'ordre topologique des sommets.
    - Je définis une variable pour suivre le nombre de sommets dans l'ordre topologique.
    - Tant que la file n'est pas vide :
        - Je retire un sommet u de la file en le prenant à la position queueStart et j'incrémente queueStart.
        - J'ajoute u à topoOrder à la position orderSize et j'incrémente orderSize.
        - Pour chaque sommet v du graphe :
            - Si il existe une arête de u vers v (c'est-à-dire si adjacencyMatrix[u][v] == 1)
                - Je décrémente inDegree[v].
            - Si inDegree[v] devient 0
                - J'ajoute v à la file en le plaçant à la position queueEnd et j'incrémente queueEnd.

    - Je retourne le tableau topoOrder contenant les sommets dans l'ordre topologique.

    
    Ordonencement des expressions :
    
    - J'appelle la méthode "topologicalSort()" (détaillée juste au dessus) sur le graphe graphe pour obtenir l'ordre topologique des sommets.
    - Je stocke la taille de l'ordre topologique dans une variable
    - Je stocke le retour de la méthode "topologicalSort()" dans un tableau

    - Pour chaque sommet dans topoOrder :
        - Je récupère l'indice de la variable varIndex.
        - Je récupère la variable correspondante variable en utilisant le tableau varMapping.
        - Si varIndex est valide (compris entre 0 et 25) :
            - J'empile l'expression correspondante sur la pile stack.


    Evaluation des expressions :

    - Je crée une pile pour stocker les opérandes.
    - Je crée une pile pour stocker les opérateurs.

    - Je parcours chaque caractère de l'expression à évaluer :

        - Si le caractère courant est un chiffre (isDigit)
            - Je commence à construire le nombre entier.
            - Je crée une variable pour récupérer mon chiffre / nombre initialisée à 0.
            - Tant que le caractère courant est un chiffre
                - Je multiplie par 10 ma variable et j'ajoute la valeur numérique du caractère courant.
                - J'avance dans l'expression jusqu'à ce que je rencontre un caractère qui n'est pas un chiffre.
            - J'empile le nombre entier construit dans la pile des opérandes.

        - Si le caractère courant est une lettre (isAlpha)
            - Je calcule l'indice de la variable en soustrayant 'a' du caractère courant.
            - Si l'indice est hors des limites du tableau des variables
                - Je lance une exception.
            - Je récupère la valeur de la variable à partir du tableau variables.
            - J'empile la valeur de la variable dans la pile.

        - Si le caractère courant est un opérateur (+, -, *, /, %)
            - J'ajoute ce caractère la pile des opérateurs.

        - Si le caractère courant est une parenthèse fermante ")"
            - Je récupère les deux premières opérandes dans ma pile.
            - Je récupère le premier opérateur dans ma pile.
            - J'initialise une variable pour stocker le résultat
            - Switch en fonction de l'opérande :
                - Calcul du résultat avec "2eme nombre dépilé" <opérateur> "1er nombre dépilé"
                (Si on le fait dans l'ordre inverse, les opérations qui ne sont pas commutatives vont poser des problèmes)
            - J'empile le résultat dans la pile des opérandes.

    Une fois que mon expression est totalement parcourue :

    - Si la pile des opérandes n'est pas vide :
        - J'affecte à la variable avant le signe "=" le résultat (sommet de la pile des opérandes)

    - Je retourne le résultat