Traitement d'une chaîne de caractères qui contient des parenthèses et des crochets

Version imprimable

06/07/2018, 07h50
chachenak

Traitement d'une chaîne de caractères qui contient des parenthèses et des crochets

Bonjour a tous!
ça fait un bon moment que j'essaie de résoudre ce problème mais je n'arrive toujours pas ! Donc je voudrais savoir si quelqu'un pourra m'orienter !
J'ai une méthode qui prend en entrée une chaîne de caractères et elle retourne un booléen.
J'ai mis plusieurs conditions dans ma méthode tel que la verification s'il s'agit d'un palindrome, compte le nombre ( , ) et [,] mais sans résultats. Quelqu'un aurait-il la gentillesse de me donner un coup de pousse ?

Résultat attendu pour plusieurs chaines :

verification("[()]") // true
verification("(()[])") // true
verification("([)]") // false
verification("((") // false
verification("[(()])") // false

verification("([(([[(([]))]]))])") // true
verification("[](()()[[]]) ()[]([])") // true
verification("([((([(([]))])))))])") // false
verification("[](()()[[]])[][[([])") // false
06/07/2018, 08h24
joel.drigo
Salut,
1. C'est quoi la question exactement ?
2. S'il faut pouvoir te dire où se trouve un (ou plusieurs) problème(s), il nous faut voir le code et savoir exactement quelle est la fonction de conversion de l'entrée vers la sortie, parce que là, ce n'est pas très clair :
  - Tu parles de plusieurs conditions et d'un résultat booléen : quelle est le lien entre ces conditions et ce résultat unique ? Un or, un and... ? Et quelles sont-elles ? Et y a t-il des entrées non traitables autre que null (chaînes vides, caractères autres que parenthèses et crochets...) ?
  - Si je comprends bien les résultats, à priori, on aurait une méthode qui vérifie que les parenthèses et crochets sont correctement balancés. On ne peut pas faire ça par simple comptage : la solution passe par une pile, soit en variable, soit par récursivité.
  - Et tu parles de palindrome (chaîne telle que si tu inverses l'ordre de caractères, la chaîne est la même, soit la lire de droite à gauche donne la même chose que de gauche à droite, qui n'a rien à voir avec un balancement correcte : [([)] est un palindrome à priori. Et ([])[()] n'en n'est pas un, mais est correctement balancée localement.
  - Et c'est quoi la versification d'un palindrome constitué de parenthèses et crochets ?
12/07/2018, 03h03
chachenak

Merci beaucoup! grâce a votre aide j'ai réussi a le faire avec une pile!
Merci encore une fois

Citation:

Envoyé par chachenak

Merci beaucoup! grâce a votre aide j'ai réussi a le faire avec une pile!

Bravo. Ce serait intéressant que tu montres ta solution. Elle pourrait servir à d'autres pour exemple.

Voici ma proposition pour une version en dur :

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
32
33
34
35
36
37
38
public static void main(String[] args) {
		test(true, "[()]"); // true
		test(true, "(()[])"); // true
		test(false, "([)]"); // false
		test(false, "(("); // false
		test(false, "[(()])"); // false
 
		test(true, "([(([[(([]))]]))])"); // true
		test(true, "[](()()[[]]) ()[]([])"); // true
		test(false, "([((([(([]))])))))])"); // false
		test(false, "[](()()[[]])[][[([])"); // false
	}
 
	private static void test(boolean expected, String string) {
		System.out.printf("Test sur %s: %s%n", string, verification(string)==expected?"OK":"KO");
	}
 
	public static boolean verification(String string) {
		Deque<Character> stack = new ArrayDeque<>();
		for(char c : string.toCharArray()) {
			switch(c) {
			case '(':
				// cas ouvrant
				stack.push(')');
				break;
			case '[':
				// cas ouvrant
				stack.push(']');
				break;
			case ')':
			case ']':
				// cas fermant
				if ( stack.isEmpty() || stack.pop()!=c ) return false;
				break;
			}
		} 
		return stack.isEmpty();
	}

Remarquons que s'il y a une seule paire de caractères, on peut simplifier la pile en la simulant par un entier, parce qu'on a besoin d'y stocker toujours uniquement le même caractère (l'unique caractère fermant), donc de ne pas le stocker. Le fait que la pile ne soit pas vide veut dire que cet unique caractère s'y trouve. Pour empiler, on incrémente par exemple, et pour dépiler, on décrémente : ceci permet de gérer l'aspect LIFO.

Et donc :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static boolean verificationParentheses(String string) {
		int stack = 0;
		for(char c : string.toCharArray()) {
			switch(c) {
			case '(':
				// cas ouvrant
				stack++; // empilement
				break;
			case ')':
				// cas fermant
				if ( stack==0/*pile vide*/ ) return false;
				stack--; // dépilement
				break;
			}
		} 
		return stack==0;
	}