Poate că problemele de parsing vi se par un chin, întrucât, cel mai probabil, vă gândiți la o rezolvare folosind un stack, o metodă care necesită foarte mult timp la implementare și care este greu de înțeles.
În acest articol vă propun o metodă care este mai ușor de înțeles și care folosește recursivitatea indirectă.
Ne vom concentra asupra problemei #2638 de pe pbinfo. Ni se cere să evaluăm o expresie ce conține numere naturale si operatorii +, – și *. Să aruncăm o privire asupra unei astfel de expresii: 24-3*7+11*2-1
Putem observa că expresia este formată din mai mulți termeni, legați prin operatorii + sau -. Fie T1 = 24, T2 = 3*7, T3 = 11*2 și T4 = 1. Expresia se va transforma în: T1-T2+T3-T4 . Deja totul devine mai simplu. Următorul pas este să observăm faptul că, la rândul lor, termenii sunt formați dintr-un singur număr sau dintr-un produs de numere, legate prin operatorul *. Aceste numere le vom numi factori (de exemplu, T2 = 3*7, deci putem spune că, T2 = F1*F2, unde F1 are valoarea 3, iar F2 valoarea 7).
Cheia în rezolvare stă în scrierea unor funcții care să returneze aceste rezultate parțiale legate prin operatori cu aceeași prioritate (de exemplu, suma și diferența au aceeași prioritate). Mai mult, pentru a putea obține sume/diferențe/produse, avem nevoie, evident, de valori, deci vom avea încă o funcție care să ne returneze aceste numere (factori).
Funcția care calculează sumele sau diferențele arată în felul următor:
long long eval(){
long long ans = termen(); // luăm valoarea primului termen
while(s[p] == '+' || s[p] == '-'){
if(s[p] == '+'){
p++; // trecem de '+'
ans += termen();
}else{
p++; // trecem de '-'
ans -= termen();
}
}
return ans;
}
În mod similar va arăta și funcția care calculează produsele dintre numere:
long long termen(){
long long ans = factor(); // luăm valoarea primului factor
while(s[p] == '*'){
p++; // trecem de '*'
ans *= factor();
}
return ans;
}
În final, vom scrie și funcția care ne va returna valoarea factorilor:
long long factor(){
long long x = 0;
while(s[p] >= '0' && s[p] <= '9')
x = x * 10 + (s[p] - 48), p++;
return x;
}Dacă problema ne spunea că pot exista și paranteze rotunde, unde se găseau alte expresii de evaluat, putem modifica funcția factor() în felul următor:
long long factor(){
long long x = 0;
if(s[p] == '('){
p++; // trecem de '('
x = eval(); // evaluăm subexpresia
p++; // trecem de ')'
return x;
}
while(s[p] >= '0' && s[p] <= '9')
x = x * 10 + (s[p] - 48), p++;
return x;
}Ultimul pas este apelul din main, adică:
cout << eval();
Este foarte importat să definim înainte antetul fiecărei funcții, deoarece, atât funcția eval(), cât și funcția factor(), apelează funcții care, până la momentul respectiv, nu au fost definite. Le vom scrie antetul odată cu variabilele globale, apoi le vom defini.
string s; int p; long long eval(); long long termen(); long long factor();
Sper ca acest articol să vă ajute în rezolvarea problemelor de parsing. Funcțiile pot suferi modificări de la problemă la problemă, însă, este important să înțelegeți principiul din spate, pentru a putea rezolva cât mai multe probleme de acest tip.
Autor: Pirnog Theodor Ioan
Colegiul National „B. P. Hasdeu”, Buzău