algorithme de la notation polonaise inverse
Bonjour,
une petite explication de l'algo avant tout avec l'exemple suivant :
Le calcul ((1 + 2) × 4) + 3 peut se lire intuitivement :
je mets 1, (1)
j'ajoute 2, ( 2 + )
je multiplie par 4, (4 ×)
j'ajoute 3. (3 +)
ce qui donne simplement l’opération développée suivante 1 2 + 4 × 3 +
Bon, j'ai trouvé un code (si dessous) qui fait le calcul mais il ne permet pas d'afficher l’opération développée avant de faire le calcul et je veux savoir s'il ya une possibilité de faire sans passer par les piles
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
| /* evaluation d'une formule arithmetique (+, -, * et entiers) et sans vraies parentheses */
#include <stdio.h>
/* à cause de strtol() */
#include <stdlib.h>
#define Base 10
/* a est la chaine à évaluer, les nombres sont écrits en base 10 */
int calcul (char *a)
{
char *p = a;
char *r = a;
char **q = &r;
/*
La chaine est vue comme une grande somme/différence de termes qui sont des produits.
Chaque produit est placé dans P et une fois complètement calculé, il est ajouté à S.
La chaine est supposée bien construite ie elle représente une formule mathématique valide.
*/
int P = 1, S = 0;
char signe = '+';
/* tant qu'on a pas examiné toute la chaine */
while (**q != '\0')
{
do /* Evaluation du produit courant */
{
if (*p == '(')
{
p++;
P *= strtol (p, q, Base);
*q = *q + 1;
p = *q + 1;
}
else
P *= strtol (p, q, Base);
p = *q + 1;
}
while (**q == '*');
/* On ajoute ou on retranche le produit au S courant */
if (signe == '+')
S += P;
else
S -= P;
/* on réinitialise */
signe = **q;
P = 1;
}
return S;
}
int main (void)
{/* Exemple illustratif */
char *a =
"2*3+8*2*4-8*4*2+8*(-9)*(-7)-8*(-10)*5-9*(-7)*(-9)*11+(-2)*3+5555";
printf ("%s =\n%d\n", a, calcul (a));
return 0;
} |
