Četvrti domaći

Zagrade sa prioritetom

Dat je izraz koji sadrži samo zagrade, pri čemu može sadržati sledeće vrste zagrada: (), [], {} i <>. Svaka vrsta zagrada ima svoj prioritet:

• () - prioritet $1$
• [] - prioritet $2$
• {} - prioritet $3$
• <> - prioritet $4$

Izraz je ispravan ako su sve zagrade ispravno uparene i ako ne postoji deo izraza gde se unutar zagrada manjeg prioriteta nalaze zagrade većeg prioriteta. Napisati program koji ispituje da li je dati izraz ispravan.

Ulaz

Sa standardnog ulaza se učitava izraz sačinjen od zagrada.

Izlaz

Na standardni izlaz ispisati DA ako je izraz ispravan, a NE inače.

Primer

Ulaz

<[()]{[]}>

Izlaz

DA

Primer

Ulaz

<[(]){[]}>

Izlaz

NE

Primer

Ulaz

<([]){[]}>

Izlaz

NE

Pandemija ASCII virusa

U svetu je zavladala pandemija ASCII virusa. Svaki ASCII virus je označen nekim ASCII karakterom.

Farmaceuti prate dolazak novih pacijenata i šalju lekove bolnicama po principu prvi došao – prvi lečen.
Međutim, postoje dva ograničenja:

1. Farmaceuti mogu proizvesti najviše k lekova u jednoj turi.
2. U jednoj isporuci lekova obrađuje se samo jedna grupa pacijenata, tj. pacijenti koji su najranije pristigli sa istim virusom.

Ulaz

Sa standardnog ulaza se unosi ceo broj k — maksimalan broj lekova po isporuci (1 ≤ k ≤ 10^6). Nakon toga, unosi se ceo broj q (1 ≤ q ≤ 10^6), a zatim i q upita u formatu:

• p c x - pojavila se grupa od x pacijenata sa virusom c.
• l - isporučeno je najviše k lekova za najranije pristiglu grupu pacijenata koji još uvek nisu izlečeni. Ukoliko u tom trenutku nema neizlečenih pacijenata, nakon ovog upita se ne dešava ništa.

Izlaz

Na standardni izlaz ispisati u zasebnim redovima preostale grupe pacijenata koji još uvek nisu izlečeni, počevši od najranije pristiglih.

Primer

Ulaz

6
5
p B 6
p A 3
l
p A 5
l

Izlaz

A 2

Primer

Ulaz

5
6
p B 6
p A 3
l
l
p A 3
p C 7

Izlaz

A 6
C 7

Primer

Ulaz

6
7
p B 6
p A 3
l
p A 3
l
p C 6
l

Izlaz

Najbalansiraniji nivo

Čvorovi u binarnom stablu pripadaju istom nivou ako su jednako udaljeni od korena. Koren pripada nivou $0$, njegova deca nivou $1$, njihova deca nivou $2$, i tako dalje.

Napisati program koji pronalazi najbalansiraniji nivo, odnosno nivo za koji važi da je apsolutna vrednost razlike broja čvorova u nivoima iznad i ispod njega najmanja moguća.

Ulaz

Sa standardnog ulaza se učitavaju elementi binarnog pretraživačkog stabla do kraja ulaza.

Izlaz

Na standardni izlaz ispisati redni broj najbalansiranijeg nivoa. U slučaju da postoji više nivoa koji su jednako balansirani, ispisati redni broj većeg. U slučaju greške, na standardni izlaz za greške ispisati $-1$ i prekinuti program sa izlaznim kodom neuspeha (1).

Primer

Ulaz

5 2 0 8 10 1 9 7

Izlaz

2

Primer

Ulaz

50 40 45 60 55 30 48 46 49 70 80 85 75

Izlaz

3

Primer

Ulaz

2 5 8

Izlaz

1

Parni putevi

Napisati program koji broji koliko ima čvorova u datom binarnom stablu u kojima postoji parni put do nekog od listova u podstablu čiji je on koren. Parni put sadrži samo čvorove sa parnim vrednostima.

Ulaz

Sa standardnog ulaza se učitavaju elementi binarnog pretraživačkog stabla do kraja ulaza.

Izlaz

Na standardni izlaz ispisati koliko postoji čvorova koj zadovoljavaju uslov zadatka. U slučaju greške, na standardni izlaz za greške ispisati $-1$ i prekinuti program sa izlaznim kodom neuspeha (1).

Primer

Ulaz

10 4 8 1 12 11 2 13

Izlaz

4

Objašnjenje

U pitanju su čvorovi 2, 4, 8 i 10.

Primer

Ulaz

1 2 3 4

Izlaz

1

Primer

Ulaz

10 4 7 1 12 11 3 13

Izlaz

0

Logički izrazi

Napisati program koji evaluira logički izraz predstavljen binarnim stablom. Svaki čvor stabla može biti ili operator (~ (negacija),& (konjunkcija), | (disjunkcija), -> (implikacija), <-> (ekvivalencija)) ili operand (T (true) ili F (false)). Listovi stabla su uvek operandi, dok su unutrašnji čvorovi uvek operatori. Svi operatori su binarni, osim negacije koja je unarni operator (pa će u stablu imati samo levo dete).Program treba da učita izraz u binarno stablo i zatim da izračuna vrednost izraza.

Napomena: zadatak se mora uraditi korišćenjem generičkih stabala. Potrebno je popuniti implementacije fajlova stablo_podatak.c i stablo_podatak.h.

Ulaz

Sa standardnog ulaza se učitava izraz u prefiksnoj notaciji. Svaki token (operator ili operand) je odvojen jednim razmakom. Na primer, izraz <-> & T ~ F -> F T predstavlja izraz (T & ~F) <-> (F -> T). Podrazumevati da je izraz ispravno zadat.

Izlaz

Na standardni izlaz treba ispisati vrednost evaluiranog izraza (T ili F).

U slučaju greške, na standardni izlaz za greške ispisati -1 i prekinuti program sa izlaznim kodom neuspeha (1).

Primer

stdin

<-> & T ~ F -> F T

stdout

T

Primer

stdin

| F -> ~ F ~ T

stdout

F