Parsing d'expressions arithmétiques

Version imprimable

23/08/2006, 09h55
Premium

Parsing d'expressions arithmétiques

Bonjour,

j'essaye de faire un exo mais je ne sais pas très bien comment m'y prendre.
Si quelqu'un pouvait m'aider ?

Merci

Voici l'énoncé :

Citation:

Écrire une classe ExprParser avec une méthode Expr parse(Scanner sc) qui construit une expression arithmétique de type Expr à partir de ce qu'elle lit sur le scanner passé en argument.
On suppose pour cela que l'expression lue par le scanner est en notation préfixe, c'est-à-dire qu'on exprime l'opérateur, puis ses deux opérandes (on se limite au cas classique des opérations binaires +, -, / et *).
Par exemple, l'expression préfixe :

+ - 7 3 / 5 * + 4 5 - 4 2

représente en notation infixe l'expression

(7 - 3) + 5 / ((4 + 5) * (4 - 2))

Pour l'analyse, on pourra supposer que tous les opérateurs débutent par des caractères différents (on peut faire un "switch").
Dans le cas où l'expression analysée serait incorrecte, on lèvera une exception de la classe ExprParseException qu'il faudra définir. Faite en sorte d'obliger le programmeur à récuperer cette exception. L'exception devra représenter le plus fidèlement possible le problème rencontré.
23/08/2006, 10h14
Nicolas_75

Bonjour,

Il serait utile de connaître le type "Expr" (EDIT : ) pour savoir ce que tu cherches à obtenir.

Cordialement,

Nicolas
23/08/2006, 11h15
Premium

1 pièce(s) jointe(s)

Citation:

Envoyé par Nicolas_75

Bonjour,

Il serait utile de connaître le type "Expr" (EDIT : ) pour savoir ce que tu cherches à obtenir.

Cordialement,

Nicolas

Je t'ai mis une archive contenant l'interface Expr et les différentes classes.
Expr est une interface permettant d'avoir une valeur de type Value (c'est un nombre) ou une expression de type BinOP (ça peut être une addition, soustraction,...)

Ci-dessous trois classes...

1. Nouvelle classe "Minus"

Code:

1
2
3
4
5
6
7
8
9
10
public class Minus extends BinOp{
 
    public Minus(Expr a, Expr b){
	super(a,b);
    }
 
    public double eval(){
	return getA().eval()-getB().eval();
    }
}

2. Classe ExprParser

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.Scanner;
 
public class ExprParser {
 
    public static Expr exprparse(Scanner sc) {
        if (sc.hasNextInt()) {
            return new Value(sc.nextInt());
        } else { // le scanner renvoie un opérateur
            char op = sc.next().charAt(0);
            // on cherche les opérandes de l'opérateur dans la suite du scanner
            Expr premierOperande = exprparse(sc);
            Expr secondOperande = exprparse(sc);
            switch (op) {
                case '+' : return new Add(premierOperande, secondOperande);
                case '-' : return new Minus(premierOperande, secondOperande);
                case '*' : return new Mult(premierOperande, secondOperande);
                case '/' : return new Div(premierOperande, secondOperande);
                default : return new Value(0); // ne devrait pas arriver
            }
        }
    }
}

3. Classe Main de test

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.util.Scanner;
 
public class Main{
 
    public static String print(Expr e) {
        if (e instanceof Value) {
            return ""+e.eval();
        } else if (e instanceof Add) {
            return "("+print(((BinOp) e).getA())+" + "+print(((BinOp) e).getB())+")";
        } else if (e instanceof Mult) {
            return "("+print(((BinOp) e).getA())+" * "+print(((BinOp) e).getB())+")";
        }         else if (e instanceof Minus) {
            return "("+print(((BinOp) e).getA())+" - "+print(((BinOp) e).getB())+")";
        } else if (e instanceof Div) {
            return "("+print(((BinOp) e).getA())+" / "+print(((BinOp) e).getB())+")";
        } else return "";
    }
 
    public static void main(String [] args){
        Scanner sc = new Scanner("+ - 7 3 / 5 * + 4 5 - 4 2");
        Expr resultat = ExprParser.exprparse(sc);
        System.out.println(print(resultat));
        System.out.println(resultat.eval());
    }
}

Ces 3 classes, rajoutées à celles que tu as données ci-dessus, donnent un tout qui compile.
Le résultat chez moi est :

Citation:

((7.0 - 3.0) + (5.0 / ((4.0 + 5.0) * (4.0 - 2.0))))
4.277777777777778

J'ai fait cela vite : le code peut probablement être optimisé et amélioré.
Il reste entre autres la gestion des exceptions à mettre en place.

En espérant que cela puisse t'aider,

Nicolas

Bonjour,
Personellement j'utiliserais du récurcif, ce qui donnerait à peu près cette algo

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 
        Expr parse(Scanner sc)
        {
            return parseRec(sc,new ArrayList());
        }
 
        Expr parseRec(Scanner sc, ArrayList exprList)
        {
            if(sc.hasNextInt())
            {
                exprList.add(sc.nextInt());
                return parseRec(sc,exprList);
            }
            if(!scanner.hasNext())
                if(exprList.length()!=0)
                    throw new Exception("Expression incorrecte");
                else
                    return exprList.get(0);
            char c = sc.next(Pattern.compile("."));
            switch(c)
            {
                case '+':
                    Expr expr1 = exprList.get(0);
                    Expr expr2 = exprList.get(1);
                    exprList.remove(expr1);
                    exprList.remove(expr2);
                    exprList.add(new Add(expr1, expr2));
                    return parseRec(sc,  exprList);
                //... meme principe pour les autres opérateurs
            }
        }

C'est un peu le principe des grammaires LR(1) que j'ai utilisé avec la grammaire suivante
Expr -> op Expr Expr
Expr -> num