Clasele 9-10 lecția 13 - 10 dec 2014

From Algopedia
Jump to navigationJump to search

Parsere de expresii

Există multe moduri de a rezolva probleme bazate pe procesarea de text. Este important să înțelegem puțină teorie, să nu ne aruncăm cu capul înainte, deoarece este ușor de scris un cont lent sau cu buguri.

Notația infixată / prefixată / postfixată

  • 3 + 4: notație infixată
  • + 4 3: notație prefixată sau notație poloneză (sau forma poloneză etc.)
  • 4 3 +: notație postfixată sau notație poloneză inversă

Notațiile prefixată și postfixată au două mari avantaje:

  1. Nu necesită paranteze. (3 + 4) * 5 se transcrie în notație prefixată ca * + 3 4 5, iar în notație postfixată ca 3 4 + 5 *
  2. Se pot evalua ușor folosind doar o stivă
    • Pentru notația prefixată: de câte ori în vârful stivei apar două numere (iar înaintea lor se află un operator), se scot cele trei elemente de pe stivă, se evaluează expresia și se pune rezultatul în apoi pe stivă
    • Pentru notația postfixată: de câte ori în vârful stivei apare un operator (iar înaintea lui se află două numere), se scot cele trei elemente de pe stivă, se evaluează expresia și se pune rezultatul în apoi pe stivă

Când întâlnim o sumă de mai mulți termeni sau un produs de mai mulți factori, cel din stânga are prioritate. Cu alte cuvinte, 3 + 4 + 5 se scrie în notație postfixată ca 3 4 + 5 +, nu 3 4 5 + +. Aceasta din urmă ar fi echivalentă cu 3 + (4 + 5). Devine evident de ce avem nevoie de această prioritate dacă ne gândim la expresia 3 - 4 + 5. Dacă o reprezentăm ca 3 4 - 5 +, atunci valoarea ei este 4. Dacă însă o reprezentăm ca 3 4 5 + -, atunci valoarea ei este -6.

Reprezentarea arborescentă a expresiilor aritmetice

  • Din reprezentarea arborescentă rezultă imediat trecerea expresiei din notație normală (infixată) în notație prefixată.

Evaluarea expresiilor aritmetice

Să ne reamintim lecția despre automate finite deterministe. Am dori să procedăm asemănător și în cazul expresiilor: văzând următorul caracter de la intrare și ținând cont în ce stare suntem, să facem un calcul aritmetic și să trecem în altă stare.

Totuși, știm deja că anumite limbaje depășesc puterea DFA-urilor. De exemplu, expresiile aritmetice pot conține un număr arbitrar de mare de paranteze imbricate, deci nu o putem parsa cu un DFA (F vine de la finit). Ne mai trebuie un lucru: o stivă care să țină minte valorile parsate până acum. Vom folosi stiva care ne este cel mai la îndemână: cea a recursivității. :-)

  • gramatici independente de context
  • separația între tokenizer (lematizor) și gramatică

Programul rezultat este foarte scurt și simplu: Media:arithmetic-expression-parser.cpp

Probleme

Desigur, există o mulțime de probleme bazate pe parsare de text, dar iată-le pe cele date la OJI și la ONI în anii recenți.

  • Expresie (ONI 2011, clasa a 10-a)
  • Expresie (OJI 2011, clasa a 10-a) (da, au puțină imaginație la nume)
  • Ex (ONI 2011, clasa a 9-a)
  • Text (OJI 2010, clasa a 10-a)

Flood fill

Se dă o matrice de numere întregi unde unele valori (să zicem 0) semnifică spații goale, iar altele (să zicem 1) semnifică pereți sau obstacole. Algoritmul fill oferă o modalitate de a vizita toate spațiile goale accesibile dintr-un punct de pornire dat. În funcție de problemă, vecinătatea a două puncte se definește pe 4 direcții sau pe 8 (în această lecție, pentru brevitate, vom trata vecinătatea pe 4 direcții).

Această lecție se bazează pe lecția de la clasele 7-8.

Varianta de bază

O implementare recursivă scurtă și clară este: 

void fill(int l, int c) {
  if (l >= 0 && l < m && c >= 0 && c < n && a[l][c] == 0) {
    a[l][c] = 1; // marchează punctul (l, c) ca vizitat
    // ... eventual și alte procesări pentru acest punct

    fill(l - 1, c);
    fill(l, c + 1);
    fill(l + 1, c);
    fill(l, c - 1);
  }
}

Această variantă are două dezavantaje:

  1. Este lentă. De câte ori este vizitat punctul (l, c)? De atâtea ori câți vecini accesibili are, căci fiecare dintre acești vecini va apela exact o dată fill(l, c).
  2. Folosește multă memorie. Stiva utilizată de recursivitate poate ajunge la O(mn), după cum se vede în imaginea de mai jos.



Pornind de la punctul (4, 1) și presupunând că apelăm cei patru vecini în ordinea N-E-S-V, stiva va conține aproape toate punctele matricei. Aceasta se întâmplă indiferent de punctul de pornire și de ordinea vizitării vecinilor.

Bordarea matricei

Dacă bordăm matricea cu obstacole (valori 1), eliminăm patru din cele cinci condiții testate. De aici înainte, vom presupune că matricea este bordată și vom elimina condițiile de încadrare în limite.

Testarea înainte de reapelare

Putem testa dacă un vecin merită vizitat înainte de a face apelul recursiv. 

void fill(int l, int c) {
  a[l][c] = 1; // marchează punctul (l, c) ca vizitat
  // ... eventual și alte procesări pentru acest punct

  if (a[l - 1][c] == 0) {
    fill(l - 1, c);
  }
  if (a[l][c + 1] == 0) {
    fill(l, c + 1);
  }
  if (a[l + 1][c] == 0) {
    fill(l + 1, c);
  }
  if (a[l][c - 1] == 0) {
    fill(l, c - 1);
  }
}

Codul se complică un pic, dar acum elementul (l, c) va fi vizitat o singură dată. Primul lucru pe care îl face rutina este să marcheze punctul ca vizitat, ceea ce previne vizitele ulterioare.

Nu știu dacă devine mult mai rapid. Poate cineva dintre voi să testeze?

Reducerea memoriei prin folosirea de variabile globale

Prima regulă atunci când ne temem că recursivitatea poate avea prea multe niveluri este să reducem memoria folosită per nivel. Putem elimina toate argumentele funcției fill() printr-un artificiu urât, dar eficient. Declarăm variabilele l și c globale și le gestionăm noi înșine: 

int l, c;

void fill() {
  if (a[l][c] != 0) {
    return;
  }
  a[l][c] = 1;
  l--;
  fill();
  l++;
  c++;
  fill();
  c--;
  l++;
  fill();
  l--;
  c--;
  fill();
  c++;
}

Trebuie să avem grijă să modificăm variabilele l și c într-o manieră consecventă. Pentru a vă convinge că rutina funcționează, observați că, după fiecare 3 linii, variabilele l și c revin la valorile pe care le aveau la intrarea în funcție.

  • Aici ar merita inserată o discuție despre GOSUB în BASIC și despre cum poți să programezi structurat chiar atunci când limbajul nu te ajută (Sinclair BASIC nu avea instrucțiunea while).

Folosirea propriei stive

Putem folosi și propria stivă, asupra căreia avem ceva mai mult control decât asupra stivei compilatorului. Atunci algoritmul de fill devine iterativ. 

void fill(int l, int c) {
  a[l][c] = 1;
  s = stivă goală;
  push(s, l, c);
  while(s != stivă goală) {
    pop(s, &l, &c);

    if (a[l - 1][c] == 0) {
      a[l - 1][c] = 1;
      push(s, l - 1, c);
    }
    if (a[l][c + 1] == 0) {
      a[l][c + 1] = 1;
      push(s, l, c + 1);
    }
    if (a[l + 1][c] == 0) {
      a[l + 1][c] = 1;
      push(s, l + 1, c);
    }
    if (a[l][c - 1] == 0) {
      a[l][c - 1] = 1;
      push(s, l, c - 1);
    }
}

Flood fill cu linie de baleiere

Prezentăm în trecere o ultimă optimizare, cu mențiunea că este mai greu de implementat în timp de concurs. Pe de altă parte, algoritmul cu linie de baleiere este cu mult mai rapid, căci face mai puține apeluri recursive.

Algoritmul operează cu intervale orizontale (linii) definite prin triplete (l, c1, c2) cu semnificația „intervalul pe linia l între coloanele c1 și c2”. Algoritmul menține o stivă cu intervalele încă neevaluate. 

void fill(int l, int c) {
  s = stivă goală;
  push(s, l, c, c); // pornim cu un interval de un singur pixel
  while(s != stivă goală) {
    (l, c1, c2) = pop(s);
    extinde c1 către V;
    extinde c2 către E;
    setează pe 1 toate elementele de la (l, c1) la (l, c2);
    examinează liniile l - 1 și l + 1, între coloanele c1 și c2;
    pune pe stivă toate intervalele găsite;
  }
}

Puteți vedea acest algoritm în funcțiune (la viteză redusă) într-un vechi joc de ZX Spectrum, The Hobbit. Dacă vă întrebați de ce grafica este implementată așa, răspunsul este: pentru că e foarte economic. Când toată memoria disponibilă este 48 KB (inclusiv memoria video), fiecare octet contează. Cam de câți octeți este nevoie pentru a reprezenta una dintre imaginile pe care le vedeți?

Surse și statistici

Iată cinci implementări cu observații despre fiecare. Am rulat pe două teste mari (obținute prin convertirea unor PNG-uri monocrome în ASCII). Ele au 10 megapixeli, respectiv 4 megapixeli.

sursă algoritm rezultat
Media:flood-fill-1.cpp flood fill „chior” moare pe la nivelul 280.000 de recursivitate
Media:flood-fill-2.cpp matrice bordată moare pe la nivelul 280.000 de recursivitate
Media:flood-fill-3.cpp variabile globale moare pe la nivelul 560.000 de recursivitate
Media:flood-fill-4.cpp stivă gestionată de program folosește peste 1.000.000 de niveluri de recursivitate
Media:flood-fill-5.cpp scan line cu stivă gestionată de program folosește maxim 211 niveluri de recursivitate

Toate sursele presupun că matricea conține la început caracterele '.' și '*'. Apoi, din punctul de pornire, ele înlocuiesc '.' cu 'o'.

Aplicații

Flood fill se folosește, în general, pentru probleme de conexitate în matrice întregi, cum ar fi:

  • numărarea „insulelor” între care nu se poate circula;
  • calculul ariei fiecărei insule.

Temă

Retrieved from "https://www.algopedia.ro/wiki/index.php?title=Clasele_9-10_lecția_13_-_10_dec_2014&oldid=11018"