关于重言式判别的问题，我找来了一个现成的程序，可是读不懂，主要是二叉树怎么实现
#include <stdio.h>#include <stdlib.h>
#include <string.h>
typedef struct DutyElement
{
char data;
int duty;
}DutyElement;
DutyElement DutyArray[100]; //定义加权数组
typedef struct BiTNode
{
char data;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
void InitDutyArray(char *s, int n) //根据输入的序列初始化加权数组
{
int i, j;
for (i = 0; i < n; i++)
{
DutyArray[i].data = s[i];
switch (DutyArray[i].data) //分别赋权值
{
case '~':
DutyArray[i].duty = 3; break;
case '&':
DutyArray[i].duty = 2; break;
case '|':
DutyArray[i].duty = 1; break;
default:
DutyArray[i].duty = 0; break;
}
}
for (i = 0; i < n; i++)
{
if (DutyArray[i].data == '(') //是左括号的话则对运算符进行加权操作
{
for (j = i; j < n; j++)
{
if (DutyArray[j].duty != 0)
DutyArray[j].duty += 5;
}
}
else
{
if (DutyArray[i].data == ')') //右括号的话对运算符进行减权操作
{
for (j = i; j < n; j++)
{
if (DutyArray[j].duty != 0)
DutyArray[j].duty -= 5;
}
}
}
}
}
int SearchMinDutyOperator(int a, int b) //寻找权值最小的运算符，即为二叉树的根节点
{
int i, n = a, duty = 1000;
for (i = a; i < b + 1; i++)
{
if (DutyArray[i].duty > 0 && DutyArray[i].duty < duty)
{
n = i;
duty = DutyArray[i].duty;
}
}
return n;
}
int ParenthesesCloesed(int a, int b) //判断序列是否在最外层有一对括号
{
int i, n = 0;
for (i = a; i <= b; i++)
{
if (DutyArray[i].data == '(')
n++;
if (DutyArray[i].data == ')')
n--;
if (n == 0)
break;
}
if (i == b)
return 1;
else
return 0;
}
BiTree Create(int a, int b) //根据加权数组创建二叉树
{
BiTree p;
if (DutyArray[a].data == '(' && DutyArray[b].data == ')' && ParenthesesCloesed(a, b) == 1) //去括号
{
a += 1;
b -= 1;
}
if (a > b)
p = NULL;
else
{
if (a == b)
{
p = (BiTNode *)malloc(sizeof(BiTNode));
p->data = DutyArray[a].data;
p->lchild = NULL;
p->rchild = NULL;
}
else
{
int n;
n = SearchMinDutyOperator(a, b);
p = (BiTNode *)malloc(sizeof(BiTNode));
p->data = DutyArray[n].data;
p->lchild = Create(a, n - 1);
p->rchild = Create(n + 1, b);
}
}
return p;
}
void AssignValue(BiTree T, char letter, char binary) //递归为对应的字母赋二进制字符
{
if (T)
{
if (T->data == letter)
T->data = binary;
AssignValue(T->lchild, letter, binary);
AssignValue(T->rchild, letter, binary);
}
}
int Calculate(BiTree T) //递归计算二进制字符二叉树
{
switch (T->data)
{
case '0':
return 0;
case '1':
return 1;
case '~':
return !Calculate(T->rchild);
case '&':
return (Calculate(T->lchild) & Calculate(T->rchild));
case '|':
return (Calculate(T->lchild) | Calculate(T->rchild));
}
}
int main()
{
BiTree T;
int m = 0, n, i, j, k, length = 0, strlength, num = 1, flag;
char value[20] = {0};
char s[100] = {0};
char c, *str;
str = (char *)malloc(sizeof(char) * 20);
for (i = 0; i < 20; i++)
{
*(str + i) = 0;
}
c = getchar();
i = 0;
while (c != '\n')
{
if (c != ' ')
{
s[i] = c;
i++;
}
c = getchar();
}
for (i = 0; i < 100; i++)
{
if (s[i] == 0)
{
n = i; //n为输入序列的长度
break;
}
}
for (i = 0; i < n; i++)
{
if (strchr(s, 'A' + i) != NULL)
length++;
else
break;
}
length = i;
InitDutyArray(s, n); //初始化加权数组
T = Create(0, n - 1);
for (i = 0; i < length; i++)
{
AssignValue(T, 'A' + i, '0');
}
flag = Calculate(T);
for (i = 0; i < length; i++)
{
num *= 2;
}
for (i = 0; i < num; i++)
{
T = Create(0, n - 1); //由于每运算一次会将原来的二叉树中的变元改变，所以得重新构造
itoa(i, str, 2);
strlength = strlen(str);
for (j = 0; j < length; j++)
{
if (strlength - j - 1 >= 0)
value[length - j - 1] = *(str + strlength - 1 - j);
else
value[length - j - 1] = '0';
}
for (k = 0; k < length; k++)
{
AssignValue(T, 'A' + k, value[k]);
}
if (Calculate(T) != flag)
{
printf("Satisfactible\n");
break;
}
else
{
if (i == num - 1 && flag == 1)
{
printf("True forever\n");
return 0;
}
if (i == num - 1 && flag == 0)
{
printf("False forever\n");
return 1;
}
}
}
for (i = 0; i < length; i++)
{
printf("%c ", 'A' + i);
}
printf("\n");
c = getchar(); //输入对各字符的赋值，保存在value数组中
i = 0;
while (c != ';')
{
if (c != ',')
{
value[i] = c;
i++;
}
c = getchar();
}
T = Create(0, n - 1); //重新构造二叉树
for (i = 0; i < length; i++)
{
AssignValue(T, 'A' + i, value[i]);
}
printf("The result is %d\n", Calculate(T));
return 0;
}
