Bonjour.
Je sollicite votre aide concernant une question d’un devoir que j’ai à faire en programmation java, appliqué aux maths . Je sèche totalement .
Le but est d’écrire une méthode java, récursive, prenant en paramètre un nombre entier n, et dont le but est d’afficher tous les mots bien parenthésés de longueur 2n.
Un mot bien parenthésé est une succession de parenthèses ouvrantes et fermantes, telle que une ouvrante est toujours refermée par une fermante, par exemple
( )( )( ) et ( ( ) ) sont des mots bien parenthésés .
( et ( ( ( ) ) sont des mots pas bien parenthésés .
J’espère que vous pourrez m’aider, ou du moins me débloquer ! …
Merci d’avance .
Bonjour,
Comment fais-tu, algorithmiquement, pour vérifier qu’un mot est bien parenthésé ?
Par exemple, le mot (()(()()))()((())()) est-il bien parenthésé ? Et le mot (()(()())))(((())()) ?
Cordialement,
V@J
Supposons que tu es à l’indice i et que ton mot (de longueur i) peut être bien parenthésé, de quelle information sur ce mot as-tu réellement besoin pour continuer ?
Indice : Chaque parenthèse ouverte doit être refermée.
Hum, je dirais qu’il faudrait utiliser une pile :
On regarde le 1er élément du mot .
Si c’est une parenthèse ouvrante ( , on l’empile .
Sinon, on retourne false car un mot bien parenthésé ne peut pas commencer par ) .
Quand on regarde le i-ème élément du mot (différent du premier)
Si c’est une ouvrante ( alors on l’empile
Sinon, on regarde le sommet de la pile .
Si ce sommet est une parenthèse fermante alors on retourne false
Si ce sommet est une parenthèse ouvrante ( alors on dépile ce sommet et on passe à l’élément i+1 .
Voilà, j’ai pensé à cet algorithme .
Donc je suppose que pour répondre à la question qu’on m’a posée, il faudrait que d’abord je crée TOUS les mots parenthésés de longueurs 2n, et que après je sélectionne les mots bien parenthésés ?
Mais je vois toujours mal comment tous les créer . Comment faire un code qui permet de passer par tous les cas possibles récursivement 
j’avais pensé que tous les mots bien parenthésés de longueur n+2 pouvaient s’obtenir à partie des mots de longueurs n en faisant les concaténations suivantes :
(x)
( )x
x( )
avec x les mots de longueur n
Et bien sûr, pour les premiers cas ça fonctionne,mais après il m’en manque !
C’est faux, mais c’est bien d’y avoir pensé (tu pourrais je pense t’en sortir quand même avec x)) et ((x où x contient respectivement deux parenthèses ouvrantes et fermantes, mais bon…).
Générer tous les mots puis vérifier s’ils sont bien parenthésés n’est pas le plus judicieux, tu peux générer directement les mots bien parenthésés.
Il y a des erreurs dans l’explication de ton algorithme de vérification du bon parenthésage (on n’empile pas une parenthèse fermante, le mot serait alors mal parenthésé).
Du coup si tu n’empiles que des parenthèses ouvrantes, tu n’as plus besoin d’une pile mais d’un compteur.
Oui c’est vrai, la pile n’est pas indispensable du coup.
Je n’ai pas compris ce que tu as écrit concernant ((x et x)) . si x est un mot bien parenthésé, alors ((x ne le sera pas …
Après, je veux bien tous les créer d’un coup, mais je vois vraiment mal comment faire .
« x)) et ((x où x contient respectivement deux parenthèses ouvrantes et fermantes » en trop, donc où x est mal parenthésé ; mais laissons tomber ça pour le moment.
Là tu sais comment vérifier qu’un mot est bien parenthésé : arrivé à l’indice i, tu as seulement besoin de connaître le nombre de parenthèses ouvrantes dans le sous-mot [0..i-1].
Ne peux-tu pas connaître de la sorte tous les mots correctement parenthésés commençant par le sous-mot [0..i-1] ?
Attention cependant à ne pas ouvrir des parenthèses qu’on ne pourrait refermer.
J’y connais rien en info mais c’est possible d’assigner une valeur à un caractère ?
Si oui ( a pour valeur 1 et ) à pour valeur -1
Ainsi un mot est bien parenthésé ssi la somme des valeurs est nulle ?
EDIT: Ah j’ai pas rafraîchi la page entre temps. Je lis les posts.
J'y connais rien en info mais c'est possible d'assigner une valeur à un caractère ?
Ca fait peut à voir…vivement qu’il y ait un peu d’info pour tous en prépa 
Sinon oui, l’idée de la pile est bonne. Pour l’implémentation, nul besoin d’avoir une « vraie » pile capable de gérer tout et n’importe quoi (je parle des types là…ça dépend du langage) mais l’idée de pile est la bonne.
On empile sur une ouvrante, on dépile sur une fermante et on regarde à chaque fois si on n’a pas déjà la réponse « mal parenthésé ».
Mais c’est quoi cette histoire de pile où on empile sur une ouvrante et on dépile sur une fermante ?
[spoiler]OCaml :
let read_int () = Scanf.scanf "%d " (fun x -> x) in
let n = read_int () in
let rec f c i mot =
if i = 2 * n then
Printf.printf "%s\n" mot
else begin
if c + 1 <= 2 * n - i - 1 then
f (c + 1) (i + 1) (mot ^ "(");
if c > 0 then
f (c - 1) (i + 1) (mot ^ ")");
end;
in f 0 0 ""
C++ :
#include <iostream>
#include <string>
using namespace std;
int n;
void f(int c, int i, string mot)
{
if(i == 2*n)
{
cout << mot << endl;
return;
}
if(c+1 <= 2*n-i-1)
f(c+1, i+1, mot + '(');
if(c > 0)
f(c-1, i+1, mot + ')');
}
int main()
{
cin >> n;
f(0, 0, "");
return 0;
}
```[/spoiler]
Ben tu as une pile vide. A chaque parenthèse ouvrante, tu empile un truc. A chaque fermante tu dépiles un truc.
Le mot est bien parenthésé ssi (toutes les opérations de dépilage sont possibles et la pile est vide à la fin).
Implémenté, ça peut être un bête entier qui en doit pas devenir négatif et être nul à la fin.
Juste pour la forme, une fonction récursive non terminale utilise toujours une pile : sa pile d’exécution !
L’idée de la pile c’est plutôt cela : que suffit-il d’ajouter à coté d’un automate fini pour reconnaître le langage des mots bien parenthésés : une pile. On parle alors d’automates à piles.
Ici faire de la reconnaissance de mots bien parenthésés dans une machine de Turing (un langage de programmation lambda, quoi) c’est un peu écraser une mouche avec un marteau d’1 tonne.
oui oui…un conteur est vérifier si on a tout le temps >=0 et ==0 à la fin et basta.
Je parlais de pile avec le background non pas des automates (vraiment là c’est marteau/mouche) mais juste du fait que, intuitivement, c’est exactement ça : quand on croise une ouvrante, on en prend note et on efface la dernière de ces notes quand on croise une fermante.
Sinon oui, un automate sans pile ne marchera pas dans ce cas.
" En informatique, laisser la théorie aux théoriciens c’est prendre le risque de programmer comme en 1950." : ho que oui 
Comme dit un ami : il faut se méfier des gens qui font de l’informatique avec un crayon 
Selon certains, le papier en informatique est plus important que le papier aux toilettes. À méditer.