postfiksna oblika aritmetičnega izraza

http://www.webis.de/pan-09/competition....


Da ti olajšam delo. Imaš na prosojnici 6 lep primer od strani 14 naprej.

Zadeve so dejansko dokaj simpl, samo moraš vedet kaj delaš.

Kako zadeve v principu delujejo:
(a+b) * c -> evaluacija izraza je dejansko pregled dvojiškega drevesa *{+{a,b},c} kjer je to poljski zapis (oz. prefixna oblika oz... kakorkoli že to imenuješ). Nižja kot je prioriteta operatorja, višje v drevesu živi (operator, ki se "evaluira" zadnji, je v korenu). Potenciranje je "skoraj brezveze" v smislu, da lahko ti izraz na neko potenco obravnavaš kot spremenljivko v začetnem računu in jo evaluiraš posebej, v novem drevesu. Dejansko na ta način lahko notri zapakiraš funkcije ipd. Npr, x * sin(x) narediš preprosto tako, da v drevesu originalnega izraza uporabljaš sin(x) kot spremenljivko.

Vrednosti posameznih spremenljivk vodiš v enem seznamu (če boš delu v c++, list, java ma ziher kaj implementirano itd.).

Ko boš to razumu, ti bo naloga izi.

Kako ponucat sklad:
Sklad uporabiš pri pregledu drevesa. Načeloma se drevesa splača pregledovati rekurzivno (simpl za napisat), samo zaradi mazohističnih oz. hitrostnih vzgibov lahko delaš pregled drevesa s skladom (načeloma je to DFS za nek splošn graf). Na hitro: pri rekurzivnem premem pregledu (na ta način dobiš npr prefixno obliko izraza, če maš v drevesu računski izraz): obdelaš koren, pregled levega poddrevesa,pregled desnega poddrevesa.
Brez rekurzije narediš to s skladom:
pregled(struct node *koren){
stack s;
s.push(koren);
while (!s.empty()){
node tmp = s.pop();
s.push(tmp.desni());
s.push(tmp.levi());
tmp.naredinekaj();
} //while
}//pregled

Tko nekak narediš nerekurzivni pregled: na sklad vržeš trenutno vozlišče, nato vržeš gor desnega in levega sina, ter pregledaš trenutno vozlišče. To počneš tokler sklad ni prazn - dejansko je še boljša do while zanka...

PS. ok, iz naslova vidim da rabiš postfix, samo gre za praktično isto stvar.