006 Evaluarea unei expresii

[•filipb]

Aici puteţi discuta despre problema Evaluarea unei expresii.

[•blasterz]

" De asemenea, o a treia metoda este explicata pe larg in aceasta sursa de 100 puncte. "

Dar ce bine e explicata in sursa...

[•pauldb]

Sursa aia chiar merge?  E prea tare. 

[•sima_cotizo]

Da, e sursa mea de 100. Initial nu voiam sa o pun pe asta la "explicate" dar am fost incurajat ca e "scurta si la obiect"... daca e nevoie am sa scriu si un comment cu o explicatie in ea si o retrimit

PS: fisierele ok nu au fost generate cu acea sursa

LE : acum am adaugat si o sursa mai bine explicata, sper ca se intelege ideea de rezolvare.

[•recviem]

Uhm .. sursa asta mie nu imi da pe nici un test.. nici macar 1+2.. iar daca pun o paranteza imi crapa mingw..

L.E. Pe OpenSUSE cu gcc 4.2.1 merge. Imi scapa ceva .. ?

[•astronomy]

Da. Pe infoarena nu se foloseste mingw si este posibil ca sursa sa se comporte diferit pe diferite compilatoare.

[•plastik]

Am nevoie de putin ajutor la ultimele doua teste.

Pe evaluator iau TLE la ele. Cand am dat si eu testele alea de la atasamente cu time, a mers in 0.107 la unul si 0.115 la al doilea. Are cineva idee cum sa modific sursa asa incat sa ia 100?

Eu fac evaluarea in alt mod, impartind expresia in 2 subexpresii cand intalnesc operanzi sau paranteze. Am luat 100 cu metoda asta la OJI-ul de anul trecut de la a 10-a cu directoare - fun times. Mi se pare foarte usor de inteles.

O pot optimiza cumva, sau trebuie sa invat evaluarea prin recursivitate indirecta? 

[•wefgef]

Tu ai complexitatea O(N^2) daca nu ma insel ... Ar fi bine sa te uiti pe sursele celorlati si sa inveti cum sa rezolvi problema in O(N) folosind recursivitate indirecta .

[•plastik]

Da, acum merge mult mai rapid. Mersi Wef.

[•amadaeus]

Pe aceeasi idee se poate renunta si la recursivitatea indirecta, scurtand mai mult codul, si se poate adapta si pentru a construi un arbore de expresie (care, odata construit, va fi foarte util in anumite probleme).

[•wefgef]

Foarte misto sursa

[•sima_cotizo]

Pe aceeasi idee se poate renunta si la recursivitatea indirecta, scurtand mai mult codul, si se poate adapta si pentru a construi un arbore de expresie (care, odata construit, va fi foarte util in anumite probleme).

Cand am scris sursa mea, m-am gandit sa fie usor de inteles si am scos in afara functia de extragere a unui numar ca sa pastrez simplitatea procedurii de evaluare... imi pare rau ca nu am comentat-o

Pe partea de arbori de expresii, este vreun loc in care acestia sunt mai utili decat evaluarea normala, cu recursivitate indirecta?
Oricum, sursa este draguta, cred ca daca o comentezi poate fi adaugata pe pagina problemei, nu ?

[•amadaeus]

Am adaugat si cateva comentarii; sper sa fie usor de inteles - mie mi s-a parut ideea super  si cred ca ar merita pusa in pagina cu problema (Sima, editeaza linkul din postul anterior, are de doua ori "http")

Referitor la arbori de expresii, eu ii foloseam cand apareau multe schimbari de variabile in expresii, cand trebuia sa transform in forma pre/postfixata expresia (cu arborele construit, asta devine o simpla parcurgere). Se mai pot face dinamici pe arborii de expresie (cate atribuiri valide a variabilelor exista pentru ca o anumita expresie logica sa fie tot timpul adevarata etc). Sigur ca toate problemele astea se pot rezolva si cu evaluari de genul recursivitate indirecta, insa algoritmii mi se par mult mai intuitivi pe arborii de expresie. Poate e doar o chestiune subiectiva...
Oricum, am comentat si sursa cu arborii - poate va fi utila cuiva

[•sima_cotizo]

  iar eu am adaugat linkurile in pagina problemei. Cred ca asa ar fi frumos, sa se prezinte idei interesante pe marginea temelor propuse in arhiv. educationala. In ultima vreme am vazut ca au aparut comentarii foarte utile si pe topicul pt Algoritmul lui Dijkstra.

PS: Lucian, numele meu mic e Cotizo

[•amadaeus]

Multumesc   Intr-adevar, au aparut cateva idei interesante pe topicul referitor la algoritmul lui Dijkstra, poate cei care are drepturi de editare acolo le vor lua in considerare. S-ar putea face si o pagina despre Bellman-Ford - dar deja discutia devine off-topic.

In privinta numelui, imi pusesem si eu intrebarea, insa n-am insistat prea mult pentru a gasi un raspuns - scuze pentru confuzie 

[•wefgef]

Am modificat pagina de la dijkstra .

[•Marius]

Eu folosesc http://en.wikipedia.org/wiki/Shunting_yard_algorithm pentru evaluarea expresiilor. Cei care nu pricep recursivitatea indirecta (ca mine) il pot folosi pe acesta.

[•amadaeus]

Foloseam si eu asta la inceput, numai ca tot codul devine destul de stufos. Cu recursivitate, procedura are vreo 15 linii

[•jean]

o intrebare : poate fi cv de genul 2-(-2) sau 2*(-2) ? 

[•pauldb]

Da.

[•alexandru92]

Cum as putea sa mai obtimizez algoritmul ?? Ia 2 TLE, unu pestul 9, altul pe testul 10
Sursa este aici. Eu am implemetat Shunting-yard algortihm.
 

[•AnDrEwBoY]

http://infoarena.ro/job_detail/185143?action=view-source
Am incercat sa folosesc pe sursa aceasta freopen si iau 10 puncte.exista vreo explicatie?(

[•rupra]

fgets citeste si "\n"

[•andrei-alpha]

Da

[•rupra]

ma bucur ca am suporteri