ja ovo radim pomocu dva steka, stek operatora i stek brojeva. kad se pokusha doda na stek operator manje vazhnosti u odnosu na onaj koji je na vrhu steka operatora taj sa vrha se ponishtava obavljajuci operaciju na dva broja sa vrha steka brojeva broj_2 operator broj_1.
ako se pojavi otvorena zagrada spushta se na stek, ako se pojavi zatvorena smatra se da je najmanjeg prioriteta i sve se pop-uje sa steka operatora i vrshe operacije nad stekom brojeva dok god ne naidje otvorena zagrada, nakon toga se ove dve zagrade ponishtavaju. za operatore kao shto rekoh vazhi klasichno pravilo, ako nailazi operator manje vazhnosti od onog na vrhu steka vrshi se ponishtavanje tog operatora uz aktivnost istog na prva dva broja sa steka brojeva, a procedura se ponavlja dok god ima operatora na vrhu steka koji su veceg prioriteta od nadolazeceg.
kad se predje preko ceo string (izraz) na kraju se prazni stek operatora i dobija tachan rezultat.
Evo primera:
treba reshiti 2*(2+2)
Code:
korak 1:
2
korak 2:
2 *
korak 3, nailazi otvorena zagrada koja je neutralna i samo se spushta na stek operatora:
2 (
*
korak 4:
2 (
2 *
korak 5:
2 +
2 (
*
korak 6:
2 +
2 (
2 *
korak 7, poshto je zatvorena zagrada manjeg prioriteta od bilo kog operatora svi operatori koji su manjeg prioriteta od operatora koji zahteva stek bice ponishtetni vrsheci svoju operaciju, a primenom formule drugi_sa_vrha OP prvi_sa_vrha:
)
-------
4 (
2 *
korak 8, zagrade koje se nadju na steku jedna do druge automatski se ponishtavaju ako je na steku otvorena a nailazi zatvorena:
4 *
2
korak 9, preostali operator na steku operatora se primenjuje nad dva preostala operanda na steku brojeva:
2*4=8
ne znam koliko je ovo efikasan algoritam, ali izbegavamo rekurziju, bukvalno u jednom prolasku kroz izraz reshavamo sve, bez obzira na postojanje zagrada.
Nadam se da sam bio jasan sa ovim algoritmom, dakle ovim izbegavamo potrebu za prevodjenje u poljsku postfiksnu notaciju ili sl.
evo programche ako hoce neko da testira:
http://www.mediafire.com/?fjmyhtm2hhx
[Ovu poruku je menjao vladar85 dana 15.02.2010. u 22:18 GMT+1]