infoarena

Aici puteţi discuta despre problema Evaluarea unei expresii (http://infoarena.ro/problema/evaluare).

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

Dar ce bine e explicata in sursa...

Sursa aia chiar merge?  :o E prea tare.  :shock:

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 :P

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

Uhm .. sursa asta (http://infoarena.ro/job_detail/144801?action=view-source) 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 .. ?

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

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? 

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 :).

Da, acum merge mult mai rapid. Mersi Wef. =D>

Pe aceeasi idee se poate renunta si la recursivitatea indirecta, scurtand mai mult codul (http://infoarena.ro/job_detail/184939?action=view-source), si se poate adapta si pentru a construi un arbore de expresie (http://infoarena.ro/job_detail/184931?action=view-source) (care, odata construit, va fi foarte util in anumite probleme). :)

Foarte misto sursa :D

Cand am scris sursa mea (http://infoarena.ro/job_detail/145234?action=view-source), 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 ? :?

Am adaugat si cateva comentarii (http://infoarena.ro/job_detail/185143?action=view-source); sper sa fie usor de inteles - mie mi s-a parut ideea super  :thumbup: 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 (http://infoarena.ro/job_detail/185171?action=view-source) - poate va fi utila cuiva :)

 :thumbup: 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 (http://infoarena.ro/forum/index.php?topic=2778.25).

PS: Lucian, numele meu mic e Cotizo :P

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 :P - scuze pentru confuzie  :oops:

Am modificat pagina de la dijkstra :).

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.

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

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

Da.

Cum as putea sa mai obtimizez algoritmul ?? Ia 2 TLE, unu pestul 9, altul pe testul 10
Sursa este aici (http://infoarena.ro/job_detail/288962?action=view-source). Eu am implemetat  Shunting-yard algortihm (http://en.wikipedia.org/wiki/Shunting_yard_algorithm).
 

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

fgets citeste si "\n"

Da

ma bucur ca am suporteri   :yahoo:

Cine imi poate spune, va rog, de ce nu imi compileaza corect sursa #294972  :readthis:  :fighting:? Acasa merge... si inca bine (cred).
http://infoarena.ro/job_detail/294972

Cred ca "operator" e cuvant rezervat, mai nou, in pascal. Incearca sa-i zici functiei "is_operator" sau ceva de genul.

Da! Mersi pentru ajutor  :D . Abia acum am  downloadat Free Pascalul si am observat; pana acum aveam un alt Pascal  :P. Acum mai ramane sa fac un program de 100 de pcte, am primit numai 90 deoarece am rezolvat problema fara sa ma uit peste rezolvarile date.

am si eu o intrebare:de cate ori se poate trece prin sir  ??? .sau mai exact care e complexitatea pentru aceasta problema

O(lungimea stringului). Poti sa parcurgi o singura data.

foarte frumoasa sursa facuta de Lucian Boca :thumbup:

LE:
intrebare:

y = eval( x, expr(lev+1), *p++ );

programul intra in
expr(lev+1) dupa ce ii trimite *p ca parametru lui eval (p ca parametru nu este incrementat si ca pointer (global) este incrementat)
sau
expr(lev+1) dupa ce ii trimite *p ca parametru lui eval (p ca parametru nu este incrementat  si nici ca variabila)
sau
expr(lev+1) inainte sa ii trimita *p ca parametru lui eval (deci p global nu este incrementat)

multumesc anticipat, sunt nou in ale pointerilor

LE2: mda nu imi dau seama deloc!... am facut niste surse in care sa testez si mai mult m am incurcat

LE3:

pe linia unde y = eval(..) intra in expr fara ca *p sa fie incrementat. astfel in caz ca este  semn si paranteza ex (...+(...)  *p indica tot + si intra in eval unde ajunge dupa inca doua autochemari sa fie *p diferit de paranteza si sa intre in forul in care se creaza x dar acolo *p e diferit de [0,..,9] (pt ca a ramas la +) si x ramane  cu val 0 dupa care iese din toate si se termina programu fara sa termine de evaluat toata expresia

http://infoarena.ro/job_detail/479037?action=view-source


LE4: pentru testul 2
 "(296+(286+891+(82+179+358-(48)*(0/173))-(251)))"
programu meu returneaza 296, am mers cu debugu si am gasit problema (am scris mai sus) si nu stiu cum sa o rezolv...

si mai ciudat e ca imi da acelasi rezultat gresit si pe celalate surse care folosesc metoda recursiva. insa cand le trimit numai a mea e gresita...
si tot la solutiile care folosesc recursivitate (copiate din solutiile oficiale) primesc acest warring "evaluare.cpp:33: warning: control reaches end of non-void function" / are vreo legatura?

help va rog !

Asta e sursa ta, am modificat doar citirea ( am folosit fgets in loc de gets , si am luat 100 ) : http://infoarena.ro/job_detail/479050?action=view-source, si faza cu warningul e ca programul nu "stie" ca acea functie ( int val ) o sa se "termine" vreodata, adica cum ai avea functia
Pe acest cod o sa primesti aceeasi eroare . De ce ? Pentru ca daca a este != 2 , programul nu returneaza nimic. Asa e si aici : Daca programul nu merge pe nici o ramura a lui case, atunci nu o sa returneze nimic, dar sigur o sa mearga pe o ramura, dar programul nu stie asta. Asa ca adaugi un return 0 la sfarsit si ar trebui sa mearga :

ms frumos :hug:


2 chestii  daca ai poti sa la lamuresti..
care e diferenta dintre fgets (vad ca ii dai mai multi parametrii) si gets?
ce ar putea face ca sursa asta ( http://infoarena.ro/job_detail/185143?action=view-source ) sa dea reulztatul gresit pe calculatorul meu? 296 in loc de 1841 la testu 2 pe calculatoru meu...

1. fgets ( S, MAX, stdin ) citeste primele MAX elemente din fisierul stdin ( sau fisier deschis cu FILE ) , in charul S. Fata de gets, el citeste si caracterul de sf. de linie , adica '\n'. S[strlen(S) - 1] o sa fie '\n', pe langa ce la gets acest caracter este ultimul caracter , adica acelasi cu S[strlen(S) - 2].
2. Nu prea inteleg exact ce vrei sa zici cu aia ...... [LE] Am observat si eu, ma uit sa vad ce are ....

si eu am updatat sursa mea cu modificarea pe care ai mentionat o si primesc acelasi rezutlat gresit... daca si tie iti face la fel inseamna ca e ceva dubios :)

primesc acelasi rezultat gresit si pe sursele cu recurenta indirecta... ciudat nu?


greseala din programu meu nu avea legatura cu ultimu caracter... el se termina (ca si restu solutiilor cu recursivitate) dupa primu numar...

Eu am luat 100 cu prima sursa oficiala ( ceva de genu am implementat si eu ) . Si aia imi merge si pe pc. In rest nu stiu ....
[LE] Toate sursele imi merg exceptand a doua sursa ( cea mai compacta ) a lui Cotizo. Si de aici rezulta si sursa data de tine, a lui Lucian. Cea cu arbore merge bine ....

mie continua sa imi dea gresit...  :/ chiar daca pe evaluator primeste 100

Ai pus enter dupa terminarea expresiei ?
App: citeste cu fgets, nu cu gets.
Poate am inteles eu gresit, dar tu spui ca gets si fgets citesc caracterul '\n', dar il pun pe pozitii diferite ? Asta este gresit, gets nu concateneaza delimitatorul, pe cand fgets, da. Scuze daca am inteles eu prost.

Da, ai inteles gresit . Sa zicem ca avem stringul abcd, citit in S. Daca il citesti cu gets, o sa ai S[strlen(S)-1] = 'd' ( adica S[3] ) . Daca il citesti cu fgets, o sa ai S[strlen(S)-1] = '\n' ( adica S[4] ) . In rest, S[3] = S[3] ( dinainte ) si tot asa. Dar S[4] ( fgets ) != S[4] ( gets ) , adica '/0' != '\n' .
[LE] Am gasit o sursa pe ideea asta cu STL ( string ) si merge perfect. Nu stiu care poate fi problema , am tot cautat si nu am gasit nimic.

pe sursa asta http://infoarena.ro/job_detail/479201?action=view-source iau 100 de puncte pentru ca am modificat citirea cu fgets. dar mie tot imi da gresit pe exemplu "(296+(286+891+(82+179+358-(48)*(0/173))-(251)))", poate si pe altele. nu inteleg, parca e zona crepusculara.... am pus si enter la sfarsitul expresiei (in fis de intrare) si da tot gresit. raman recunoscator daca imi emplica cineva misteru asta

Evaluarea se face sub linux. Pe windows compilatorul are bug-uri, etc. Tu ai linux ca sa iti dea cum e pe infoarena ? :)

Nu are linux, dar nu pot sa inteleg cum de o sursa cu STL ( care e schimbat doar stringul, adica in loc de char e string ) merge ok ...

nu am linux...

Nu exista compilator de linux pentru windows ?

Compilator de linux pt windows nu exista. Exista cel mult o portare a lui pe windows. Oricum, treaba nu tine de compilator ci de sistemul de operare. Pe windows newline este \r\n, pe linux e \n, de acolo problema.

Ai zis o prostie, compilatoarele sunt aceleasi pentru ambele os-uri gcc, respectiv g++. Se comporta la fel pe ambele os-uri.
Incearca citirea cu stream-uri :-?? mie imi merge perfect orice ii fac...
Folosesti cumva MinGW Developer Studio ?

Tocmai ti-am explicat mai sus ca difera in functie de sistem. Incearca tu pe orice versiune a compilatorului mingw (portul gcc pe windows) sa afisezi cu %lld de exemplu. Plus ca difera chiar de la distributie de linux la distributie de linux.

Mingw, din cate stiu e versiunea gcc pt windows. Teoretic ar trebui sa mearga exact ce merge si pe linux. Daca nu merge, inseamna ca e bug (presupun). Corect, cu streamuri folosesc si eu cand trebuie sa afisez long long sau alte chestii, si sunt pe windows (cam rar, ma rog). Vad ca deviaza rau topicu' in topic de compilatoare.

daca trebuie sa introduc si functia sin   in expresie   de ex sa calculeze  sin(5)+1+5....
care ma poate ajuta?

Trebuie sa adaugi, cu o prioritate mai mare decat inmultirea, operatia de aplicare a unei functii asupra unei expresii. Incearca sa rezolvi problema apel (http://infoarena.ro/problema/apel) mai intai.

 Nu exista cazuri de genul 2-(-2) sau 4 * (-5)!

Cât face 27/3*3?

27

Se poate renunta la recursivitatea indirecta, arbori dar si la chestia aia pe nivele, folosind o singura functie recursiva. Ideea este ca atunci cand dai de un + sau - sa te comporti la fel cum s-ar deschide o paranteza imediat dupa acel operator de prioritate scazuta, iar cand dai iar de un astfel de operator faci la fel cum s-ar fi inchis paranteza, astfel returnand ceea ce ai calculat deja. In felul asta stii ca intotdeauna * si / vor avea prioritate, deoarece se vor gasi numai intre acele pseudoparanteze.

Stie cineva daca este vreun lucru in testul 7 care nu se afla in celelalte teste?

Din cate am vazut la cei cu incorect pe testul 8 (nu 7 cum ai zis tu, asa am vazut si la jobul tau), cred ca e de la tipul de date. Incearca sa pui int, nu short.

imi spune cineva daca raspunsul fina poate sa fie de genu 32,1 , adica numar real :?

raspunsul final poate fi doar numar intreg.

Am reusit sa fac problema foarte simplu (dupa cateva ore de incercari de implementare "heavy") cu ideea de paduri disjuncte in O(t logt) (t este numarul de termeni - numere). Gasesti prioritatea fiecarui operator si retii si pozitia operandului din stanga lui (asta ar trebui sa fie usor), dupa sortezi operatorii descrescator dupa prioritati si unesti padurea operandului din stanga cu cea a operandului din dreapta, actualizand in acelasi timp rezultatul padurii nou formate. Aceasta parte a algoritmului este practic liniara. Solutia a luat suta cu 8ms pe cel mai mare test.

Imi poate spune si mie cineva ce este gresit in sursa asta:  http://www.infoarena.ro/job_detail/1323695  (http://www.infoarena.ro/job_detail/1323695)?

Imi 3 Incorect si un KBS, dar pe laptopul meu imi da raspunsul bun pe aceste teste.

LE: Am rezolvat.

Am făcut cu Shunting Yard Algorithm :D și oleacă de OOP :) http://www.infoarena.ro/job_detail/1420260?action=view-source (http://www.infoarena.ro/job_detail/1420260?action=view-source)

Salut !
Imi spune si mie cineva va rog de ce iau 0 puncte  pe sursa asta .. nu e cea mai eficienta ..dar am luat testele la rand si afiseaza bine.

http://www.infoarena.ro/job_detail/1458914?action=view-source

Multumesc anticipat !

Pt problemele din arhiva educationala, fisierele de intrare/iesire sunt valabile pentru download. Pentru problema asta, e poti gasi aici: http://www.infoarena.ro/problema/evaluare?action=attach-list
Ia de acolo un fisier de intrare si vezi ce rezultat obtii pe el.. daca iei 0 puncte, atunci ar trebui sa fie diferit fata de rezultatul din fisierul de iesire :).. si asa iti vei putea da seama ce nu merge

Am aceeasi problema: evaluatorul imi da 0 puncte, cu toate ca am luat cateva teste din atasamente care dau bine pe calculatorul meu. Am citit pagina despre evaluator, dar tot nu inteleg ce am gresit. Folosesc librarii standard, afisez ce trebuie...

http://www.infoarena.ro/job_detail/1737859?action=view-source

Am rezolvat problema folosind tutorialul "Forma poloneza postfixata" de pe Youtube, de la adresa:
https://youtu.be/kdpldr28fgI

Link-ul spre articolul despre forma poloneza nu pare sa duca unde trebuie.
E acesta articolul corect?
http://ksuweb.kennesaw.edu/faculty/rbrow211/web_lectures/postfix/ (http://ksuweb.kennesaw.edu/faculty/rbrow211/web_lectures/postfix/)

Pare sa fie corect.