Nenad Božidarević
Februar 2015.

Parsiranje Bulovih izraza

Da, veoma dugo nisam pisao, ali me ovaj zadatak kopka već neko vreme, tako da sam najzad seo i bacio se na njegovo rešavanje.

U svom sada već skoro četiri godine starom tekstu Utisci sa testa za praksu u Microsoftu naveo sam zadatke sa kojima sam se tada susreo, ali nisam zalazio u to kako se oni rešavaju. Međutim, za ovo je očigledno bilo zainteresovanih ljudi, pa je jedan komentar na tekst bio pitanje kako se rešava zadatak sa parsiranjem Bulovog izraza. Prisetimo se kako je on glasio:

Dat je pravilno formiran logički izraz koji se sastoji od karaktera T, F, &, |, !, (, ) i razmaka. Potrebno je odrediti njegovu vrednost u linearnom vremenu. Pritom je & (AND) većeg prioriteta od | (OR).

Nažalost, na sâmom testu ovaj zadatak nisam uspeo da rešim sa zadatom (linearnom) složenošću, a nakon toga mu se nisam vraćao. Sada sam, međutim, došao u situaciju gde se već neko vreme nisam bavio algoritmima, i ovo je bila savršena prilika da se podsetim nekih najosnovnijih stvari, uključujući i C++a (jer na poslu radim frontend u PHPu i Javascriptu). Dakle, bacimo se na posao.

Pročitaj ostatak teksta