Algo/pascal : Génération d'un langage correspondant à une expression régulière

Version imprimable

20/02/2007, 02h41
Invité

Algo/pascal : Génération d'un langage correspondant à une expression régulière

(Supprimé)
20/02/2007, 07h16
PRomu@ld

Lorsque tu as une notation suffixe, tu peux utiliser une pile :

-> tu as une lettre ou une expression, tu empiles.
-> tu tombes sur un opérateur, tu dépiles les deux éléments précédents et tu empiles l'arbre en question.

Tu répètes le tout jusqu'à avoir fini d'analyser.

Ensuite il faut aussi que tu gères les cas d'erreur (pile vide et opérateur, pile avec plus d'un élément etu plus rien à traiter, ...)

Citation:

J'ai honte de poster mon code parce que ça marche pas du tout

Il ne faut pas, ton code peut nous aider à cerner là où tu as des problèmes.
20/02/2007, 12h27
pseudocode

Mon conseil: inverse le probleme.

Dans quelles cas une sequence de lettres n'est PAS valide ?

- Est-ce qu'une sequence peut commencer par un "a" ?
oui. Pourquoi ?

- Est-ce qu'une sequence peut commencer par un "c" ?
non. Pourquoi ?

Une fois que tu as repondu a ces deux questions, l'algo devient plus facile.

PS: c'est quand meme mechant comme ennoncé. Y a pas grand monde qui aura le bonus. :aie:

Citation:

Le sous-programme devrait afficher à l'écran "ac, ad, bc, bd".

Mince. J'avais zappé cette ligne :oops:. Bon oublie ce que j'ai dit, y a beaucoup plus simple (je me disais aussi que l'exo etait un peu balaise :aie: ). Comme j'ai oublié le Pascal depuis longtemps, ca va etre a toi de porter mon pseudo-java en Pascal.

La stategie consiste a "developper" l'expression algebrique, comme en math: (a+b).(c+d) = ac+ad+bc+bd
L'astuce consiste a gerer les resultats sous forme de liste L=(ab,ad,bc,bd)

On ecrit les fonctions qui représentent les operations:

add(L1,L2) --> L3 tel que add( (a,b,...) , (c,d,...) ) -> (a,b,c,d,...)
mul(L1,L2) --> L3 tel que mul( (a,b,...) , (c,d,...) ) -> (ac,ad,bc,bd,...)

Pour finir, on ecrit le parcours reccursif de l'arbre,en appelant les operations au fur et a mesure:
Code:

1 2 3 4 5 6 7 8 List expand(None n) { if (n.value=="+") return add( expand(n.left) , expand(n.right) ); if (n.value==".") return mul( expand(n.left) , expand(n.right) ); // Dans les autre cas, on traite une valeur List l = new List(); l.add( n.value ); return l; }
A la fin, expand() renvoie la liste des valeurs possibles :yaisse2:

Citation:

Envoyé par MasterMatt

En tout cas merci beaucoup Pseudocode, ton aide a été précieuse.

De rien. Ca m'a assez amusé de coder ca en java. :P

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
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
import java.util.ArrayList;
import java.util.List;
 
public class TreeExpander {
 
	// Node definition
	class node {
		public node left; 
		public node right;
		public String value;
		public node(String v) {
			this.value=v;
		}
	}
 
	// build the Tree
	private node buildTree() {
		// (A+B).(C+D)
		node root = new node(".");
		root.left = new node("+");
		root.left.left = new node("A");
		root.left.right = new node("B");
		root.right = new node("+");
		root.right.left = new node("C");
		root.right.right = new node("D");
		return root;
	}
 
 
	// add operator: (a,b)+(c,d) -> (a,b,c,d)
	private List<String> add(List<String> list1, List<String> list2) {
		List<String> list3 = new ArrayList<String>();
		list3.addAll(list1);
		list3.addAll(list2);
		return list3;
	}
 
	// mul operator: (a,b).(c,d) -> (ac,ad,bc,bd)
	private List<String> mul(List<String> list1, List<String> list2) {
		List<String> list3 = new ArrayList<String>();
		for(String l1:list1)
			for(String l2:list2)
				list3.add(l1+l2);
		return list3;
	}
 
	// expand the tree
	private List<String> expand(node n) {
		// operator +
		if (n.value.equals("+"))
			return add(expand(n.left),expand(n.right));
 
		// operator .
		if (n.value.equals("."))
			return mul(expand(n.left),expand(n.right));
 
		// otherwise it's a simple value
		List<String> list = new ArrayList<String>();
		list.add(n.value);
		return list;
	}
 
	// test this class
	private void test() {
		node root = buildTree();
 
		List<String> list = expand(root);
 
		for(String s:list) System.out.println(s);
	}
 
	public static void main(String[] args) {
		new TreeExpander().test();
	}
}