Discussion :

[araqh]

Bonjour,

J'essaie de faire un programme qui vérifie qu'une expression est bien parenthésée.
J'ai pas d'erreurs à la compilation ni à l'exécution. Mais il ne fonctionne pas correctement: toutes les expressions tapées son considérées comme bien parenthésées...
Je vous envoie mon code ci-dessous, quelque pourrait m'aider? Je vois pas d'où vient le problème.

Merci beaucoup d'avance.

Code :

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

1
2
3
4
5
6
7
 
public interface Stack 
{
	public Object push(int i);
	public Object pop();
	public boolean isEmpty();
}

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
41
42
43
 
 
 
class PileArray implements Stack 
{
	Object[] pile;
	int debut;
 
	public PileArray() 
	{
		pile= new Object[100];
		debut=-1;
	}
 
 
	public boolean isEmpty() 
	{
		return debut == -1;
	}
 
 
	public Object push(int item) 
	{
		if (debut==pile.length-1)  
		{
			pile[++debut] = item;
		}
 
		return item;
	} 
 
 
	public Object pop() 
	{
 
		if(!isEmpty())
		{
			debut--;
		}
 
		return pile[debut];
	}
}

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
 
 
import java.io.*;
 
   public class Parenthesage 
   {
 
     public static boolean verifiParen(String s) 
    {
       PileArray stack = new PileArray ();     
 
       for (int i = 0; i < s.length()-1; i++) 
	{
		switch (s.charAt(i)) 
		{
			case '(':
					stack.push(new Character ('('));
			break;
			case '[':
					stack.push(new Character ('['));
			break;
 
			case '{':
					stack.push(new Character ('{'));
 
			break;
			case ')':
					Character c = (Character) stack.pop();
					if (!match(c.charValue(), s.charAt(i))) return false;
			break;
			case ']':
 
					c = (Character) stack.pop();
					if (!match(c.charValue(), s.charAt(i))) return false;
			break;
			case '}':
					c = (Character) stack.pop();
					if (!match(c.charValue(), s.charAt(i))) return false;
			break;
			default:
			break;
		}
       }
 
       if ( stack.isEmpty())
		return true;
	else 
		return false ;
 
     }
 
 
     public static boolean match(char lpar, char rpar) {
       switch (lpar) {
       case '(': return rpar == ')';
       case '[': return rpar == ']';
       case '{': return rpar == '}';
       default: return false;
       }
     }
 
 
     public static void main(String[] args) throws IOException 
     {
	BufferedReader stdr;  
	stdr = new BufferedReader(new InputStreamReader(System.in));
 
	String line = stdr.readLine();   
	while (line != null) {
         if (verifiParen(line))
           System.out.println("well parenthesized");
         else
           System.out.println("parenthesis mismatch");
 
         line = stdr.readLine();   
       }
     }
   }

[tchize_]

Code :

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

1
2
3
4
		if (debut==pile.length-1)  
		{
			pile[++debut] = item;
		}

Comme au départ cette condition est fausse, debut restera indéfiniement à -1

Code :

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

1
2
3
4
5
6
7
8
9
10
	public Object pop() 
	{
 
		if(!isEmpty())
		{
			debut--;
		}
 
		return pile[debut];
	}

lors du pop, si c'est vide, tu ne retourne pas d'erreur -> si t'as une parenthèse ouverte pour deux fermantes, tu ne remarquera pas d'erreur (ton code va ignorer la deuxième).

Comme tu n'incrémente jamais, et que tu ignore les erreurs lors du pop, ta pile reste à vide sans erreur.

[araqh]

Merci beaucoup pour ta réponse.

J'ai créé une variable qui indique combien d'éléments il y a dans la pile et je l'incrémente à chaque fois que j'ajoute un élément dans celle-ci. Voici les changements que j'ai fait:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
public Object push(int item) 
	{
 
		if (debut==compteur)  
		{
			pile[++debut] = item;
		}
		compteur++;
		return item;
	}

Code :

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

1
2
3
4
5
6
7
8
9
 
	public Object pop() 
	{
		try{
		debut--;}
		catch (EmptyStackException e){}
 
		return pile[debut];
	}

Maintenant j'ai une erreur à l'exécution (une exception):
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -2
at PileArray.pop(PileArray.java:40)
at Parenthesage.verifiParen(Parenthesage.java:26)
at Parenthesage.main(Parenthesage.java:67)

Je vois pas où le problème. Est-ce que tu pourrais m'expliquer?
Merci beaucoup d'avance

[tchize_]

pourquoi tu met un tel if autour de ton empillement? ta ne permet, encore une fois, que l'empilement d'un seul élément! parce que une fois que t'aura fait ++debut, ben la condition debut==compteur ne sera plus valable -> plus aucun empilement ne sera fait.

Pour ton dépilement, ton exception montre que tu essaie de lire à l'index -2 de ton tableau, ce qui est illogique.
-> quand l'index est <0, renvoie une erreur, c'est qu'on ferme une parenthèse de trop.