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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
|
//Retrait de tout espace (Il est inutile de traiter les espaces)
//Il faut remplacer le point par une virgule, sinon cela pose des problème de Parse
//et de détection des nombres (on peut aussi en interdire la saisie au préalable)
chaineInput = chaineInput.Replace(" ", "").Replace(".", ",").ToUpper();
//Boucle de parcours de la chaine passée en entrée, chaques éléments de la chaine ne sera lu, qu'une, et qu'une seule fois,
//il n'y a donc qu' N itérations
foreach (char caractere in chaineInput)
{
/********************************************************************************
********** ETAPE 1 : Creation des tokens de nombres / variables / fonctions ****
********************************************************************************/
//Permet de déterminer s'il s'agit d'un nombre
if (string.IsNullOrEmpty(chaineLectureVariable) && EstNumeric(caractere))
{
//On enrichi la chaine tant qu'on trouve un morceau de nombre (permet la constitution de nombre double par incrémentation de lecture)
chaineLecture += caractere;
//On passe au caractère suivant, puisque le caractère courant a été traité
continue;
}
//S'il ne s'agit pas d'un nombre, ni d'un operateur, ni d'une parenthèse, ni d'un séparateur de fonction,
//il s'agit donc d'une variable prédéfinie OU d'une fonction
//De la même maniere que la construction des nombres doubles, on construit la variable sur plusieurs itérations
if (string.IsNullOrEmpty(chaineLecture) && !EstOperateur(caractere) && !caractere.Equals('(')
&& !caractere.Equals(')') && !caractere.Equals(';'))
{
//Construction de la variable
chaineLectureVariable += caractere;
//On passe au caractère suivant, puisque le caractère courant a été traité
continue;
}
//Si chaineLectureVariable on est deja dans la constitution d'une variable
//Si on détecte une parenthèse ouvrante après le nom de variable c'est qu'il s'agit d'une fonction
if (!string.IsNullOrEmpty(chaineLectureVariable) && caractere.Equals('('))
{
//Detection d'une fonction
//On ajoute la fonction au stack comme un opérateur
listStack.Push(chaineLectureVariable);
chaineLectureVariable = string.Empty;
//Ajout de la parenthèse et passage à la lecture suivante
listStack.Push(caractere.ToString());
listStack_parametrage.Push(1);
continue;
}
//Si un token de nombre à précédement été constitué on l'ajoute à la queue
if (!string.IsNullOrEmpty(chaineLecture) && EstNumeric(chaineLecture) && !chaineLecture[chaineLecture.Length - 1].Equals(','))
{
listOutput.Enqueue(chaineLecture);
//Si un nombre a été détecté, il y a précédence par un nombre, donc opération de calcul sur le symbole '-'
precNum = true;
chaineLecture = string.Empty;
}
else
{
//Erreur, un nombre a été mal renseigné (ex nombre decimal incomplet => 3. ou 3.h (avec un caractère))
if (!string.IsNullOrEmpty(chaineLecture))
{
throw new UserException("L'un des nombres renseignés est incorrect.");
}
}
//Si un token de variable prédéfinie à précédement été constitué on l'ajoute à la queue
if (!string.IsNullOrEmpty(chaineLectureVariable))
{
listOutput.Enqueue(chaineLectureVariable);
//Si une variable prédéfini a été détecté, il y a précédence par un nombre, donc opération de calcul sur le symbole '-'
precNum = true;
chaineLectureVariable = string.Empty;
}
//Les point-virgules agissent comme séparateur de nombres (pour les fonctions),
//permettent de compter les parametres présents dans la fonction et
//agissent comme des parenthèses droite (sans retrait de parenthèse gauche)
if (caractere.Equals(';'))
{
//L'ensemble des opérateurs doivent être dé-stacker avant le passage au parametres suivant
while (listStack.Count > 0 && !listStack.Peek().Equals("("))
{
listOutput.Enqueue(listStack.Pop().ToString());
}
//Il reste forcement la parenthèse gauche pour identifier le début de fonction, sinon => erreur de parenthèsage
if (listStack.Count.Equals(0))
throw new UserException("Problème de parenthèsage");
//Incrémentation du nombre de parametres à chaques identification du symbole ';'
listStack_parametrage.Push(listStack_parametrage.Pop() + 1);
//Lorsque l'on dépile on retombe sur une parenthèse, il n'y a donc pas précédence par un nombre
precNum = false;
continue;
}
/***********************************************************************************************************
****** ETAPE 2 : Creation des tokens operateurs_arithmetiques et de la gestion des nombres negatifs *******
***********************************************************************************************************/
//s'il s'agit d'un opérateur on ajoute au stack
if (EstOperateur(caractere))
{
if (caractere.Equals('-') && (listOutput.Count.Equals(0) || (listStack.Count > 0 && listStack.Peek().Equals("(") && !precNum)))
{
//Gestion des nombres/variables negatifs :
//Si le nombre est écrit au debut de la chaine (ex : -5 + 6) ou suite à une parenthèse (ex : -5*(-6))
//Dans ce cas on ajoute un zero avant d'ajouter l'operateur (ex: 0 - 5 + 6 // 0-5*(0-6))
listOutput.Enqueue("0");
listStack.Push(caractere.ToString());
continue;
}
else
{
parcourStack = true;
//Verification de la précédence afin de déterminer si on ajoute l'operateur à la queue ou au stack
while (parcourStack)
{
if (listStack.Count > 0 && Precedence(caractere, listStack.Peek()[0]))
{
//si la priorite : caractere <= listack.peek()
listOutput.Enqueue(listStack.Pop().ToString());
}
else
{
//s'il n'y a pas de précédence caractere > listack.peek OU caractere est autre chose qu'un opérateur
listStack.Push(caractere.ToString()); //On ajoute l'opérateur à la liste STack
parcourStack = false; //Arrêt de la boucle de lecture
}
}
}
//Si un opérateur a été détecté, il n'y a pas précédence par un nombre
precNum = false;
//On passe au record suivant
continue;
}
/**************************************************************************************
****** ETAPE 3 : Creation des tokens de parenthèse ET de gestion des fonctions *******
**************************************************************************************/
//Dès que l'on rencontre une parenthèse gauche on la stack, elle servira au dépilement (plus tard dans l'algo)
if (caractere.Equals('('))
{
listStack.Push(caractere.ToString());
//Si une parenthèse a été détecté, il n'y a pas précédence par un nombre
precNum = false;
//On passe au record suivant
continue;
}
//Lorsque l'on trouve une parenthèse fermante on traite l'ensemble du contenu des parenthèse
if (caractere.Equals(')'))
{
//Tant que l'on ne trouve pas de parenthèse gauche on depile les operateurs_arithmetiques dans la file
while (listStack.Count > 0 && !listStack.Peek().Equals("("))
{
listOutput.Enqueue(listStack.Pop().ToString());
}
//En sortie de boucle on controle le premier element de la pile
if (listStack.Count > 0 && listStack.Peek().Equals("("))
{
listStack.Pop(); //On retire la parenthèse ouvrante de la pile, car elle a été traitée
//On recompte le nombre d'éléments du stack pour s'assurer qu'il ne s'agisse pas d'une parenthèse non attaché à une fonction
if (listStack.Count > 0 && EstFonction(listStack.Peek()[0]))
{
//Ajout nombre parametrage
listOutput.Enqueue(prefix_parametre + listStack_parametrage.Pop().ToString());
//Une fois les parametres ajoutés, on peut ajouter la fonction qui utilisera le parametrage
listOutput.Enqueue(listStack.Pop());
precNum = true;
}
continue;
}
else
{
throw new UserException("Problème de parenthèsage");
}
}
//La boucle est pre-interrompue après tout traitement, cette ligne ne doit jamais s'executer sinon => erreur
//ex : probleme de nombre decimaux incomplets
throw new TechnicalException("Une erreur est survenue, problème technique, algorithme mal implémenté.");
} |
[C#] Shunting-Yard & Calcul d'un RPN [Algo. Postfix]
Répondre avec citation
Partager