Tables de vérité

Soyez le premier à donner votre avis sur cette source.

Vue 6 045 fois - Téléchargée 255 fois

Description

Il s'agit d'un prog qui interpete des expressions logiques (dans un format proche de l'algebre de Boole) et qui en donne la table de vérité.
En fait, sans trop le savoir, j'ai utilisé des arbres binaires

Source / Exemple :


#include <stdio.h>
#include <string.h>
#define True 1
#define False 0
#define MAX 9

typedef int BOOL;

unsigned long two_power(int);
void truth_table(int);
int parenthesage(char*, int);
void eat_spaces(char*);
int eat_parentheses(char*, int);
int interpret_expression(char*, int, int);

unsigned long two_power(int puiss)
{
  int i;
  unsigned long res;
  for(i = 0, res = 1; i < puiss; i++) res *= 2;
  return res;
}

FILE* resultat;
int current_indice = 0;
int nb_exp;
int result[MAX] = {0};
int nb_used;
BOOL Logic_Variables[26][2] = {0};  //1ere dim : valeur, 2e dim: si used
int enculeur_de_maman[26] = {0};

struct Operation
{
  BOOL (*op) (BOOL, BOOL);
  int rg_arg1, rg_arg2;
} expression[MAX][1000];

//fonctions  logiques
int f(int a, int rg)
{
  if (a > 0) return expression[rg][a].op( f(expression[rg][a].rg_arg1, rg), f(expression[rg][a].rg_arg2, rg));
  else if (a <= 0) return (-a);
}

BOOL give_result(int num_exp, int rien)
{
  if (result[num_exp] == -1) result[num_exp] = expression[num_exp][0].op(f(expression[num_exp][0].rg_arg1, num_exp), f(expression[num_exp][0].rg_arg2, num_exp));
  return result[num_exp]; }

BOOL get_var(BOOL indice, BOOL a)
{
  return (Logic_Variables[indice][0]);
}

BOOL not(BOOL p, BOOL a)    { return (!p); }
BOOL and(BOOL p, BOOL q)    { return (p && q); }
BOOL or(BOOL p, BOOL q)     { return (p || q); }
BOOL impli(BOOL p, BOOL q)  { return (!p || q); }
BOOL equi(BOOL p, BOOL q)   { return (p == q); }
BOOL xor(BOOL p, BOOL q)    { return ((p && !q) || (!p && q)); }

//fonctions de traitement de la chaine
void eat_spaces(char* chaine)
{
  int i;
  for (i = 0; i < strlen(chaine); i++) //strlen réévaluée à chaque itération
    if (chaine[i] == ' ') strcpy(&chaine[i], &chaine[i+1]);
  //fprintf(error, "espaces vires\n");
}

int eat_parentheses(char* chaine, int size)
{
  int i, a, b;
  //fprintf(error, "déparenthèsage de ");
  //for(i = 0; i < size; i++) putc(chaine[i], error);
  //fprintf(error, " -> ");
  while (chaine[0] == '(' && chaine[size-1] == ')' && parenthesage(&chaine[1], size-2) == 0)
    {
      chaine[size-1] = '\0';
      strcpy(chaine, &chaine[1]);
      size -= 2;
    }
  //for(i = 0; i < size; i++) putc(chaine[i], error); fprintf(error, "(%d)\n", size);
  return size;
}

int parenthesage(char* commande, int size)
{
  int i, par;
  for (i = 0, par = 0; i < size; i++)
    {
      if (commande[i] == '(') par++;
      else if (commande[i] == ')') par--;
      if (par < 0) return i+1;
    }
  if (par != 0) return strlen(commande)+1;
  else return 0;
}

int main()
{
  char input[2000];
  char commande[2000];
  int a, b, i, j;
  nb_used = 0;
  //error = fopen("debug.info", "w");
  resultat = fopen("result.txt", "wr");
  
  do
    {
      printf("Nombre d'expressions a interpreter (1 - 9): ");
      scanf("%d", &nb_exp);
    }
  while (nb_exp < 1 || nb_exp > 9);
  gets(commande); //vide le buffer

  for (i = 0; i < nb_exp; i++)
    {
      //current_indice = 0;
      do
	{
	  printf("[%d]:  ", i+1);
	  current_indice = 0;
	  gets(input);
	  strcpy(commande, input);
	  eat_spaces(commande);
	  a = parenthesage(commande, strlen(commande));
	  b = interpret_expression(commande, i, strlen(commande));
	  if (a != 0) printf("Erreur de parenthesage (car %d)\n", a);
	  if (b == 0) printf("Probleme de syntaxe\n");
	}
      while (a != 0 || b == 0);
      fprintf(resultat, "[%d]:  %s\n", i+1, input);
      /*current_indice = 0;
	interpret_expression(commande, i, strlen(commande));*/
    }
  for (i = 0, j = 0; i < 26; i++)
    if (Logic_Variables[i][1])
      {
	enculeur_de_maman[j] = i;
	j++;
      }
  truth_table(0);
  printf("\n\nEntre n'importe quoi pour quitter ");
  scanf(" %s", commande);
  return 0;
}

void truth_table(int operation)  //operation: rg de l'op à lancer ds exp
{
  int i;
  unsigned long max_to_go, j;
  for (i = 0; i < nb_used; i++)
    {
      printf("%c ", 'a' + enculeur_de_maman[i]);
      fprintf(resultat, "%c ", 'a' + enculeur_de_maman[i]);
    }
  for (i = 0; i < nb_exp; i++)
    {
      printf(" [%d]", i+1);
      fprintf(resultat, " [%d]", i+1);
    }
  printf("\n");
  fprintf(resultat, "\n");
  max_to_go = two_power(nb_used);
  for (j = 0; j < max_to_go; j++)
    {
      for (i = 0; i < nb_used; i++)
	{
	  Logic_Variables[enculeur_de_maman[i]][0] = (j >> (nb_used - 1 - i)) % 2;
	  printf("%d ", Logic_Variables[enculeur_de_maman[i]][0]);
	  fprintf(resultat, "%d ", Logic_Variables[enculeur_de_maman[i]][0]);
	}
      for (i = 0; i < nb_exp; i++ )
	{
	  result[i] = expression[i][operation].op(f(expression[i][operation].rg_arg1, i), f(expression[i][operation].rg_arg2, i));
	  printf("  %d ", result[i]);
	  fprintf(resultat, "  %d ", result[i]);
	}
      printf("\n");
      fprintf(resultat, "\n");
    }
}

int interpret_expression(char* chaine, int num_exp, int size)
{
  int indice, i, par = 0, i_arg2, sz_arg1 = 0, j, a, b;

  indice = current_indice;
  //fprintf(error, "indice de ce qui vien: %d\n", current_indice);
  current_indice++;
  size = eat_parentheses(chaine, size); 

    
  if (size == 3 && chaine[0] == '[' && chaine[2] == ']' && chaine[1] <= '9' && chaine[1] >= '1')
    {
      expression[num_exp][indice].op = give_result;
      expression[num_exp][indice].rg_arg1 = -(chaine[1] - '1');
      expression[num_exp][indice].rg_arg2 = 0;
      if (chaine[1] - '1' >= num_exp)
	{
	  printf("Expression %d inexistante\n", chaine[1] - '0');
	  return 0;
	}
      else return 1;
    }

  if (size == 1 && chaine[0] >= 'a' && chaine[0] <= 'z') 
    {
      expression[num_exp][indice].op = get_var;
      expression[num_exp][indice].rg_arg1 = -(chaine[0] - 'a');
      expression[num_exp][indice].rg_arg2 = 0;
      if ( Logic_Variables[chaine[0]-'a'][1] == 0 )
	{
	  nb_used++;
	  Logic_Variables[chaine[0]-'a'][1] = 1;
	}
      //for(j = 0; j < profondeur; j++) fputc(' ', error);
      //fputc(chaine[0], error); putc('\n', error);
      return 1;
    }

  if (chaine[0] == '-')
    {
      expression[num_exp][indice].op = not;
      expression[num_exp][indice].rg_arg1 = current_indice;
      //for(j = 0; j < profondeur; j++) fputc(' ', error);
      //putc('-', error); putc('\n', error);
      a = interpret_expression(&chaine[1], num_exp, size - 1);
      expression[num_exp][indice].rg_arg2 = 0;
      return a;
    }

  for (i = 0, par = 0; i < size; i++)
    {
      if (chaine[i] == '(' ) par++;
      else if (chaine[i] == ')' ) par--;
      else if (par == 0)
	{
	  if (chaine[i] == '.')
	    {
	      expression[num_exp][indice].op = and;
	      sz_arg1 = i;
	      i_arg2 = i + 1;
	      //for(j = 0; j < profondeur; j++) fputc(' ', error);
	      //fprintf(error, "and %d %d\n", sz_arg1, i_arg2);
	      break;
	    }
	  else if (chaine[i] == '+')
	    {
	      expression[num_exp][indice].op = or;
	      sz_arg1 = i;
	      i_arg2 = i + 1;
	      //for(j = 0; j < profondeur; j++) fputc(' ', error);
	      //fprintf(error, "or %d %d\n", sz_arg1, i_arg2);
	      break;
	    }
	  else if (chaine[i] == '=' && chaine[i+1] == '>')
	    {
	      expression[num_exp][indice].op = impli;
	      sz_arg1 = i;
	      i_arg2 = i + 2;
	      //for(j = 0; j < profondeur; j++) fputc(' ', error);
	      //fprintf(error, "=> %d %d\n", sz_arg1, i_arg2);
	      break;
	    }
	  else if (chaine[i] == '<' && chaine[i+1] == '=' && chaine[i+2] == '>')
	    {
	      expression[num_exp][indice].op = equi;
	      sz_arg1 = i;
	      i_arg2 = i + 3;
	      //for(j = 0; j < profondeur; j++) fputc(' ', error);
	      //fprintf(error, "<=> %d %d\n", sz_arg1, i_arg2);
	      break;
	    }
	  else if (chaine[i] == 'X' && chaine[i+1] == 'O' && chaine[i+2] == 'R')
	    {
	      expression[num_exp][indice].op = xor;
	      sz_arg1 = i;
	      i_arg2 = i+3;
	      //for(j = 0; j < profondeur; j++) fputc(' ', error);
	      //fprintf(error, "xor %d %d\n", sz_arg1, i_arg2);
	      break;
	    }
	}
    }

  if (sz_arg1 == 0) return 0;  //sz_arg1 necessairement modifie si operateur reconnu, sinon reste a 0
  
  a = expression[num_exp][indice].rg_arg1 = current_indice;
  interpret_expression(chaine, num_exp, sz_arg1);
  b = expression[num_exp][indice].rg_arg2 = current_indice;
  interpret_expression(&chaine[i_arg2], num_exp, size - i_arg2);
  return (a && b);
}

Conclusion :


Table de verite v 0.9 (bool edition)
-------------------------------------

Il s'agit d'un prog qui interpete des expressions logiques (dans un format proche de l'algebre de Boole) et qui en donne la table de vérité.
Les opérateurs utilisés sont
-et: "."
-ou: "+"
-ou exclusif: "XOR"
-implication: "=>"
-equivalence: "<=>"
Si aucun parenthesage n'est présent, les opérations sont effectuees de gauche a droite.

Les variables logiques sont aux nombres de 26: les lettres non accentuees en minuscules uniquement
Pour rappeler (composition) une expression précédent, on met [num de l'expression] comme s'il s'agissait d'une variable.
Une copie de la sortie est mise dans le fichier resultat.txt, qui peut alors etre imprimé au besoin.
On espace comme on veut les expressions, de toutes facons, tous les espaces sont supprimés.

Voilà un exemple:

[1]: a.b
[2]: aXORk
[3]: [1]+[2]
[4]: [3].k
a b k [1] [2] [3] [4]
0 0 0 0 0 0 0
0 0 1 0 1 1 1
0 1 0 0 0 0 0
0 1 1 0 1 1 1
1 0 0 0 1 1 0
1 0 1 0 0 0 0
1 1 0 1 1 1 0
1 1 1 1 0 1 1

Si une expression n'est pas correcte, ca plante, mais aucun autre dommage que l'arret du prog n'est causé au PC.

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

Cyberboy2054
Messages postés
173
Date d'inscription
jeudi 20 décembre 2001
Statut
Membre
Dernière intervention
22 août 2008

Trop bien :)
juste un truc, ta fonction two_power est lente, tu peux l optimiser un poil :
unsigned long two_power(int p)
{
return (2 << p);
}

et cela fait, il me semble, la meme chose ( renvoi de 2 puissance p), mais avec une boucle for en moins ...
cs_Kirua
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008

vala, j'ai juste tappé "gcc logic_benoit.c" ds la console et ça m'a fait a.exe qui marche impec, merci ;-)
mickaeliazerty
Messages postés
10
Date d'inscription
samedi 5 juin 2004
Statut
Membre
Dernière intervention
27 juillet 2004

je ne connaissais pas l'opérateur ^ qui est donc un xor, si j'ai bie compris.
pour la compilation, j'utilise le gcc de Dev-Cpp 4.9.8.5 de la manière suivante

(dans C:\autoexec.bat)
PATH c:\path

(dans c:\path\gcc.bat que j'ai créé)
@Echo Off
C:\Dev-Cpp\bin\gcc.exe %1 -o %2

puis pour compiler cette source je lance depuis la console
[source_dir]:\>gcc logic_Benoit.c test.exe

et là, pas de soucis, ca compile et me sort mon test.exe
cs_Kirua
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008

BOOL xor(BOOL p, BOOL q) { return ((p && !q) || (!p && q)); }

tu peux faire ça plutôt:

return p^q
cs_Kirua
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008

C:\Program Files\Dev C++\Projects>g++ logic_Benoit.c -o logic_Benoit.exe -I"C:/Program Files/Dev C++/include/c++" -I"C:/Program Files/Dev C++/include/c++/mingw
32" -s
logic_Benoit.c:62: parse error before `!' token
logic_Benoit.c:67: parse error before `^' token
logic_Benoit.c: In function `int interpret_expression(char*, int, int)':
logic_Benoit.c:241: parse error before `;' token
logic_Benoit.c:259: parse error before `;' token
logic_Benoit.c:268: parse error before `||' token
logic_Benoit.c:295: parse error before `^' token

pq? :(
Afficher les 7 commentaires

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.