Dotaz: Shuting-yard algoritmus a unární mínus

[Jardík]

Snažím se přepsat svojí semestrálku z javy do C++ a použít ji tak jako semestrálku

Jelikož ten parser v javě byl né moc efektivní, snažím se implementovat Shunting-yard algoritmus. Už to mám tak tak hotové, ale potřebuji do toho dád "unární mínus". Tj. např. -1^-5^5 ... -(1^(-(5^5))). Unární mínus místo obyčejného mi to rozpozná, ale nevím, jakou mu mám dát prioritu, jak je asociativní, nějak nakoupnou a zakomponovat to do toho postupu na wiki.

Odpovědi

[Ladicek]

Tenhle algoritmus neznám, takže můžu říct jenom tolik: gramatika aritmetického výrazu je triviální, takže starý dobrý rekurzivní sestup a jedu

No, každopádně unárnímu mínus patří priorita nejvyšší (jak je vidět z té gramatiky).

[Jardík]

Už se mi to podařilo dodělat hnusnou podmínkou.

Právě rekurzi jsem tam nechtěl Proto jsem se pustil do tohodle. Teď ještě vymyslet, jak to "zkompilovat" do assembleru, aby se to superrychle vyhodnocovalo

[Ladicek]

Praví muži umí dělat rekurzi bez rekurze, a GCC myslím dělá optimalizaci tail callů, takže CPS je jasná volba

Ne, na aritmetické výrazy je tenhle algoritmus asi super, zvlášť pokud se člověk spokojí s vyhodnocováním zásobníkem.

[Ash]

Praví muži už nejsou :)