Discussion :

[lazydev]

bonjour,
je prépare un examen et j'essaie de répondre aux question qui on été posé les années précédentes. J'aurais de savoir si le code que j'ai fait est bon et s'il aurait peut-être un meilleure moyen de faire.
La question :

On définit les séquences de paranethèses balancées comme suit :
-la séquence vide est balancée
-la séquence „( )“ est balancée
-une séquence balancée suivie d'une autre séquence balancée est balancée
-la séquence constitué de „ ( „ suivie d'une séquence balancée suivie de „)“ est une séquence balancée
-seules les séquences qui peuvent être construites selon ses règles sont balancées

Exemples :
„(()“ n'est pas balancée
„(()(()))“ est balancée
„()(()“ n'est pas balancée

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
32
33
34
35
36
37
38
39
40
 
public class Sequence {
 
   public boolean testBalance(ArrayList toTest){
        boolean test=false;
        ArrayList copyList=new ArrayList();
        //si vide il est balancée
        if(toTest.size()==0){
            test=true;
 
        }else{
            if(toTest.size() % 2 != 0){
                //s'il n'est pas divisible par 2 la séq. est forcément non balancée
                test=false;
            }else{
                for(int i=0; i<toTest.size(); i++){
                    if(toTest.get(i).equals("(") && toTest.get(i+1).equals(")")){
                      i++;
                    }else{
                       copyList.add(toTest.get(i));
                    }
                }
 
                test=testBalance(copyList);
            }
        }
        return test;
   }
   public static void main(String[] args) {
        //String [] toTest={"(","(",")","(",")",")","(",")"};
        String [] toTest={"(","(","(",")","(",")",")",")"};
        //String [] toTest={"(","(",")"};
        //String [] toTest={"(",")","(",")"};
        ArrayList list= new ArrayList(Arrays.asList(toTest));
        System.out.println(list);
        Sequence examen= new Sequence();
        System.out.println(examen.testBalance(list));
 
    }
}

[dinobogan]

C'est dommage de mélanger récursif et boucle for pour la sous chaine "()".
Voici un exemple d'une méthode non récursive :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
    public boolean testBalance( String chaine )
    {
        if( chaine.length() % 2 != 0 )
        {
            return false;
        }
        else
        {
            int compte = 0;
 
            for( int i = 0 ; i < chaine.length() ; ++i )
            {
                if( chaine.charAt( i ) == '(' ) ++compte;
                else if( chaine.charAt( i ) == ')' ) --compte;
                if( compte < 0 ) return false;
            }
 
            return compte == 0;
        }
    }

Et un exemple en récursif :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
    public boolean recurseTestBalance( String chaine )
    {
        return internalTestBalance( chaine, 0 ) == 0;
    }
 
    private int internalTestBalance( String chaine, int indice )
    {
        if( indice >= chaine.length() ) return 0;
        else
        {
            int compte = 0;
            if( chaine.charAt( indice ) == '(' ) ++compte;
            else if( chaine.charAt( indice ) == ')' ) --compte;
            return compte + internalTestBalance( chaine, indice + 1 );
        }
    }

[lazydev]

C'est vrai j'aurais du faire attention de ne pas mélanger les deux.
Je vais essayer de changer ca et ensuite je regarderais tes exemples en détail.

Déjà Merci.