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.

Format izraza

Za početak, probajmo da formalizujemo od čega izraz može da se sastoji – smatraćemo da razmaci ne postoje, jer se njih lako možemo otarasiti. Ne sećam se tačno pravilne notacije, ali mislim da će ovo biti dovoljno jasno:

• <izraz> = <vrednost> <operand> <vrednost> <operand> <vrednost>…
  Izraz se sastoji od jedne ili više vrednosti između kojih su operandi.
• <operand> = & ili |
  Ovde ne uključujemo negaciju, jer je ona unarna operacija.
• <vrednost> = T ili F ili (<izraz>) ili !<vrednost>

Na primer:

• T & !(T | F) | !!F – podvučene su vrednosti u glavnom izrazu.
• Ako pogledamo drugu vrednost, videćemo da se ona može predstaviti kao !<vrednost>, gde je vrednost (T | F)
• Kako ova vrednost ima zagrade, potrebno je da zađemo u njih, nakon čega dobijamo nov podizraz sa dve vrednosti i operandom |.

Ako ovo zvuči pomalo konfuzno, možda će biti jasnije kada objasnim postupak koji ćemo pratiti.

Postupak

Pošto se traži linearna složenost, najviše smisla ima prolaziti redom kroz string i postepeno računati vrednost. Na osnovu formata izraza, nameće se sledeće rešenje:

1. Odredimo prvu vrednost u izrazu.
2. Pogledamo sledeći karakter, jer će to biti operand (ukoliko ga nema, došli smo do kraja i već imamo izračunatu vrednost).
3. Ukoliko je operand &, on ima prioritet, pa je potrebno da nađemo vrednost koja sledi iza njega i AND-ujemo je sa trenutnom vrednošću. Nakon toga se vraćamo na 2. korak i ponavljamo postupak.
4. Ukoliko je operand |, ne smemo ga “upotrebiti” odmah, jer iza njega možda postoji operand & koji bi morao da se izvrši prvi. Ono što možemo, doduše, jeste da izračunamo vrednost izraza desno od operanda, i onda da to OR-ujemo sa trenutnom vrednošću.
5. Kada dođemo do kraja stringa, ujedno smo našli i finalnu vrednost.

Što se tiče računanja vrednosti, postupak je prilično jednostavan:

• Ukoliko je u pitanju T ili F, to je vrednost.
• Ukoliko je prvi karakter ! možemo ga preskočiti, izračunati vrednost nakon njega, i negirati je.
• Ukoliko je prvi karakter (, vrednost je zapravo izraz, tako da preskačemo prvi karakter i parsiramo izraz u zagradama.

Kôd

#include <utility>
#include <string>
#include <iostream>

using namespace std;

// Koristimo pair<bool, int> da bismo mogli da propagiramo trenutnu
// vrednost zajedno sa trenutnom pozicijom u izrazu

pair<bool, int> parsirajIzraz(string izraz, int pozicija);
pair<bool, int> parsirajVrednost(string izraz, int pozicija);

pair<bool, int> parsirajIzraz(string izraz, int pozicija) {
  pair<bool, int> rezultat = parsirajVrednost(izraz, pozicija);

  // Ako obradjujemo ceo izraz, dosli smo do kraja kada obradimo sve karaktere.
  // Medjutim, ako obradjujemo podizraz, njegov kraj je kada naidjemo na
  // zatvorenu zagradu.

  while (rezultat.second < izraz.length() && izraz[rezultat.second] != ')') {
    pair<bool, int> novRezultat;

    if (izraz[rezultat.second] == '&') {
      novRezultat = parsirajVrednost(izraz, rezultat.second+1);
      rezultat.first = rezultat.first && novRezultat.first;
    } else {
      novRezultat = parsirajIzraz(izraz, rezultat.second+1);
      rezultat.first = rezultat.first || novRezultat.first;
    }

    rezultat.second = novRezultat.second;      
  }

  // Ukoliko smo dosli do zatvorene zagrade, preskacemo je i oznacavamo
  // sledeci karakter za obradu

  ++rezultat.second;

  return rezultat;
}

pair<bool, int> parsirajVrednost(string izraz, int pozicija) {
  switch (izraz[pozicija]) {
    case 'T':
      return make_pair(true, pozicija + 1);
    case 'F':
      return make_pair(false, pozicija + 1);
    case '!':
      pair<bool, int> vrednost = parsirajVrednost(izraz, pozicija + 1);
      vrednost.first = !vrednost.first;
      return vrednost;
    case '(':
      return parsirajIzraz(izraz, pozicija + 1);
  }
}

int main() {
  string izraz;

  cin >> izraz;
  
  cout << parsirajIzraz(izraz, 0).first << endl;
  
  return 0;
}

Složenost

Najzad, postavlja se pitanje – kako možemo biti sigurni da ovo ima linearnu složenost, s obzirom da se koristi rekurzija? “Trik” je u tome što rekurziju uvek pozivamo za sledeći karakter u izrazu, tako da jedan karakter nikada neće biti obrađen u više različitih poziva neke funkcije, što dalje znači da tokom izvršavanja konstantno idemo “napred” kroz string, i nad svakim karakterom vršimo konstantan broj operacija.