[C++, algoritmică] Numărarea parantezărilor booleane

Teoria este din cartea Algoritmica C++ de Vlad Sebastian Ionescu, Eugen Laslo.

Teorie

Fişierul paran.in conţine pe prima linie un număr natural N. Pe a doua linie se află N valori booleane (0 sau 1), iar a treia linie conţine N – 1 valori din mulţimea {-1, -2, -3}, reprezentând operatorii and, or, respectiv xor. Aceştia au priorităţi egale şi se consideră dispuşi între operanzii daţi.

Se cere numărul de parantezări valide existente astfel încât expresia rezultată să aibă rezultatul true.

Exemplu:
paran.in

3
1 0 0
-2 -1

paran.out:
1

Explicaţie: expresia dată este T or F and F. Există două parantezări valide: ((T or F) and F) şi (T or (F and F)). Se poate observa că, dintre acestea, doar a doua are valoarea true.

Spre deosebire de majoritatea problemelor prezentate până acum, aceasta este o problemă de numărare, nu de determinare a unui optim. Rezolvarea acestei probleme este similară cu problema numărării partiţiilor unui număr: va trebui să găsim subprobleme a căror rezultat să îl putem aduna pentru a obţine rezultatul unei probleme mai mari.

Este evident că abordările backtracking ies din discuţie, întrucât am fi astfel limitaţi la expresii de lungime nu mai mare de ~10.

Să punem la punct modul în care vom reţine datele. Vom considera valorile 1 / 0 date ca fiind nişte simboluri şi le vom reţine într-un vector boolean S. Operatorii daţi îi vom reţine într-un vector de numere întregi op, cu semnificaţie op[i] = operatorul dintre simbolurile i şi i + 1. Acesta va juca un rol foarte important în formula de recurenţă pe care o vom deduce.

Fie acum T[i][j] = câte posibilităţi există de a paranteza expresia formată din simbolurile [i, j] astfel încât rezultatul acesteia să fie true. Mai mult, vom calcula în paralel şi F[i][j] = câte posibilităţi există de a paranteza expresia formată din simbolurile [i, j] astfel încât rezultatul acesteia să fie false. Aceste două matrici se vor calcula similar cu modul de calcul al matricii de la problema înmulţirii optime a matricelor. T şi F vor depinde una de cealaltă, dar dependeţele nu vor fi circulare, deci le vom putea calcula pe amândouă în paralel.

Am identificat deja elemente descoperite prima dată în cadrul a două probleme distincte. Tocmai acest lucru face ca programarea dinamică să fie o tehnică greu de stăpânit: inexistenţa unui şablon de rezolvare a problemelor. De multe ori avem nevoie de tehnici pe care nu le-am mai întâlnit, sau de combinarea mai multor idei de rezolvare a altor probleme.

În primul rând ne punem problema cazurilor de bază: T[i][i] şi F[i][i] ar trebui să fie evident cum se calculează, aşa că nu vom insista asupra acestui aspect.

Să presupunem acum că vrem să aflăm numărul de parantezări valide şi adevărate (a căror rezultat este true) ale unei subexpresii formate din simbolurile [i, j]. Mai mult, presupunem că ştim care este numărul de parantezări valide şi adevărate (şi false) ale subexpresiilor [i, k] şi [k + 1, j], pentru orice 1 ≤ i ≤ k < j ≤ N. Dacă ştim să calculăm T[i][j] şi F[i][j] pe baza acestor informaţii, atunci putem aplica acelaşi procedeu pentru toate elementele de deasupra diagonalei principale, iar în final răspunsul problemei va fi dat de T[1][N].

Avem trei cazuri pentru un k fixat:

  1. Dacă op[k] = -1 (and), atunci adunăm la T[i][j] valoarea T[i][k] * T[k + 1][j], deoarece avem nevoie ca ambele subexpresii să fie adevărate, deci putem combina orice parantezare adevărată a acestora.
  2. Dacă op[k] = -2 (or), atunci este de ajuns ca doar una dintre subexpresii să fie adevărată. Vom aduna aşadar la T[i][j] valoarea A[i][k] * A[k + 1][j] – F[i][k] * F[k + 1][j], unde A[x][y] = T[x][y] + F[x][y]. Practic, se scad din totalul parantezărilor cele false, rămânând cele adevărate.
  3. Dacă op[k] = -3 (xor), atunci cele două subexpresii trebuie să aibă valori diferite (una adevărată, iar cealaltă falsă). Adunăm aşadar la T[i][j] valoarea:
    T[i][k] * F[k + 1][j] + F[i][k] * T[k + 1][j]

Valorile matricei F se calculează similar. Avem aşadar recurenţele:

Menţionăm că suma T[1][N] + F[1][N] este al N-lea număr Catalan. Acestea reprezintă, printre altele, numărul de parantezări valide formate din N paranteze.

Avem aşadar un algoritm cu timpul de execuţie O(N3), a cărui implementare nu ar trebui să fie o noutate.

Adăugirile mele

În figura de mai sus, cu cele 2 sume cu 3 ramuri fiecare:

  1. op[k] == -1 înseamnă că al k-lea operator (unde k începe de la 1 și crește) este ȘI.
  2. op[k] == -2 înseamnă similar SAU.
  3. op[k] == -3 înseamnă similar XOR (SAU EXCLUSIV).

A II-a ramură a sumei de la T este scrisă astfel:

op[k] == -2 înseamnă că această ramură se folosește doar când operatorul de pe poziția k este SAU.

Ea poate fi scrisă și astfel:
    ce e la această sumă în cazul când op[k] == -1 (când operatorul este ȘI), +(plus) T[i][k] * F[k+1][j] + F[i][k] * T[k+1][j].

Altfel scris:
T[i][j] = T[i][k] * T[k+1][j] + T[i][k] * F[k+1][j] + F[i][k] * T[k+1][j].

T[i][j] reprezintă numărul maxim de parantezări care se evaluează la true (spre deosebire de false) care se pot construi din elementele booleane (true sau false) din subsecvența S[i, j].
F[i][j] are valoare complementară lui T[i][j], și pentru oricare i și j date, A[i][j] = T[i][j] + F[i][j], în această relație putându-se muta elemente din membrul stâng în cel drept și invers.

Deci expresia de mai sus „T[i][k] * T[k+1][j] + T[i][k] * F[k+1][j] + F[i][k] * T[k+1][j]”  poate fi scrisă în cuvinte astfel:

parantezari true de la i la j =
    parantezari true de la i la k ORI parantezari true de la k+1 la j PLUS
    parantezari true de la i la k ORI parantezari false de la k+1 la j PLUS
    parantezari false de la i la k ORI parantezari true de la k+1 la j.

Mai sus, prin parantezari intelegem parantezari booleane, eventual complexe – exemple: T; T or F, ((T or F) and T) etc. Practic, se însumează produse care reprezintă combinații din tabelele de adevăr ale funcțiilor.
Factorul din stânga/dreapta reprezintă expresia din stânga/dreapta a unei perechi de expresii care împreună formează o nouă parantezare (combinație de paranteze).

O formulă generală de calcul al lui A[i][j] care se obține din posibilele combinații din tabelele de adevăr de mai jos este:
A[i][j] = T[i][j] + F[i][j] = T[i][k] * T[k+1][j] + T[i][k] * F[k+1][j] + F[i][k] * T[k+1][j] + F[i][k] * F[k+1][j].

Dacă i == j, A[i][j] este răspunsul la întrebarea „Câte parantezări sunt posibile dintr-o singură valoare booleană?”, dacă i != j, se aplică formulele de recurență.

Tabelele de adevăr ale operațiilor logice folosite:

AND (ȘI)
0
1
0
0
0
1
0
1

OR (SAU)
0
1
0
0
1
1
1
1

XOR (SAU EXCLUSIV)
0
1
0
0
1
1
1
0

Pentru exemplul dat (paran.in & paran.out), cele 3 matrice rezultat sunt (se afișează doar diagonalele principale și elementele care sunt deasupra ei):

T

  1 1 1
    0 0
      0

F

  0 0 1
    1 1
      1

A

  1 1 2
    1 1
      1

După cum se vede, valorile matricei T și cele ale matricei F sunt complementare una alteia.

Execuția pas cu pas

La citirea datelor,
N devine 3,
S devine [1, 0, 0] și
op devine [-2, -1] (lungimea lui op este lungimea lui S, – 1).

Se creează 2 matrice, T (numele vine de la True) și F (numele vine de la False), de dimensiuni N ori N, care se completează astfel:

1. toate celulele matricelor (eventual doar cele din diag. princip. și de deasupra) se inițializează cu 0.
2. toate celulele din diagonala principala a lui T se initializeaza cu S[i] si cele din diagonala principala a lui F se initializeaza cu 1 – S[i] (echivalent cu 1 – T[i][i]).
3. ultimul pas este parcurgerea celulelor în felul de mai jos și aplicarea formulelor de recurență din figura întâi:

i = N – 1 = 3 – 1 = 2

> j = 1
    pt. fiecare k de la i = 2 la j – 1 = 0, crescator
       [nu se execută] 

> j = 2
    pt. fiecare k de la i = 2 la j – 1 = 1
       [nu se execută]
> j = 3
    pt. fiecare k de la i = 2 la j – 1 = 2 [1 pas]
       > k = 2
           op[k] = -1 (AND)
           => T[i][j] (T[2][3]) = T[2][2] * T[3][3] = 0 * 0 = 0
              F[i][j] = A[2][2] * A[3][3] – T[2][3] = 1 * 1 – 0 = 1

i = 2 – 1 = 1

> j = 1
    pt. fiecare k de la i = 1 la j – 1 = 0
        [nu se executa]

> j = 2
    pt. fiecare k de la i = 1 la j – 1 = 1 [1 pas]
        > k = 1
           op[k] = -2 (OR)
           => T[1][2] = T[1][1] * T[2][2] = 1
              F[1][2] = F[1][1] * F[2][2] = 0 * 1 = 0

> j = 3
    pt. fiecare k de la i = 1 la j – 1 = 2
        > k = 1
           op[k] = -2 (OR)
           => T[1][3] = A[1][1] * A[2][3] – F[1][1] * F[2][3] = 1 * 1 – 0 * 1 = 1
              F[1][3] = F[1][1] * F[2][3] = 0 * 1 = 0
        > k = 2
           op[k] = -1 (AND)
           => T[1][3] = T[1][2] * T[3][3] = 1 * 0 = 0
              F[1][3] = A[1][2] * A[3][3] – T[1][2] * T[3][3] = 1 * 1 – 1 * 0

i = 1 – 1 = 0 < 1, sfarsit.

Matricile T și F se calculează doar pentru valorile de deasupra diagonalei principale, din colțul din dreapta jos a matricei, în zig-zag până sus.

Eu nu am găsit problema aceasta pe infoarena.ro.

Codul meu sursă

#include
using namespace std;

const int maxn = 101;

void citire(int &N, int S[maxn],
       int op[maxn], ifstream &in)
{
       in >> N;
       for (int i = 1; i <= N; ++i)
       {
              in >> S[i];
       }
       // op[i] = operatorul dintre simbolul i si i + 1
       for (int i = 1; i <= N – 1; ++i)
       {
              in >> op[i];
       }
}

void paran(int N, int S[], int op[],
       int T[][maxn], int F[][maxn])
{
       for (int i = 1; i <= N; ++i)
       {
              for (int j = 1; j <= N; ++j)
              {
                     T[i][j] = F[i][j] = 0;
              }
       }

       for (int i = 1; i <= N; ++i)
       {
              T[i][i] = S[i];
              F[i][i] = 1 – T[i][i];
       }

       // atentie la sensul parcurgerii
       for (int i = N – 1; i >= 1; –i)
       {
              for (int j = 1; j <= N; ++j)
              {
                     for (int k = i; k < j; ++k) // exclus j
                     {
                           int aik = T[i][k] + F[i][k],
                                  akp1j = T[k + 1][j] +
                                  F[k + 1][j];
                           if (op[k] == -1) // and
                           {
                                  T[i][j] += T[i][k] * T[k + 1][j];
                                  F[i][j] += aik * akp1j – T[i][k] *
                                         T[k + 1][j];
                           }
                           else if (op[k] == -2) // or
                           {
                                  T[i][j] += aik * akp1j –
                                         F[i][k] * F[k + 1][j];
                                  F[i][j] += F[i][k] * F[k + 1][j];
                           }
                           else // xor
                           {
                                  T[i][j] += T[i][k] * F[k + 1][j] +
                                         F[i][k] * T[k + 1][j];
                                  F[i][j] += F[i][k] * F[k + 1][j] +
                                         T[i][k] * T[k + 1][j];
                           }
                     }
              }
       }
}

int main()
{
       int N, S[maxn], op[maxn];
       int T[maxn][maxn], F[maxn][maxn];

       ifstream in(„paran.in”);
       citire(N, S, op, in);
       in.close();

       ofstream out(„paran.out”);
       paran(N, S, op, T, F);
       out << T[1][N] << endl;
       out.close();

       return 0;
}

Dacă se înlocuiește acest rând de mai sus din funcția main:

out << T[1][N] << endl;
cu următorul fragment de cod, programul afișează ce este deasupra diagonalelor principale și pe diagonalele principale din matricele T, F și A (se afișează frumos doar când numărul de parantezări este de o singură cifră).

out << ‘T’ << endl;
for (int i = 1; i <= N; ++i)
{
       for (int j = 1; j <= i; ++j)
       {
              out << ‘ ‘ << ‘ ‘;
       }
       for (int j = i; j <= N; ++j)
       {
              out << T[i][j] << ‘ ‘;
       }
       out << endl;
}

out << ‘F’ << endl;
for (int i = 1; i <= N; ++i)
{
       for (int j = 1; j <= i; ++j)
       {
              out << ‘ ‘ << ‘ ‘;
       }
       for (int j = i; j <= N; ++j)
       {
              out << F[i][j] << ‘ ‘;
       }
       out << endl;
}

out << ‘A’ << endl;
for (int i = 1; i <= N; ++i)
{
       for (int j = 1; j <= i; ++j)
       {
              out << ‘ ‘ << ‘ ‘;
       }
       for (int j = i; j <= N; ++j)
       {
              out << (T[i][j] + F[i][j]) << ‘ ‘;
       }
       out << endl;
}

Capturi de ecran

Lasă un răspuns

Completează mai jos detaliile tale sau dă clic pe un icon pentru a te autentifica:

Logo WordPress.com

Comentezi folosind contul tău WordPress.com. Dezautentificare /  Schimbă )

Fotografie Google

Comentezi folosind contul tău Google. Dezautentificare /  Schimbă )

Poză Twitter

Comentezi folosind contul tău Twitter. Dezautentificare /  Schimbă )

Fotografie Facebook

Comentezi folosind contul tău Facebook. Dezautentificare /  Schimbă )

Conectare la %s

%d blogeri au apreciat: