题目参见：清华大学出版社的《数据结构题集（C语言版）》 P148 5.1
刚开始时不知道从哪里下手，尤其是将输入的字符串序列建立成二叉树，自己想了半天越想越复杂，于是决定不浪费时间去网上直接找解题思路，发现通过构建加权字符数组的方法很不错，整体思路有了就动手实现吧，整个过程中对递归的应用很多，更加体会到了递归的美妙之处啊。。= v =。
中间比较纠结的是判别是否永真或永假，尤其是每进行一次运算会改变二叉树中原先的变元，最初没有考虑到这个结果很多都是直接跳到了结果，没有判断过程。。。
本来以为构造出二叉树之后后面的工作会简单一些，结果还是耗了很长时间。。= =||，高兴太早了麽，，，代码就堆在下面了。。
代码
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4
5 typedef struct DutyElement
6 {
7 char data;
8 int duty;
9 }DutyElement;
10
11 DutyElement DutyArray[100]; //定义加权数组
12
13 typedef struct BiTNode
14 {
15 char data;
16 struct BiTNode *lchild, *rchild;
17 }BiTNode, *BiTree;
18
19 void InitDutyArray(char *s, int n) //根据输入的序列初始化加权数组
20 {
21 int i, j;
22 for (i = 0; i < n; i++)
23 {
24 DutyArray[i].data = s[i];
25 switch (DutyArray[i].data) //分别赋权值
26 {
27 case '~':
28 DutyArray[i].duty = 3; break;
29 case '&':
30 DutyArray[i].duty = 2; break;
31 case '|':
32 DutyArray[i].duty = 1; break;
33 default:
34 DutyArray[i].duty = 0; break;
35 }
36 }
37 for (i = 0; i < n; i++)
38 {
39 if (DutyArray[i].data == '(') //是左括号的话则对运算符进行加权操作
40 {
41 for (j = i; j < n; j++)
42 {
43 if (DutyArray[j].duty != 0)
44 DutyArray[j].duty += 5;
45 }
46 }
47 else
48 {
49 if (DutyArray[i].data == ')') //右括号的话对运算符进行减权操作
50 {
51 for (j = i; j < n; j++)
52 {
53 if (DutyArray[j].duty != 0)
54 DutyArray[j].duty -= 5;
55 }
56 }
57 }
58 }
59 }
60
61 int SearchMinDutyOperator(int a, int b) //寻找权值最小的运算符，即为二叉树的根节点
62 {
63 int i, n = a, duty = 1000;
64 for (i = a; i < b + 1; i++)
65 {
66 if (DutyArray[i].duty > 0 && DutyArray[i].duty < duty)
67 {
68 n = i;
69 duty = DutyArray[i].duty;
70 }
71 }
72 return n;
73 }
74
75 int ParenthesesCloesed(int a, int b) //判断序列是否在最外层有一对括号
76 {
77 int i, n = 0;
78 for (i = a; i <= b; i++)
79 {
80 if (DutyArray[i].data == '(')
81 n++;
82 if (DutyArray[i].data == ')')
83 n--;
84 if (n == 0)
85 break;
86 }
87 if (i == b)
88 return 1;
89 else
90 return 0;
91 }
92
93 BiTree Create(int a, int b) //根据加权数组创建二叉树
94 {
95 BiTree p;
96 if (DutyArray[a].data == '(' && DutyArray[b].data == ')' && ParenthesesCloesed(a, b) == 1) //去括号
97 {
98 a += 1;
99 b -= 1;
100 }
101 if (a > b)
102 p = NULL;
103 else
104 {
105 if (a == b)
106 {
107 p = (BiTNode *)malloc(sizeof(BiTNode));
108 p->data = DutyArray[a].data;
109 p->lchild = NULL;
110 p->rchild = NULL;
111 }
112 else
113 {
114 int n;
115 n = SearchMinDutyOperator(a, b);
116 p = (BiTNode *)malloc(sizeof(BiTNode));
117 p->data = DutyArray[n].data;
118 p->lchild = Create(a, n - 1);
119 p->rchild = Create(n + 1, b);
120 }
121 }
122 return p;
123 }
124
125 void AssignValue(BiTree T, char letter, char binary) //递归为对应的字母赋二进制字符
126 {
127 if (T)
128 {
129 if (T->data == letter)
130 T->data = binary;
131 AssignValue(T->lchild, letter, binary);
132 AssignValue(T->rchild, letter, binary);
133 }
134 }
135
136 int Calculate(BiTree T) //递归计算二进制字符二叉树
137 {
138 switch (T->data)
139 {
140 case '0':
141 return 0;
142 case '1':
143 return 1;
144 case '~':
145 return !Calculate(T->rchild);
146 case '&':
147 return (Calculate(T->lchild) & Calculate(T->rchild));
148 case '|':
149 return (Calculate(T->lchild) | Calculate(T->rchild));
150 }
151 }
152
153 void main()
154 {
155 BiTree T;
156 int m = 0, n, i, j, k, length = 0, strlength, num = 1, flag;
157 char value[20] = {0};
158 char s[100] = {0};
159 char c, *str;
160 str = (char *)malloc(sizeof(char) * 20);
161 for (i = 0; i < 20; i++)
162 {
163 *(str + i) = 0;
164 }
165 c = getchar();
166 i = 0;
167 while (c != '\n')
168 {
169 if (c != ' ')
170 {
171 s[i] = c;
172 i++;
173 }
174 c = getchar();
175 }
176 for (i = 0; i < 100; i++)
177 {
178 if (s[i] == 0)
179 {
180 n = i; //n为输入序列的长度
181 break;
182 }
183 }
184 for (i = 0; i < n; i++)
185 {
186 if (strchr(s, 'A' + i) != NULL)
187 length++;
188 else
189 break;
190 }
191 length = i;
192 InitDutyArray(s, n); //初始化加权数组
193 T = Create(0, n - 1);
194 for (i = 0; i < length; i++)
195 {
196 AssignValue(T, 'A' + i, '0');
197 }
198 flag = Calculate(T);
199 for (i = 0; i < length; i++)
200 {
201 num *= 2;
202 }
203 for (i = 0; i < num; i++)
204 {
205 T = Create(0, n - 1); //由于每运算一次会将原来的二叉树中的变元改变，所以得重新构造
206 itoa(i, str, 2);
207 strlength = strlen(str);
208 for (j = 0; j < length; j++)
209 {
210 if (strlength - j - 1 >= 0)
211 value[length - j - 1] = *(str + strlength - 1 - j);
212 else
213 value[length - j - 1] = '0';
214
215 }
216 for (k = 0; k < length; k++)
217 {
218 AssignValue(T, 'A' + k, value[k]);
219 }
220 if (Calculate(T) != flag)
221 {
222 printf("Satisfactible\n");
223 break;
224 }
225 else
226 {
227 if (i == num - 1 && flag == 1)
228 {
229 printf("True forever\n");
230 return;
231 }
232 if (i == num - 1 && flag == 0)
233 {
234 printf("False forever\n");
235 return;
236 }
237 }
238 }
239 for (i = 0; i < length; i++)
240 {
241 printf("%c ", 'A' + i);
242 }
243 printf("\n");
244 c = getchar(); //输入对各字符的赋值，保存在value数组中
245 i = 0;
246 while (c != ';')
247 {
248 if (c != ',')
249 {
250 value[i] = c;
251 i++;
252 }
253 c = getchar();
254 }
255 T = Create(0, n - 1); //重新构造二叉树
256 for (i = 0; i < length; i++)
257 {
258 AssignValue(T, 'A' + i, value[i]);
259 }
260 printf("The result is %d\n", Calculate(T));
261 }