Note de curs, probleme algoritmică, 6 ianuarie 2014

În acest curs am discutat despre problema Bool.

Cerință

Să se evalueze o expresie cu operanzi (true sau false) și operatori (not, and și or) booleeni în care operanzii sunt constante sau variabile cu valori cunoscute.

Rezolvare

Cele mai simple expresii sunt cele în care apare doar o constantă. Vom nota acest tip de expresii cu C:

C = "TRUE" | "FALSE"

Alte expresii simple sunt cele în care apare doar o variabilă. Vom nota acest tip de expresii cu V:

V = "A" | "B" | "C" | ... | "Z"

Deoarece aceste tipuri de expresii reprezintă un singur operand, fără niciun alt operator, vom grupa cele două tipuri de expresii într-unul singur, notat cu X:

X = C | V

Cele mai simple expresii, care conțin doar operatorul not și un operand vor fi notate cu N:

N = "NOT " + X

Dorim să extindem definiția lui N astfel încât să acopere expresiile care conțin oricâți operatori not (inclusiv 0) și un operand:

N = X | "NOT " + N

Pe baza expresiilor de tip N putem obține expresii puțin mai complicate, care conțin operatorul and, cu o precedență mai mică decât not. Vom nota acest tip de expresii cu E:

E = N + " AND " + N

Dorim să extindem definiția lui E astfel încât să acopere expresiile care conțin oricâți operatori and (inclusiv 0):

E = N | N + " AND " + E

Pe baza expresiilor de tip E putem obține expresii și mai complicate, care conțin operatorul or, cu cea mai mică precedență. Vom nota acest tip de expresii cu O:

O = E + " OR " + E

Dorim să extindem definiția lui O astfel încât să acopere expresiile care conțin oricâți operatori or (inclusiv 0):

O = E | E + " OR " + O

Expresiile construite până acum conțin constante, variabile, toți operatorii și țin cont de precedența lor, dar omit complet parantezele. Pe baza expresiilor de tip O vom defini expresiile cu paranteze, de tip P:

P = "(" + O + ")"

Pentru a obține expresii oricât de complicate, în care expresiile de tip P sunt operanzi în expresii și mai complicate, vom extinde definiția lui X:

X = C | V | P

Gramatica asociată expresiilor

În concluzie, putem spune că problema ne cere să evaluăm expresii de tip O, definite astfel:

C = "TRUE" | "FALSE"
V = "A" | "B" | "C" | ... | "Z"
X = C | V | P
N = X | "NOT " + N
E = N | N + " AND " + E
O = E | E + " OR " + O
P = "(" + O + ")"

Implementare

Pentru fiecare tip de expresii se va implementa câte o funcție recursivă care va primi ca parametru de intrare-ieșire un pointer către șirul de caractere care conține expresia pe care trebuie să o evalueze și care se garantează că este de tipul corespunzător. Aceste funcții vor returna o valoare de tip boolean, reprezentând valoarea expresiei, în funcție de valorile variabilelor la momentul evaluării și va avansa pointerul până după sfârșitul expresiei.

Ca excepție, expresiile de tip C, V și P vor fi evaluate în aceeași funcție - cea care evaluează expresiile de tip X.

Sursa

#include <stdio.h>

const int MAX_SIR = 100;

char sir[MAX_SIR + 1];
bool variabile[26];

int N;
bool SOL;

bool evalO(char* &sir);

bool evalX(char* &sir) {
	bool answer;
	if (sir[0] == '(') { // ( O )
		++sir; // "("
		answer = evalO(sir);
		++sir; // ")"
	} else if (sir[0] == 'T' && sir[1] == 'R') {
		sir += 4; // "TRUE"
		answer = true;
	} else if (sir[0] == 'F' && sir[1] == 'A') {
		sir += 5; // "FALSE"
		answer = false;
	} else { // VARIABLE
		answer = variabile[sir[0] - 'A'];
		++sir;
	}
	return answer;
}

bool evalN(char* &sir) {
	if (sir[0] == 'N' && sir[1] == 'O') { // NOT N
		sir += 4; // "NOT "
		return !evalN(sir);
	} else { // X
		return evalX(sir);
	}
}

bool evalE(char* &sir) {
	bool answer = evalN(sir);
	if (sir[0] == ' ' && sir[1] == 'A' && sir[2] == 'N') {
		sir += 5; // " AND "
		answer &= evalE(sir);
	}
	return answer;
}

bool evalO(char* &sir) {
	bool answer = evalE(sir);
	if (sir[0] == ' ' && sir[1] == 'O' && sir[2] == 'R') {
		sir += 4; // " OR "
		answer |= evalO(sir);
	}
	return answer;
}

int main(void) {
	int i;
	char c;
	char* pozitie;

	// citirea datelor
	gets(sir);

	// calcularea solutiei
	scanf("%d\n", &N);
	for (i = 0; i < N; ++i) {
		scanf("%c", &c);
		variabile[c - 'A'] = !variabile[c - 'A'];
		pozitie = sir;
		SOL = evalO(pozitie);
		//assert(pozitie == sir + strlen(sir));

		// afisarea solutiei
		printf("%d", SOL);
	}
	printf("\n");

	return 0;
}