Discussion :

[AnozerOne]

Bonjour.

Dans le but de manipuler les arbres binaires, j'essaye de coder une calculatrice qui interprète une chaine de caractère en expression mathématique et forcément doit calculer le résultat.

Parce que c'est déjà suffisamment compliqué pour moi (à l'heure actuelle en tout cas), le résultat sera forcément un réel, et les paramètres seulement des entiers, avec les opérations de base, +/*-

Afin de me simplifier la vie, avant de chercher à calculer/parser la chaine de caractère, je formate le string de cette façon :

- je supprime tous les espaces " "
- tous les * implicites sont ajoutés : "5(6+2)" -> "5*(6+2)"
- quand 2 signes +- se suivent , le remplacer par l'opérateur équivalent. "5++6" -> "5+6"
- je met en évidence les opérateurs prioritaires * et / avec des ajouts de parenthèse : "5+4*7" -> "5+(4*7)"

En illustration de mes dires voici le code en vJass (langage pseudo orienté objet dédié à l'éditeur de jeu warcraft3)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
function GetResult takes string whichString returns real
    local integer length // length of the string whichString
    local integer i // used in loop
    local integer j // same
    local integer right_par = 0 // these 2 variables are used as an index inside whichString for paranthese adds
    local integer left_par = 0 // i could use only one instead but the code would be uglier
    local string s // used in loop
    local string s2 // same
    local string s3 // same
    local real r // result
    local INode n // binary tree created with the expression whichString
 
    // dans toutes les loop je pourrais limiter la reconstruction de la chaine whichString,
    // et à la place stocker les index nécessaires dans whichString
    // pour les appliquer à la fin de la loop
    // ca devrait etre plus performant mais plus difficile à faire et osef ...
 
    // delete " "
 
    set whichString = ReplaceString(whichString," ","",false)
    set s = SubStringBJ(whichString,1,1)
 
    if s == "" or s == null then
        debug call BJDebugMsg("syntax error")
        return 0
    endif
 
    // particular case : first character of whichString
    set s = SubStringBJ(whichString,1,1)
    if (s == "+" or s == "-") and IsInt(SubStringBJ(whichString,2,2)) then
        set whichString = "0"+whichString
    endif
 
    // delete "++" , "+-" , "-+" , "--" to simplify the parsing process
 
    set i = 0
    loop
    set i = i+1
    set s =  SubStringBJ(whichString,i,i)
    exitwhen s == "" or s == null
 
        // ideally s2 and s3 would be setted only when needed, but the code would be uglier
        set s2 = SubStringBJ(whichString,i+1,i+1)
        set s3 = SubStringBJ(whichString,i+2,i+2)
 
        if s == "+" then
            if s2 == "+" then // ++
                if s3 =="(" or IsInt(s3) then
                    set whichString = SubStringBJ(whichString,1,i) + SubStringBJ(whichString,i+2,StringLength(whichString))
                    set i = i+1 // skip useless check
                else
                    debug call BJDebugMsg("syntax error")
                    return 0.
                endif
            elseif s2 == "-" then // +-
                if s3 =="(" or IsInt(s3) then
                    set whichString = SubStringBJ(whichString,1,i-1) + SubStringBJ(whichString,i+2,StringLength(whichString))
                    set i = i+1  // skip useless check
                else
                    debug call BJDebugMsg("syntax error")
                    return 0.
                endif
            endif
        elseif s == "-" then
            if s2 == "+" then // -+
                if s3 =="(" or IsInt(s3) then
                    set whichString = SubStringBJ(whichString,1,i) + SubStringBJ(whichString,i+2,StringLength(whichString))
                    set i = i+1  // skip useless check
                else
                    debug call BJDebugMsg("syntax error")
                    return 0.
                endif
            elseif s2 == "-" then // --
                if s3 =="(" or IsInt(s3) then
                    set whichString = SubStringBJ(whichString,1,i-1) + "+" + SubStringBJ(whichString,i+2,StringLength(whichString))
                    set i = i+1 // skip useless check
                else
                    debug call BJDebugMsg("syntax error")
                    return 0.
                endif
            endif
        endif
 
    endloop
 
    // add 'implicites' *
    set i = 0
    loop
    set i = i+1
    set s = SubStringBJ(whichString,i,i)
    exitwhen s == "" or s == null
 
        if IsInt(SubStringBJ(whichString,i,i)) and SubStringBJ(whichString,i+1,i+1) == "(" then
            set whichString = SubStringBJ(whichString,1,i) + "*" + SubStringBJ(whichString,i+1,StringLength(whichString))
            set i = i+2 //  // skip useless check "x("
        endif
 
    endloop
 
    // add 'paranthèses' 'implicites' (opérators priority * and / )
 
    set i = 0
 
 
    // left to right
 
    loop
    set i = i+1
    set s = SubStringBJ(whichString,i,i)
    exitwhen s == "" or s == null
 
        if s == "*" or s == "/" then
            set j = i
 
            loop // left to right, on the right of the operator
            set j = j+1
            set s = SubStringBJ(whichString,j,j)
            exitwhen s == "" or s == null
 
                if j == StringLength(whichString) then
                    set right_par = j+1
                    exitwhen true
                endif
 
                if not IsInt(s) then // we have find the end of the value
                    set right_par = j
                    exitwhen true // endloop
                endif
 
            endloop
 
            set j = i
 
            loop // right to left, on the left of the operator
            set j = j-1
            set s = SubStringBJ(whichString,j,j)
            exitwhen s == "" or s == null
 
                if j == 1 then
                    set left_par = 0
                    exitwhen true
                endif
 
                if not IsInt(s) then // we have find the end of the value
                    set left_par = j
                    exitwhen true // endloop
                endif
 
            endloop
 
            set whichString = SubStringBJ(whichString,1,left_par) + "(" + SubStringBJ(whichString,left_par+1,right_par-1) + ")" + SubStringBJ(whichString,right_par,StringLength(whichString))
            set i = right_par + 1 // skip useless checks
        endif
 
    endloop
 
    call BJDebugMsg( "result == " + whichString)
 
    return 0.0
endfunction

C'est un langage très verbeux pseudo orienté objet et je me contenterais donc de donner ces précisions :

string -> chaine de caractère
BJDebugMsg -> affiche à l'écran le string donné en paramètre
SubStringBJ -> découpe un string, le premier caractère de la chaine a pour index 1 , et le dernier la longueur de la chaine.
IsInt -> fonction personnalisée qui revoie true si le string est un entier et false si ce n'est pas le cas.

La construction de nœuds me pose problème quand i s'agit d'expressions plus complexe que "<valeur 1> <opérateur> <valeur 2>", ou autrement dit quand il y a des parenthèses.

Je ne comprends pas comment procéder pour parser et construire les nœuds adéquats.
Même si je sais que les nœuds doivent être des opérateurs et les feuilles des valeurs et que j'ai une vague idée qu'une fonction récursive simplifierait le parsing/construction des nœuds.


Help.

[ToTo13]

Bonjour,

il faut tout d'abord commencer par faire un analyseur lexical afin de trouver les différents nombre, opérations, parenthèse.
Pour tu implémentes une grammaire d'expressions arithmétiques.

[AnozerOne]

Merci pour les liens, je suis en train de digérer peu à peu le premier lien, je lis le cours dans son entier.
Pourrais tu si possible me donner le lien d'un cours qui développe le sujet "analyseur lexical", stp ?

Je suis fort intéressé par la théorie, car j'ai dans mes objectifs de réaliser un préprocesseur d'un langage script, qui permettrait d'émuler de nouvelles fonctionnalités du dit langage.
Donc en quelque sorte créer un pseudo langage en transformant le code de l'utilisateur en code script valide.
Je n'aurais donc pas à faire une analyse lexicale du script ainsi généré car l'IDE dédié s'en chargera, mais par contre du pseudo langage avant qu'il soit parsé.