Calculer en notation polonaise inverse

Les objectifs de cet exercice sont de :

• calculer une expression arithmétique en notation polonaise inverse (RPN), c'est-à-dire de type "5 3 2 + *",
• transformer une expression arithmétique RPN en expression infixe, c'est-à-dire "5 * (3 + 2)".

1. 1

   Indice

   Diviser la chaîne par des espaces et mapper chaque élément vers un type de jeton selon sa valeur.
   Écrire une fonction expr_to_list : string -> token list qui renvoie la liste de lexèmes (token) correspondant à une expression arithmétique séparée par des espaces. Par exemple expr_to_list "5 2 3 + x" renvoie [TKNum 5; TKNum 2; TKNum 3; TKOp "+"; TKOp "x"].
2. 2

   Indice

   Parcourir la liste de jetons en maintenant une pile et appliquer les opérateurs sur les deux éléments du haut.
   Écrire une fonction compute : token list -> int qui calcule la valeur d'une expression arithmétique en notation polonaise inverse à l'aide d'une pile. Par exemple compute [TKNum 5; TKNum 2; TKNum 3; TKOp "+"; TKOp "x"] renvoie 25.
3. 3

   Indice

   Enchaîner la fonction de parsing avec la fonction de calcul et vérifier le résultat produit.
   Tester les fonctions précédentes sur l'expression 5 2 3 + x et vérifier que le calcul produit bien le résultat attendu.
4. 4

   Indice

   Utiliser une pile pour accumuler les sous-arbres et combiner les deux nœuds supérieurs lors de la lecture d'un opérateur.
   Écrire une fonction build_atree_from_rpn : token list -> atree qui renvoie l'arbre syntaxique abstrait correspondant à une expression en notation polonaise inverse. Par exemple build_atree_from_rpn [TKNum 5; TKNum 2; TKNum 3; TKOp "+"; TKOp "x"] renvoie Node("x", Num 5, Node("+", Num 2, Num 3)).
5. 5

   Indice

   Associer un entier à chaque opérateur en utilisant un motif de correspondance sur le nœud de l'arbre.
   Écrire une fonction priority : atree -> int qui calcule la priorité d'un nœud opérateur (1 pour + et -, 2 pour x et /, 0 sinon). Par exemple priority (Node("+", Num 1, Num 2)) renvoie 1.
6. 6

   Indice

   Parcourir récursivement l'arbre syntaxique et ajouter des parenthèses autour des enfants dont la priorité est inférieure.
   Écrire une fonction rpn_to_infix : token list -> token list qui renvoie la liste des lexèmes d'une expression en notation infixe, en ajoutant les parenthèses nécessaires selon les priorités. Par exemple rpn_to_infix [TKNum 5; TKNum 2; TKNum 3; TKOp "+"; TKOp "x"] renvoie [TKNum 5; TKOp "x"; TKOp "("; TKNum 2; TKOp "+"; TKNum 3; TKOp ")"].
7. 7

   Indice

   Parcourir la liste de jetons et accumuler leurs représentations textuelles dans une chaîne initiale vide.
   Écrire une fonction concat : token list -> string qui renvoie la chaîne de caractères correspondant à une liste de jetons. Par exemple concat [TKNum 5; TKOp "x"; TKOp "("; TKNum 2; TKOp "+"; TKNum 3; TKOp ")"] renvoie "5x(2+3)".
8. 8

   Indice

   Composer les fonctions de transformation successivement sur la chaîne d'entrée pour obtenir la chaîne infixe finale.
   Enchaîner les fonctions expr_to_list, rpn_to_infix et concat sur l'expression 5 2 3 + x pour obtenir la chaîne infixe finale.