A Boolean expression is represented as a binary tree of strings (BT) in which internal nodes contain the logical connectors $$\texttt{AND}$$, $$\texttt{OR}$$ and $$\texttt{NOT}$$, and leaves contain strings representing Boolean variables.

Ex: the expression $$a_1$$ $$\texttt{AND}$$ $$\texttt{NOT}$$ ($$bool_2$$ $$\texttt{OR}$$ $$bx_{30}$$) is represented by the following BT:

An interpretation of an expression is represented by a set of pairs $$\texttt{<variable, value>}$$ that associates to each variable of the expression a Boolean value.

Ex: the set ($$\texttt{<a1,1>,<bool2,0>,<bx30,1>}$$) associate the value 1 ($$\texttt{True}$$) to the Boolean variables $$a_1$$ and $$bx_{30}$$ and the value 0 ($$\texttt{False}$$) to $$bool_2$$.

• Assume that we use BT dynamic implementation; give the declaration of the types Interpretation and Expression.
• Write a function that returns the Boolean value of a variable in an interpretation if it exists.
• Write a function $$\texttt{int Evaluate(Interpretation I, Expression E, int *Value)}$$ that computes the value of the expression E according to the interpretation I.
• Now, we want to test whether a given expression is valid (true for all interpretations). Assume the existence of an array containing all interpretations of a given expression (all possible variables combinations), write a function
  $$\texttt{int Valid(Interpretation arrayInter[], int NBInter, Expression E)}$$
  that checks the validity of the expression.

1.
#include <string.h>
typedef struct  {
	char var[10];
	int val;
} Couple;

typedef struct node{ 
	char value[10]; 
	struct node *left, *right; 
}  *Expression;

typedef struct {
	Couple arr[100];
	int size;
} Interpretation;

2.
int find_val(Interpretation In, char v[],int *value)
{
	int i;
	for (i=0;i<In.size;i++)
		if (!strcmp(In.arr[i].var,v))
		{
			*value = In.arr[i].val;
			return 1;
		}
	return 0;
}

3.
int Evaluate(Interpretation In, Expression E, int *Value) 
{
	int vl,vr,bl,br;
	if (E == NULL) return 0;
	if (E->left == NULL && E->right == NULL) 
		return find_val(In, E->value,Value);
	bl = Evaluate(In,E->left,&vl);
	br = Evaluate(In,E->right,&vr);
	if (!strcmp(E->value,"NOT"))
	{
		if (bl != 0 || br == 0) return 0;
		*Value = 1-vr;
		return 1;
	}
	if (bl == 0 || br == 0) return 0;
	if (!strcmp(E->value,"AND"))
		*Value = vl && vr;
	else
		*Value = vl || vr;
	return 1;
}

4.
int Valid(Interpretation arrayInter[], int NBInter, Expression E)
{
	int i,v;
	for (i = 0; i<NBInter;i++)
	{
		if(!Evaluate(arrayInter[i],E,&v))
			return -1;
		if (!v) 
			return 0;
	}
	return 1;
}