/**

Un corrigé du TP2.

 */

#include <iostream>
#include <sstream>
#include <string>

using namespace std;

/******************************************************************************
 1- DEFINITIONS COMMUNES AUX TYPES PILE ET FILE
 ******************************************************************************/

// Cette directive selectionne l'implementation "tableau" des piles et files. La
// commenter pour selectionner l'implementation "liste chaînée".
#define IMPL_TABL

#ifdef IMPL_TABL

// Nombre maximal d'éléments géré par une pile ou une file
#define MAX_ELEM 100

#else

// Définition d'un maillon et d'une liste
typedef struct maillon {
	int info;
	struct maillon* suiv;
} maillon;

typedef maillon* liste;

#endif


/******************************************************************************
 2- DEFINITION DES TYPES PILE ET FILE
 ******************************************************************************/

//
// DEFINITION d'une pile
//
  typedef struct pile {
#ifdef IMPL_TABL
    int elements[MAX_ELEM];
    int sommet;             // sommet : +1 au dessus du vrai sommet
#else
    liste elements;
    unsigned int taille;
#endif
 } pile;

//
// DEFINITION d'une file
//
  typedef struct file {
#ifdef IMPL_TABL
     int elements[MAX_ELEM + 1];
     int debut;             // debut : élément de debut de file
     int fin;               // fin : +1 après la vraie fin de file
#else
    maillon* debut;         // élément de début de file
    maillon* fin;           // élément de fin de file
    unsigned int taille;
#endif
 } file;

// Note : il faut laisser un élément du tableau inutilisé pour
// distinguer les cas :
// - file vide : fin == debut
// - file pleine : SUCC(fin) == debut
// Le tableau fait donc (MAX_ELEM + 1) éléments pour faire que
// la file puisse contenir jusqu'à MAX_ELEM éléments.

#define SUCC(n) ((n) == MAX_ELEM ? 0 : (n) + 1)
#define PRED(n) ((n) == 0 ? MAX_ELEM : (n) - 1)

/******************************************************************************
 3- FONCTIONS DE MANIPULATION D'UNE PILE
 ******************************************************************************/

/**
 * Sert à initialiser une variable de type pile à "pile vide".
 *
 * Retourne : la valeur d'initialisation d'une pile vide.
 */
pile initPile() {
    pile r;
#ifdef IMPL_TABL
    r.sommet = 0;
#else
    r.elements = NULL;
    r.taille = 0;
#endif
    return r;
}

/**
 * Détermine la taille d'une pile.
 *
 * Paramètre p : pile à examiner.
 *
 * Retourne : la taille de p.
 */
int taillePile(pile p) {
#ifdef IMPL_TABL
    return p.sommet;
#else
    return p.taille;
#endif
}

/**
 * Détermine si une pile est vide.
 *
 * Paramètre p : pile à tester.
 *
 * Retourne : 1 si p est vide et 0 sinon.
 */
int estPileVide(pile p) {
    return taillePile(p) == 0;
}

/**
 * Détermine l'élément au sommet d'une pile.
 *
 * Paramètre p : pile à examiner.
 * Paramètre e : sommet de la pile retourné.
 *
 * Retourne : 1 si succès et 0 sinon.
 */
int sommet(pile p, int* e) {
    // si un paramètre ou l'état est incorrect
    if (e == NULL || estPileVide((p))) {
        return 0;
    }
#ifdef IMPL_TABL
    *e = p.elements[p.sommet - 1];
#else
    *e = p.elements->info;
#endif
    return 1;
}

/**
 * Empile un élément sur une pile.
 *
 * Paramètre p : pile sur laquelle empiler.
 * Paramètre e : élément à empiler.
 *
 * Retourne : 1 si succès et 0 sinon.
 */
int empiler(pile* p, int e) {
    // si un paramètre est incorrect
    if (p == NULL) {
        return 0;
    }
#ifdef IMPL_TABL
    if (p->sommet >= MAX_ELEM) {
        // pile pleine
        return 0;
    }
    p->elements[p->sommet] = e;
    p->sommet += 1;
#else
    maillon* n = new maillon;
    n->info = e;
    n->suiv = p->elements;
    p->elements = n;
    p->taille += 1;
#endif
    return 1;
}

/**
 * Dépile un élément d'une pile.
 *
 * Paramètre p : pile de laquelle dépiler.
 * Paramètre e : élément dépilé.
 *
 * Retourne : 1 si succès et 0 sinon.
 */
int depiler(pile* p, int* e) {
    // si un paramètre ou l'état est incorrect
    if (p == NULL || e == NULL || estPileVide(*p)) {
        return 0;
    }
#ifdef IMPL_TABL
    p->sommet -= 1;
    *e = p->elements[p->sommet];
#else
    maillon* d = p->elements;
    *e = d->info;
    p->elements = p->elements->suiv;
    p->taille -= 1;
    delete d;
#endif
    return 1;
}


/******************************************************************************
 4- FONCTION DE MANIPULATION D'UNE FILE
 ******************************************************************************/

/**
 * Sert à initialiser une variable de type file à "file vide".
 *
 * Retourne : la valeur d'initialisation d'une file vide.
 */
file initFile() {
    file r;
#ifdef IMPL_TABL
    r.debut = 0;
    r.fin = 0;
#else
    r.debut = NULL;
    r.taille = 0;
#endif
    return r;
}

/**
 * Détermine la taille d'une file.
 *
 * Paramètre f : file à examiner.
 *
 * Retourne : la taille de f.
 */
int tailleFile(file f) {
#ifdef IMPL_TABL
    int t = f.fin - f.debut;
    if (t < 0) {
        t += MAX_ELEM + 1;
    }
    return t;
#else
    return f.taille;
#endif
}

/**
 * Détermine si une file est vide.
 *
 * Paramètre f : file à tester.
 *
 * Retourne : 1 si f est vide et 0 sinon.
 */
int estFileVide(file f) {
    return tailleFile(f) == 0;
}

/**
 * Détermine l'élément au début d'une file.
 *
 * Paramètre f : file à examiner.
 * Paramètre e : début de la file retourné.
 *
 * Retourne : 1 si succès et 0 sinon.
 */
int debut(file f, int* e) {
    // si un paramètre ou l'état est incorrect
    if (e == NULL || estFileVide((f))) {
        return 0;
    }
#ifdef IMPL_TABL
    *e = f.elements[f.debut];
#else
    *e = f.debut->info;
#endif
    return 1;
}

/**
 * Détermine l'élément à la fin d'une file.
 *
 * Paramètre f : file à examiner.
 * Paramètre e : fin de la file retourné.
 *
 * Retourne : 1 si succès et 0 sinon.
 */
int fin(file f, int* e) {
    // si un paramètre ou l'état est incorrect
    if (e == NULL || estFileVide((f))) {
        return 0;
    }
#ifdef IMPL_TABL
    *e = f.elements[PRED(f.fin)];
#else
    *e = f.fin->info;
#endif
    return 1;
}

/**
 * Enfile un élément dans une pile.
 *
 * Paramètre f : file dans laquelle enfiler.
 * Paramètre e : élément à enfiler.
 *
 * Retourne : 1 si succès et 0 sinon.
 */
int enfiler(file* f, int e) {
    // si un paramètre est incorrect
    if (f == NULL) {
        return 0;
    }
#ifdef IMPL_TABL
    int s = SUCC(f->fin);
    if (s == f->debut) {
        // file pleine
        return 0;
    }
    f->elements[f->fin] = e;
    f->fin = s;
#else
    // créer le maillon à ajouter
    maillon* n = new maillon;
    n->info = e;
    n->suiv = NULL;
    // si premier maillon de la file
    if (f->debut == NULL) {
        // initialiser debut, fin et taille
        f->debut = n;
        f->fin = n;
        f->taille = 1;
        return 1;
    }
    // sinon, ne modifier que fin et taille
    f->fin->suiv = n;
    f->fin = n;
    f->taille += 1;
#endif
    return 1;
}

/**
 * Défile un élément d'une file.
 *
 * Paramètre f : file de laquelle défiler.
 * Paramètre e : élément défilé.
 *
 * Retourne : 1 si succès et 0 sinon.
 */
int defiler(file* f, int* e) {
    // si un paramètre ou l'état est incorrect
    if (f == NULL || e == NULL || estFileVide(*f)) {
        return 0;
    }
#ifdef IMPL_TABL
    *e = f->elements[f->debut];
    f->debut = SUCC(f->debut);
#else
    maillon* d = f->debut;
    *e = d->info;
    f->debut = d->suiv;
    f->taille -= 1;
    delete d;
    // note : pas besoin de modifier f->fin
#endif
    return 1;
}


/******************************************************************************
 5- EXERCICES D'APPLICATION
 ******************************************************************************/

/**
 * Inverse l'ordre des éléments d'une file.
 *
 * Paramètre f : file à inverser.
 *
 * Retourne : 1 si succès et 0 sinon.
 */
int inverser(file* f) {
    // si un paramètre est incorrect
    if (f == NULL) {
        return 0;
    }
    // passer par une pile pour inverser
    pile p = initPile();
    while (!estFileVide(*f)) {
        int e;
        defiler(f, &e);
        empiler(&p, e);
    }
    // transvaser en sens inverse
    while (!estPileVide(p)) {
        int e;
        depiler(&p, &e);
        enfiler(f, e);
    }
    return 1;
}

/**
 * Fusionne une collection de files d'entrées triées par ordre décroissant de
 * leurs éléments en une unique file de sortie triéee par ordre décroissant de
 * ses éléments. Les doublons éventuels ne sont pas supprimés. Après exécution,
 * toutes les files d'entrée sont vides.
 *
 * Exemple d'exécution :
 * - files en entrée : <11, 5, 4< ; <7< ; <10, 5, 5, 1<
 * - file en sortie : <11, 10, 7, 5, 5, 5, 4, 1<
 *
 * Paramètre fe : tableau des files d'entrées.
 * Paramètre nfe : nombre de files dans fe.
 * Paramètre fs : file de sortie.
 *
 * Retourne : 1 si succès et 0 sinon.
 */
int fusionner(file* fe, int nfe, file* fs) {
    // si un paramètre est incorrect
	if ((fe == NULL && nfe != 0) || fs == NULL) {
		return 0;
	}
	// initialiser la file de sortie
	*fs = initFile();
	// si aucune file d'entrée : rien à faire
	if (nfe == 0) {
		return 1;
	}
	// cas général : 1 ou plusieurs files d'entrée
	int inv = 0;   // indice première file non vide
	while (1) {
		// déterminer la 1ere file non vide
		int i = inv;
		while (i < nfe && estFileVide(fe[i])) {
			i += 1;
		}
		// aucune ? : on a terminé
		if (i >= nfe) {
			return 1;
		}
		inv = i;
		// une ? : on a une valeur initiale pour le maximum
		int mv;         // valeur maximum
		int mi = inv;   // indice file ayant le maximum
		debut(fe[mi], &mv);
		// chercher le maximum parmi les files non vides suivantes
		i += 1;
		while (i < nfe) {
            if (!estFileVide(fe[i])) {
                int v;
                debut(fe[i], &v);
                if (v > mv) {
                    // mémoriser le maximum et l'indice de la fils correspondante
                    mv = v;
                    mi = i;
                }
            }
            i += 1;
		}
		// défiler le maximum, l'enfiler sur la file de sortie et recommencer
		defiler(&fe[mi], &mv);
		enfiler(fs, mv);
	}
	return 1;
}

/**
 * Décompose une file d'entrée en une collection de file de sorties triées par
 * ordre décroissant de leurs éléments. Les doublons éventuels ne sont pas
 * supprimés. Après exécution, la file d'entrée est vide.
 *
 * Exemple d'exécution :
 * - file en entrée : <1, 7, 7, 2, 4, 5, 0<
 * - files en sortie : <1, 0< ; <7, 7, 2< ; <4< ; <5<
 *
 * Paramètre fe : file d'entrée à décomposer.
 * Paramètre fs : tabeau des files de sortie.
 * Paramètre nfs : nombre de files dans fs.
 *
 * Retourne : 1 si succès et 0 sinon.
 */
int decomposer(file* fe, file** fs, int* nfs) {
    // si un paramètre est incorrect
	if (fe == NULL || fs == NULL || nfs == NULL) {
		return 0;
	}
	// au pire, le nombre de files de sorties est la taille de la file d'entrée
	int ntfs = 0;               // nombre de files de sorties créées
	int n = tailleFile(*fe);
	file *tfs = new file[n];    // tableau maximum des files de sorties
	// pour chaque élément défilé de la file d'entrée
	for (int i = 0; i < n; i++) {
		int v;
		defiler(fe, &v);
		// chercher la file de sortie où mettre l'élément en fin
		int j;
		for (j = 0; j < ntfs; j++) {
			int t;
			fin(tfs[j], &t);
			if (t >= v) {
				break;
			}
		}
		// pas trouvée ? : créer une nouvelle file
		if (j >= ntfs) {
			tfs[ntfs] = initFile();
			j = ntfs;
			ntfs += 1;
		}
		// enfiler v dans la file de sortie trouvée ou créée
		enfiler(&tfs[j], v);
	}
	// tronquer le tableau alloué et le renvoyer
	*fs =  new file[ntfs];
	for (int i = 0; i < ntfs; i++) {
		(*fs)[i] = tfs[i];
	}
	delete tfs;
	*nfs = ntfs;
	return 1;
}

/**
 * Trie une file dans l'ordre décroissante de ses éléments.
 *
 * Paramètre f : file à trier.
 *
 * Retourne : 1 si succès et 0 sinon.
 */
int trier(file* f) {
    // si un paramètre est incorrect
    if (f == NULL) {
        return 0;
    }
    // trier = decomposer puis fusionner
    file* fs;
    int nfs;
    return decomposer(f, &fs, &nfs) && fusionner(fs, nfs, f);
}

/**
 * Evalue une expression booléenne post-fixée. Les opérateurs sont '+' (ou),
 * '*' (et), '^' (ou exclusif) et '!' (négation) ; les opérandes sont les
 * constantes 0 (faux) et 1 (vrai).
 *
 * Exemple d'exécution :
 * - évaluation de "1 0 + !" : 0
 * - évaluation de  "0 1 ! * 1 +" : 1
 * - évaluation de "0 1" ou "1 + 0" ou "" : -1 (expressions incorrectes)
 *
 * Paramètre e : expression à évaluer.
 *
 * Retourne : l'évaluation de e ou -1 si échec.
 */
int evaluer(const char* e) {
    // si un paramètre est incorrect
	if (e == NULL) {
		return -1;
	}
	// utiliser une pile pour les opérandes
	pile p = initPile();
	int o1, o2;
	// pour chaque élément lu
	while (*e != '\0') {
		switch (*e) {
		    // opérande 0 ou 1 ? : empiler
		case '0':
			empiler(&p, 0);
			break;
		case '1':
			empiler(&p, 1);
			break;
			// opérateurs +, ., etc. ? : dépiler les opérandes
			// faire l'opération et rempiler le résultat
		case '+':
			if (!depiler(&p, &o1) || !depiler(&p, &o2)) {
				return -1;
			}
			empiler(&p, o1 || o2);
			break;
		case '.':
			if (!depiler(&p, &o1) || !depiler(&p, &o2)) {
				return -1;
			}
			empiler(&p, o1 && o2);
			break;
		case '^':
			if (!depiler(&p, &o1) || !depiler(&p, &o2)) {
				return -1;
			}
			empiler(&p, o1 ^ o2);
			break;
		case '!':
			if (!depiler(&p, &o1)) {
				return -1;
			}
			empiler(&p, !o1);
			break;
		case ' ':
			break;
		default:
			return -1;
		}
		e += 1;
	}
	int v;
	// l'expression est bien formée s'il reste
	// exactement un élément dans la pile...
	if (!depiler(&p, &v) || !estPileVide(p)) {
		return -1;
	}
	// cet élément est le résultat
	return v;
}


/******************************************************************************
 FONCTIONS UTILITAIRES - Construction et affichage de piles et files
 ******************************************************************************/

/**
 * Convertit un tableau d'entiers en une pile. Le premier élément correspond au
 * sommet de la pile, le dernier au fond.
 *
 * Parametre n : le nombre d'éléments de t.
 * Parametre t : tableau d'entiers à convertir.
 *
 * Retourne : la pile équivalente à t.
 */
pile pilet(int n, const int t[]) {
    pile r = initPile();
    for (int i = 0; i < n; i++) {
        empiler(&r, t[n - 1 - i]);
    }
    return r;
}

/**
 * Représente une pile sous la forme d'une chaine de caractères. Le premier élément
 * listé est le sommet de la pile, le dernier le fond.
 *
 * Parametre p : pile à représenter.
 *
 * Retourne : la chaîne représentant p.
 */
string chainep(pile* p) {
    if (estPileVide(*p)) {
        return "<|";
    }
    ostringstream s;
    pile t = initPile();
    s << "<";
    // parcours DESTRUCTIF de la pile
    while (!estPileVide(*p)) {
        int e;
        depiler(p, &e);
        empiler(&t, e);
        s << e << ", ";
    }
    // pile à RECONSTRUIRE juste apres
    while (!estPileVide(t)) {
        int e;
        depiler(&t, &e);
        empiler(p, e);
    }
    // remplacer le dernier ", " par "|" (fond de pile)
    string r = s.str();
    return r.replace(r.size() - 2, r.size(), "|");
}

/**
 * Convertit un tableau d'entiers en une file. Le premier élément correspond au
 * debut de la file, le dernier à la fin.
 *
 * Parametre n : le nombre d'éléments de t.
 * Parametre t : tableau d'entiers à convertir.
 *
 * Retourne : la file équivalente à t.
 */
file filet(int n, const int t[]) {
    file r = initFile();
    for (int i = 0; i < n; i++) {
        enfiler(&r, t[i]);
    }
    return r;
}

/**
 * Représente une file sous la forme d'une chaine de caractères. Le premier élément
 * listé est le début de la file, le dernier la fin.
 *
 * Parametre f : file à représenter.
 *
 * Retourne : la chaîne représentant f.
 */
string chainef(file* f) {
    if (estFileVide(*f)) {
        return "<<";
    }
    ostringstream s;
    int t = tailleFile(*f);
    s << "<";
    // parcours reconstructif de la file
    for (int i = 0; i < t; i++) {
        int e;
        defiler(f, &e);
        enfiler(f, e);
        s << e << ", ";
    }
    // remplacer le dernier ", " par "<" (fin de file)
    string r = s.str();
    return r.replace(r.size() - 2, r.size(), "<");
}


/******************************************************************************
 PROGRAMME DE TEST - Tester ici chaque fonction developpee
 ******************************************************************************/

int main() {

    //
    // TESTS D'UNE PILE
    //

    // pile vide
    cout << "\nTEST pile vide" << endl;
    int r, e;
    pile p = initPile();
    string c = chainep(&p);
    cout << "taillePile(" << c << ") = " << taillePile(p) << endl;
    cout << "estPileVide(" << c << ") = " << estPileVide(p) << endl;
    cout << "sommet(" << c << ", " << &e << ") = " << sommet(p, &e) << endl;

    // un premier empilement
    cout << "\nTEST on empile" << endl;
    r = empiler(&p, 1);
    cout << "empiler(" << c << ", 1) = " << r << ", p = " << chainep(&p) << endl;
    c = chainep(&p);
    cout << "taillePile(" << c << ") = " << taillePile(p) << endl;
    cout << "estPileVide(" << c << ") = " << estPileVide(p) << endl;
    r = sommet(p, &e);
    cout << "sommet(" << c << ", e) = " << r << ", e = " << e << endl;

    // un deuxieme empilement
    cout << "\nTEST on empile encore" << endl;
    r = empiler(&p, 2);
    cout << "empiler(" << c << ", 1) = " << r << ", p = " << chainep(&p) << endl;
    c = chainep(&p);
    cout << "taillePile(" << c << ") = " << taillePile(p) << endl;
    cout << "estPileVide(" << c << ") = " << estPileVide(p) << endl;
    r = sommet(p, &e);
    cout << "sommet(" << c << ", e) = " << r << ", e = " << e << endl;

    // un depilement
    cout << "\nTEST on depile" << endl;
    r = depiler(&p, &e);
    cout << "depiler(" << c << ", e) = " << r << ", p = " << chainep(&p) << ", e = " << e << endl;
    c = chainep(&p);
    cout << "taillePile(" << c << ") = " << taillePile(p) << endl;
    cout << "estPileVide(" << c << ") = " << estPileVide(p) << endl;
    r = sommet(p, &e);
    cout << "sommet(" << c << ", e) = " << r << ", e = " << e << endl;

    cout << "\nTEST on depile encore" << endl;
    r = depiler(&p, &e);
    cout << "depiler(" << c << ", e) = " << r << ", p = " << chainep(&p) << ", e = " << e << endl;
    c = chainep(&p);
    cout << "taillePile(" << c << ") = " << taillePile(p) << endl;
    cout << "estPileVide(" << c << ") = " << estPileVide(p) << endl;
    r = sommet(p, &e);
    cout << "sommet(" << c << ", e) = " << r << ", e = " << e << endl;

    //
    // TESTS D'UNE FILE - partiel
    //
    cout << "\nTEST file" << endl;
    file f = filet(3, (int[]){1, 2, 3});
    cout << tailleFile(f) << endl;
    r = debut(f, &e);
    cout << "debut = " << r << ", e = " << e << endl;
    r = fin(f, &e);
    cout << "fin = " << r << ", e = " << e << endl;
    cout << "f = " << chainef(&f) << endl;

    //
    // TESTS inverser() - partiel
    //
    cout << "\nTEST inverser()" << endl;
    f = filet(3, (int[]){1, 2, 3}); c = chainef(&f); r = inverser(&f);
    cout << "inverser(" << c << ") = " << r << ", f = " << chainef(&f) << endl;

    //
    // TESTS fusionner() - partiel
    //
    cout << "\nTEST fusionner()" << endl;
    file fe[] = {filet(3, (int[]){11, 5, 4}), filet(1, (int[]){7}), filet(4, (int[]){10, 5, 5, 1})};
    file fs;
    r = fusionner(fe, 3, &fs);
    cout << "fusionner(..., ..., ...) = " << r << ", fs = " << chainef(&fs) << endl;

    //
    // TESTS decomposer() - partiel
    //
    cout << "\nTEST decomposer()" << endl;
    int nfs;
    file* tfs;
    f = filet(7, (int[]){1, 7, 7, 2, 4, 5, 0});
    r = decomposer(&f, &tfs, &nfs);
    cout << "decomposer(..., ..., ...) = " << r << ", nfs = " << nfs << endl;
    for (int i = 0; i < nfs; i++) {
        cout << "tfs[" << i << "] = " << chainef(&tfs[i]) << endl;
    }

    //
    // TESTS trier() - partiel
    //
    cout << "\nTEST trier()" << endl;
    f = filet(7, (int[]){1, 2, 3, 4, 5, 6, 7}); c = chainef(&f); r = trier (&f);
    cout << "trier(" << c << ") = " << r << ", f = " << chainef(&f) << endl;


    //
    // TESTS evaluer() - partiel
    //
    cout << "\nTEST evaluer()" << endl;
    c = "1 0 + !";
    cout << "evaluer(" << c << ") = " << evaluer(c.c_str()) << endl;
    c = "1 0 + 0";
    cout << "evaluer(" << c << ") = " << evaluer(c.c_str()) << endl;


	return 0;
}