dijkstrin algoritam (zadatak)

[5ra]

U prošlogodišnjem kolokviju ima zadatak da neki određeni aritmetički izraz pretvorimo iz infixa u postfix. zanima me moramo li u takvom zadatku to napisati u pseudo kodu ili baš u c-u.

_________________
http://www.youtube.com/watch?v=xYVoUEly-jA

[napraviculom]

takav zadatak smo radili na vjezbama. zadatak ne trazi da napises algoritam.
crtali smo tablicu (gdje smo stali, ispis, stog)

_________________
"I'm the operator with my pocket calculator"

[bubble]

A sto ako imam zadan postfix i trebam ga pretvorit u prefix. Ili sto ako imam zadan infix i trebam ga pretvorit u prefix.
Da li mi sami trebamo "doci" do tih algoritama na neki nacin? Da li postoji neka fora koja olaksava to? Mala modifikacija dijkstrin algoritma koju ja ne vidim?

[fireball]

prefix radis na isti nacin kao postfix samo na stog bacas operatore a operande ispisujes

_________________

[napraviculom]

[bubble]

A sto bi onda imao u ovom slucaju: (A + B) / (D + E) (infix)
Treba doci prefix: / + A B + D E

Mogu pomocu stabla.. ali one fore sa stackom, nikako.
Nasla sam na webu, ali prekomplicirano..
Mozda ne treba to.

[Luuka]

Mislim da je to najjednostavnije raznim grupiranjem...gledaš koji operator ima najveći prioritet pa se igraš...

(A+B)/(C+D)= { najveći prioritet je / } = / (A+B)(C+D) = {sad zagrade sređuješ} = /(+AB)(+CD) = {makneš zagrade } = /+AB+CD

_________________
"Bolje bi prolazio na faxu da sam na drogama nego na netu" - by a friend of mine
"Poslije spavanja doma spavanje bilo di mi je najdraža stvar" - by the same guy

[fireball]

@napraviculom: imas pravo, malo sam se zaletio... nisam razmisljao sta sam pisao

_________________

[bbbbbbb]

vezano uz infix->prefiks i obrnuto...
nisam sigurna vrijedi li ovo za svaki primjer i prihvaća li se ovakav algoritam, ali mislim da bi se to moglo izvesti nekako ovako:

infix->prefiks:
analogno kao u dijkstrin algoritmu za infix u postfix, ali sa sljedećim modifikacijama:
-čitamo infiks izraz s desna na lijevo!!!
-i kad ispisujemo operande (i operatore) ispisujemo ih s desna na lijevo
-na isti način stavljamo operatore na stog (čitajući ih s desna na lijevo), samo kad imamo zagrade to vršimo u obrnutom redoslijedu, tj. kad učitamo ')' stavljamo ga na stog, a kad učitamo'(' ispisujemo i uklanjamo operatore s vrha sve dok ne dodemo do ')' kojeg tada uklonimo

prefix->infiks:
analogno kao i prebacivanje postfixa u infiks (napravljeno na vježbama) sa sljedećim modifikacijama:
-čitamo prefiks zapis s desna na lijevo!!!
-na isti način operande spremamo na stog, ali kad naiđemo na operator ch računamo b1 ch b2 (obrnuto od postfix->infiks) (b1 je na vrhu stog a b2 'ispod' njega)

tj. zapravo me zanima je li 'dopušteno' ovo ispisivanje i učitavanje s desna na lijevo u algoritmu (koje se prilično jednostavno realizira u C-u)?

[RonnieColeman]

Da ne otvaram topik radi jedne rečenice, recite mi koje je zadnje gradivo koje ulazi u kolokvij odnosno što je zadnje rađeno na vježbama, zadnja rečenica zadnjih vježbi?

_________________
...He never had looked less like captain of any-thing, even his own soul.

[dosed_girl]

riješili smo zadatak: razradite impl. "obicnih" bin. stabala pomocu polja(kao za potp. bin. stablo) i prikazite u polju stablo (pa smo ga nacrtali).

_________________
a part of me gets sick / a part of me gets sore

[RonnieColeman]

Hvala ti.

_________________
...He never had looked less like captain of any-thing, even his own soul.