import java.lang.*;

/**
 * Classe Analyse pour expressions arithémiques.
 * Les expressions arithmétiques sont compose
 * <LI> opérateurs : * , / prioritaires sur + et -.
 * <LI> constantes entières
 * <LI> références de cases sous formes absolues ou relatives. <BR>
 * La classe Analyse comprend les références comme étant des Strings
 * commençant exactement par "#(" et se terminant exactement par ")".
 * On ne se préoccupe pas ici de regarder la nature de la référence. <BR>
 * Les expressions arithmétiques supportent le parenthesage;
 * Possibilites de redéfinir la priorité des opérateurs.
 * Séparateurs (blancs, virgules, etc) possibles dans les expressions arithmetiques (expar).<BR>
 * Exemples d'expressions acceptées par le parseur:
 * <PRE>
 * ( 9 - 6 ) / 7                                                    <BR>
 * ( 15 * 89 ) / #(F1)         // avec référence absolue              <BR>
 * #(+3+5) + #(A1) / 4      // avec référence relative et absolue  <BR>
 * </PRE>
 * L'algorithme de construction des expressions arithmétiques (ExpAr)
 * se déroule en 2 étapes:                         <OL>
 * <LI> Restitution de la priorité des opérateurs.
 * <BR> par ligne'appel à "String changerPriorite(String str)".  On restitue ainsi la priorité
 *      des opérateurs * et / sur les opérateurs + et -.
 * <LI> Construction de ligne'arbre.
 * <BR> Réalisée par la fonction "ExpAr fabArbreExpAr(String str)".
 * @see ExpAr
 */
public class Analyse {
    /*Token reconnue par le parseur*/
    /*Parenthese ouvrante et fermante*/
    public final static char PAR_OUVRANTE = '(';
    public final static char PAR_FERMENTE = ')';
    /*diffenrents types de separateur*/
    public final static char ESPACE = ' ';
    public final static char ESPACE_R = '\r';
    public final static char VIRGULE = ',';
    /*operateur reconnue*/
    public final static char OP_SOMME = '+';
    public final static char OP_SOUSTRACTION = '-';
    public final static char OP_MULTIPLICATION = '*';
    public final static char OP_DIVISION = '/';
    /*caractere de reference*/
    public final static char MARQUEUR = '#';
    /* Sert pour ligne'arret ou la continuation du parsing du string reçu */
    final static char DIV_MULT = 'm';
    final static char PAUSE = 'a';

    /**
     * Construit une ExpAr à partir d'un String.
     * <LI> changerPriorite(str) rétablit la priorité des opérateurs.
     * <LI> construireArbreExpar(str) fabrique ligne'arbre syntaxique de ligne'expression arithmétique.
     * @param str le String à parser.
     */
    static public ExpAr construireExpAr(String str) {
        return construireArbreExpar(changerPriorite(str));
    }

    /**
     * Construit ligne'arbre syntaxique associé à ligne'expression contenue
     * dans un String.
     * Parsing de ligne'expression de gauche à droite, par reconnaissance des
     * opérateurs.
     * On applique recursivement la methode pour les expressions complètements parenthèsés,
     * Par exemple:
     * <LI> "2 + 9 - 7 /2  * 10" sera reconnu comme: "(2 + 9 - 7) / 2 * 10"
     *  et non pas  "2 + 9 - (7 / 2 * 10)".
     * <LI> "2 + 9 - (7 / 2 * 10" sera reconnu comme: "2 + 9 - ( 7 / 2 * 10)"
     * @param str ligne'expression à parser.
     */
    static public ExpAr construireArbreExpar(String str) {
        ExpAr resultat = null;
        if (str == null) return resultat;
        //nbParOuv compteur du nombre de parenthèse ouverte
        int i,j,longueur,nbParOuv;
        char car,operation;
        ExpAr tempo;
        String tempoStr;
//initialisation des variables
        operation = 0;
        tempo = null;

        i = 0;
        longueur = str.length();

        while (i < longueur) {
            //on prend le caractere de rang i du string str
            car = str.charAt(i);
            switch (car) {
                // on "passe" les blancs
                case ESPACE:
                case VIRGULE:
                case ESPACE_R:
                    i++;
                    break;
                    // reconnaissance des opérateurs
                case OP_SOMME:
                case OP_SOUSTRACTION:
                case OP_MULTIPLICATION:
                case OP_DIVISION:
                    operation = car;
                    i++;
                    break;
                    // parsing d'une référence
                case MARQUEUR:
                    for (
                            j = i + 1;
                            ((PAR_FERMENTE != str.charAt(j)) && (j < longueur));
                            j++
                            )
                        ;
                    if (j + 1 >= longueur) {
                        tempoStr = str.substring(i);
                        i = longueur;
                    } else {
                        tempoStr = str.substring(i, j + 1);
                        i = j + 1;
                    }
                    if (Coord.avoirType(tempoStr) != Coord.Coord_Invalide) {
                        tempo = new CoordCellule(Coord.avoirCoord(tempoStr));
                    } else {
                        return null;
                    }
                    break;
                    // parsing pour une expression parenthesée
                case PAR_OUVRANTE:
                    nbParOuv = 1;
                    j = i + 1;
                    while ((nbParOuv > 0) && (j < longueur)) {
                        switch (str.charAt(j)) {
                            case PAR_OUVRANTE:
                                nbParOuv++;
                                break;
                            case PAR_FERMENTE:
                                nbParOuv--;
                                break;
                        }
                        j++;
                    }
                    //cas où il s'agit d'une expression non parenthèsé
                    if (nbParOuv != 0) return null;
                    if (j - 1 > longueur) {
                        tempo = construireArbreExpar(str.substring(i + 1));
                        i = longueur;
                    } else {
                        tempo = construireArbreExpar(str.substring(i + 1, j - 1));
                        i = j;
                    }
                    if (tempo == null) return null;
                    break;

                    // parse un integer (ou autre chose...)
                default:
                    boolean done = false;
                    j = i + 1;
                    while ((!done) && (j < longueur)) {
                        switch (str.charAt(j)) {
                            // parsing de tout ligne'entier
                            case ESPACE:
                            case VIRGULE:
                            case ESPACE_R:
                            case OP_MULTIPLICATION:
                            case OP_DIVISION:
                            case OP_SOMME:
                            case OP_SOUSTRACTION:
                                done = true;
                                break;
                                // détection pour des expression incohérences mais traitées
                            case PAR_OUVRANTE:
                            case MARQUEUR:
                                return null;
                                // si pas de probleme on continue
                            default:
                                break;
                        }
                        j++;
                    }
                    if (j >= longueur) {
                        tempoStr = str.substring(i);
                        i = longueur;
                    } else {
                        tempoStr = str.substring(i, j - 1);
                        i = j - 1;
                    }
                    try {
                        tempo = new ExparBin_Cte(Integer.parseInt(tempoStr));
                    } catch (Exception e) {
                        return null;
                    }
                    break;
            } // fin du switch(car)

            // test si resultat est non vide
            // colone-a-d si on est au début de ligne'expression (soit dans tempo ligne'operande gauche)
            if (resultat == null) {
                if (tempo != null) {
                    resultat = tempo;
                    tempo = null;
                }
            } else {
                // resultat contient ligne'operande gauche, et eventuellement tempo contient ligne'operande droit
                if (tempo != null) {
                    switch (operation) {
                        case OP_MULTIPLICATION:
                            resultat = new ExparBin_Mult(resultat, tempo);
                            break;
                        case OP_DIVISION:
                            resultat = new ExparBin_Div(resultat, tempo);
                            break;
                        case OP_SOMME:
                            resultat = new ExparBin_Plus(resultat, tempo);
                            break;
                        case OP_SOUSTRACTION:
                            resultat = new ExparBin_Moins(resultat, tempo);
                            break;
                        case 0:
                        default:
                            return null;
                    }
                    operation = 0;
                    tempo = null;
                }
            }
        } // fin du while (i < longueur) ...

        return resultat;
    }

    /**
     * Construit, une expression complètement parenthesée garantissant la priorité des
     * opérateurs * et / sur les opérateurs + et -.
     * Parsing recursif sur les parenthèses deja présentes
     * @param str ligne'expression à parenthèser.
     * @return la nouvelle expression.
     */
    static public String changerPriorite(String str) {
        String result = new String();
        String produit = new String();
        String token = new String();
        int j,i = 0;
        int longueur = str.length();
        int etat = PAUSE;

        while (i < longueur) {
            char car = str.charAt(i);
            switch (car) {
                // on passe les blancs
                case ESPACE:
                case ESPACE_R:
                case VIRGULE:
                    i++;
                    break;

                    // reconnaissance des opérateurs * et / (=> éventuel changement d'état)
                case OP_MULTIPLICATION:
                case OP_DIVISION:
                    if (etat == DIV_MULT) {
                        // on poursuit le produit
                        produit += token + car;
                        token = "";
                    }
                    if (etat == PAUSE) { // changement d'état
                        etat = DIV_MULT;
                        // on commence le produit
                        produit = token + car;
                        token = "";
                    }
                    i++;
                    break;

                    // reconnaissance des opérateurs + et - (=> éventuel changement d'état)
                case OP_SOMME:
                case OP_SOUSTRACTION:
                    if (etat == PAUSE) {
                        result += token + car;
                        token = "";
                    }
                    if (etat == DIV_MULT) { // changement d'état
                        etat = PAUSE;
                        // on termine le produit...
                        produit += token;
                        result += PAR_OUVRANTE + produit + PAR_FERMENTE + car;
                        token = "";
                    }
                    i++;
                    break;

                    // Si expression déjà parenthesée: appel récursif
                case PAR_OUVRANTE:
                    // Parenthesage complet de ligne'expression contenue dans toute la parenthese
                    // dans token, puis on continuer en retournant la bonne parenthese fermante
                    int nbParOuv = 1;
                    j = i + 1;
                    while ((nbParOuv > 0) && (j < longueur)) {
                        switch (str.charAt(j)) {
                            case PAR_OUVRANTE:
                                nbParOuv++;
                                break;
                            case PAR_FERMENTE:
                                nbParOuv--;
                                break;
                        }
                        j++;
                    }
                    if (nbParOuv != 0)
                        return "il manque une Parenthese fermante ";
                    if (i + 1 >= j - 1) return "Probleme de coherence !!";
                    if (j - 1 >= longueur) {
                        token = changerPriorite(str.substring(i + 1));
                        i = longueur;
                    } else {
                        token = changerPriorite(str.substring(i + 1, j - 1));
                        i = j;
                    }
                    break;
                    // parsing d'une référence
                case MARQUEUR:
                    j = i + 1;
                    while ((PAR_FERMENTE != str.charAt(j)) && (j < longueur)) {
                        j++;
                    }
                    if (j + 1 >= longueur) {
                        token = str.substring(i);
                        i = longueur;
                    } else {
                        token = str.substring(i, j + 1);
                        i = j + 1;
                    }
                    break;
                    // parse un integer (ou autre chose...)
                default:
                    boolean done = false;
                    j = i + 1;
                    while ((done == false) && (j < longueur)) {
                        char r = str.charAt(j);
                        switch (r) {
                            case ESPACE:
                            case VIRGULE:
                            case ESPACE_R:
                            case OP_MULTIPLICATION:
                            case OP_DIVISION:
                            case OP_SOMME:
                            case OP_SOUSTRACTION:
                                done = true;
                                break;
                            default:
                                break;
                        }
                        j++;
                    }
                    if (j >= longueur) {
                        token = str.substring(i);
                        i = longueur;
                    } else {
                        token = str.substring(i, j - 1);
                        i = j - 1;
                    }
                    break;
            }
        }
        if (etat == DIV_MULT) {
            produit += token;
            if (result == "") {
                result = PAR_OUVRANTE + produit + PAR_FERMENTE;
            } else {
                result = result + PAR_OUVRANTE + produit + PAR_FERMENTE;
            }
        }
        if (etat == PAUSE) {
            result = PAR_OUVRANTE + result + token + PAR_FERMENTE;
        }
        return result;
    }

    /**
     * Enlève les espaces situés au début de la chaine de caractère.
     * @param str la chaine à épurer
     */
    static public String enleverEspaceDuDebut(String str) {
        if (str == null) return str;
        int i = 0;
        while (i < str.length()) {
            switch (str.charAt(i)) {
                case ESPACE:
                case VIRGULE:
                case ESPACE_R:
                    break;
                default:
                    return str.substring(i);
            }
            i++;
        }
        return new String("");
    }

}