C/C++ - Evaluarea unei expresii artimetice

Post Title

Evaluarea unei expresii aritmetice( sau si logice) poate reprezenta  un subiect interesant pentru trasarea graficelor de functii sau pentru modificarea pozitiei unui obiect intr-un joc( ajungand la scripturi )
Etape:
        0. Descompunerea sirului de caractere in atomi
        1. Definirea variabilelor
        2. Transformarea expresiei in forma postfixta
        3. Evaluarea

0. Descompunerea sirului de caractere in atomi

  1.  
  2. #include <cstring>
  3. #include <string>
  4. #include <vector>
  5.  
  6. ...
  7.  
  8. char expr_chars[]=".........";
  9.  
  10. std::vector<std::string> atoms;
  11.  
  12. char *atom_ptr;
  13. atom_ptr=strtok(expr_chars," "); // caracterul ' ' este singurul separator
  14. while(atom_ptr!=nullptr)
  15. {
  16. atoms.push_back(atom_ptr);
  17. atom_ptr=strtok(NULL," ");
  18. }


De exemplu, expresia "12 + 28" va fi descompusa in 12,+,28. Expresia "12+28" ar fi mai dificil de procesat, dificultatea crescand odata cu numarul de operatori care devin si separatori. Poate parea inestetic ca o expresie sa fie scrisa avand doar caracterul spatiu drept separator, dar acest lucru face mai usoara extragerea atomilor, implicit evaluarea expresiei.

1. Definirea variabilelor:

  1.  
  2. std::map<std::string,float> vars; // primul caracter din numele variabilelor
  3. // trebuie sa fie o litera sau caracterul '_'
  4. //pentru a usura lucrul, valorile vor fi considerate ca fiind reale, indiferent daca sunt intregi sau reale
  5.  

Definirea variabilelor se face prin simpla inserare vars["name_var"]=value;

2. Forma postfixata( prietenoasa cu stiva)

Ex: 10 + 2 * ( 1 + 3 )   =>   10 2 1 3 + * +

Algoritm:
    - este nevoie de o stiva pentru operatori si una pentru forma finala
    - prioritate operatiilor:    /, *  = 1 // prioritate mare
                                      +, -  = 0 // prioritate mica

    Cat timp mai exista atomi executa
        Daca atomul curent este "(" se adauga pe stiva operatorilor
        Daca atomul curent este ")" se extrag din stiva operatori si se adauga la forma finala pana
            cand se intalneste atomul "(", care este sters din stiva operatorilor
        Daca atomul current este operator
            Daca operatorul din varful stivei are prioritate mai mare ca prioritatea celui curent atunci se
                extrag din stiva operatorilor operatori si se adauga la forma finala pana cand se intalneste
                    un operator cu prioritate mai mica sau egala. Se adauga in stiva operatorilor operatorul curent.
            Altfel se adauga operatorul curent in stiva operatorilor
        Altfel
            Daca atomul curent este o constanta sau o variabila de adauga la forma finala
    Daca in stiva mai sunt operatori se extrag si se adauga in forma finala

  1.  
  2. std::vector<std::string> op_stack, final_form;
  3. int current_atom=0;
  4. int op_stack_size=0;
  5.  
  6. while(atoms.size()>current_atom)
  7. {
  8. if(atoms[current_atom]=="("){ op_stack.push_back("("); ++op_stack_size;}
  9. if(atoms[current_atom]==")")
  10. {
  11. while(op_stack_size>0 and op_stack[op_stack_size-1]!="(")
  12. {
  13. final_form.push_back(op_stack[op_stack_size-1]);
  14. op_stack.pop_back();
  15. --op_stack_size;
  16. }
  17. op_stack.pop_back();
  18. --op_stack_size;
  19. }
  20. if(isOperator(current_atom)==true )
  21. {
  22. if(op_stack_size>0 and getPriority(op_stack[op_stack_size-1]) > getPriority(atoms[current_atom]))
  23. {
  24. while(op_stack_size>0 and getPriority(op_stack[op_stack_size-1]) > getPriority(atoms[current_atom]))
  25. {
  26. final_form.push_back(op_stack[op_stack_size-1]);
  27. op_stack.pop_back();
  28. --op_stack_size;
  29. }
  30. }
  31. else
  32. {
  33. op_stack.push_back(atoms[current_atom]);
  34. ++op_stack_size;
  35. }
  36. }
  37. else
  38. {
  39. final_form.push_back(atoms[current_atom]);// atomul curent e constanta sau variabila
  40. }
  41. ++current_atom;
  42. }
  43. for(int i=op_stack.size()-1;i>=0;--i) // se adauga la forma finala operatorii ramasi in stiva
  44. {
  45. final_form.push_back(op_stack[i]);
  46. }

3. Evaluarea:

Algoritm:

- este necesara o noua stiva

Cat timp nu sa ajuns la finalul formei postfixate executa
          Daca atom curent este constanta sau variabila atunci se adauga pe stiva valoarea indicata de acesta
          Daca atom curent este operator se va efectua operatia caracteristica operatorului. Sunt extrasi primi doi atomi din varful stivei, ce reprezinta operanzii, si este adaugat rezultatul pe stiva

Ex: 10 2 1 3 + * +
        1. stiva: 10
        2. stiva: 10 2
        3. stiva: 10 2 1
        4. stiva: 10 2 1 3
        5. stiva: 10 2 4
        6. stiva: 10 8
        7. stiva: 18
        Rezultatul e 18.

  1.  
  2. std::vector<float> eval_stack;
  3.  
  4. int current_atom=0;
  5.  
  6. while(current_atom<final_form.size())
  7. {
  8. if(isOperator(final_form[current_atom])==true)
  9. {
  10. int eval_stack_last=eval_stack.size()-1;
  11. /// operand1 operator operand2
  12. /// operator1 se gaseste la indicele eval_stack_last-1
  13. /// operator2 se gaseste la indicele eval_stack_last
  14. if(final_form[current_atom]=="+")
  15. {
  16. eval_stack[eval_stack_last-1]=eval_stack[eval_stack_last-1]+eval[eval_stack_last];
  17. eval_stack.pop_back();
  18. }
  19. if(final_form[current_atom]=="-")
  20. {
  21. eval_stack[eval_stack_last-1]=eval_stack[eval_stack_last-1]-eval[eval_stack_last];
  22. eval_stack.pop_back();
  23. }
  24. if(final_form[current_atom]=="/")
  25. {
  26. eval_stack[eval_stack_last-1]=eval_stack[eval_stack_last-1]/eval[eval_stack_last];
  27. eval_stack.pop_back();
  28. }
  29. if(final_form[current_atom]=="*")
  30. {
  31. eval_stack[eval_stack_last-1]=eval_stack[eval_stack_last-1]*eval[eval_stack_last];
  32. eval_stack.pop_back();
  33. }
  34. }
  35. else
  36. {
  37. if(isVariable(final_form[current_atom]))
  38. {
  39. eval_stack.push_back(vars[final_form[current_atom]]);
  40. }
  41. else
  42. {
  43. eval_stack.push_back(atof(final_form[current_atom]));
  44. }
  45. }
  46. ++current_atom;
  47. }
  48.  

La final, stiva va contine un singur element ce reprezinta rezultatul expresiei aritmetice.

Evaluatorul poate fi extins lejer pentru a suporta operati logice si relationale. Pentru folosirea in expresi a functiilor sin,cos,abs, este necesara o modificare consistenta a elaborarii formei postfixate. In acest caz parametrul functiei este calculat si pus pe stiva, de unde il preia functia folosita.

Ex:   1+sin( PI/2 )*5      =>     1  PI  2  /  call_sin  5  *  +


 

Autor articol

Comentarii

Comentariu adaugat de marian
Bravo alexandru pentru nou tau articol, se mai poate face putin refactoring, nu e ok partea de if-uri imbricate. Inca o data bravo pentru articol si la cat mai multe.
go to page top marian | 2016-06-28

  • 1
Trebuie sa fii logat sa poti lasa un comentariu Autentificare Inregistrare Logare cu Facebook
top