Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | evaluare.in, evaluare.out | Sursă | ad-hoc |
| Autor | Arhiva Educationala | Adăugată de |  Sima Cotizo •sima_cotizo |
| Timp execuţie pe test | 0.025 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Poti vedea testele pentru aceasta problema accesand atasamentele.Vezi solutiile trimise | Statistici
Evaluarea unei expresii
Se da un sir de caractere ce reprezinta o expresie aritmetica.
Cerinta
Afisati rezultatul obtinut prin evaluarea expresiei.
Date de intrare
Fisierul de intrare evaluare.in va contine pe prima linie un sir de caractere compus din cifre ( '0' - '9' ), operatorii '+', '-', '*', '/' si paranteze( '(', ')' ).
Date de iesire
In fisierul de iesire evaluare.out se va scrie un singur numar intreg care reprezinta valoarea obtinuta in urma evaluarii expresiei.
Restrictii si precizari
- 1 ≤ lungimea sirului ≤ 100 000
- operatorii '+','-','*' au semnificatia cunoscuta de la matematca, iar operatorul '/' reprezinta catul impartirii intregi a doua numere
- ordinea efectuarii operatiilor este cea normala
- se garanteaza ca atat rezultatul final, cat si orice rezultat intermediar nu va depasi in modul 1 000 000 000
Exemplu
| evaluare.in | evaluare.out |
|---|---|
| (1+1)*3+10/2 | 11 |
Indicatii de rezolvare
Probabil cea mai cunoscuta metoda de a evalua o expresie algebrica este scrierea ei in forma poloneza , urmata de evaluarea propriu-zisa, despre care puteti gasi mai multe aici .
Problema se poate rezolva si folosind arbori, metoda explicata pe larg aici .
De asemenea, o a treia metoda este explicata pe larg in aceasta sursa de 100 puncte.
Probleme asemanatoare (ca idee de rezolvare cel putin) de pe infoarena:
Cosmin: Fa te rog si niste teste mai mici (lungimea expresiei 500 de caractere), ca e o solutie simpla recursiva ce vreau sa o scriu.
Cotizo: Ok. Pot sa micsorez limita daca e nevoie. Oricum si eu am o solutie cu recursivitate indirecta pe care o mentionam la acea "a treia metoda" si nu stiu daca intra in timp inca, dar mie imi place pt ca e usor de inteles :)
Cosmin: nu trebuie sa micsorezi limita, doar sa dai teste gradate. Cu o solutie sa se ia 50 si cu alta 100.
