本篇继承上篇，主要是把代码贴出来。
可视化的方式是将语法树按照dot格式写入dot文件，然后通过graphviz工具包转换为png。关于graphviz可以直接去官网下载。三个平台的版本都有。
代码如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340#include <iostream>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <sstream>
#include <stack>
#include <fstream>
using namespace std;
const int num1 = 1;
const int num2 = 2;
const int num3 = 1;
const int num_atom = 3;
char op1[num1] = {'-'}; //低级运算符蕴含
char op2[num2] = {'|','&'}; //中级运算符析取合取
char op3[num3] = {'^'}; //高级运算符否定
char atoms[num_atom] = {'q','p','r'}; //原子
struct Node{
int id;
int child_num;
string val;
int left_child;
int right_child;
};
vector<Node> nodes;
int now_id = 0;
int my_stoi(string str){
if(str == ""){
return -1;
}
int ans = 0;
int n = str.length();
for(int i=0;i<n;i++){
ans = ans*10 + (str[i]-'0');
}
return ans;
}
string my_itos(int num){
stringstream stream;
stream << num;
return stream.str();
}
/*
*
* 将逻辑符号转换为已读的
*/
string formatValue(string value){
if(value == "->"){
value="→";
}
if(value == "&"){
value="∧";
}
if(value == "|"){
value="∨";
}
if(value == "^"){
value="￢";
}
return value;
}
/*
*
* 生成一个节点，并将节点的id以字符串的形式返回
*/
string genNode(string value,string left,string right,int childnum){
// cout<<"gen node "<<value<<endl;
value = formatValue(value);
Node node;
node.child_num = childnum;
node.val = value;
node.left_child = my_stoi(left);
node.right_child = my_stoi(right);
node.id = now_id;
nodes.push_back(node);
now_id++;
return my_itos(now_id-1);
}
bool isOP3orAtom(char c){
for(int i=0;i<num3;i++){
if(c == op3[i])
return 1;
}
for(int i=0;i<num_atom;i++){
if(c == atoms[i]){
return 1;
}
}
return 0;
}
/*
* 判断是否为否定运算符
*/
bool isOP3(char c){
for(int i=0;i<num3;i++){
if(c == op3[i])
return 1;
}
return 0;
}
/*
* 判断是否为原子符号
*/
bool isAtom(char c){
for(int i=0;i<num_atom;i++){
if(c == atoms[i]){
return 1;
}
}
return 0;
}
/*
* 消去否定符，有否定符（op3）的话向下生成一个叶子节点，
* 没有否定符则生成当前生成一个叶子节点
* 默认原子词符号（atoms）
* 返回值，该节点id
*/
string elimination_non(string formula){
if(isOP3(formula[0])){
string tmp = "";
tmp = formula[0];
return genNode(tmp,elimination_non(formula.substr(1,formula.length())),"",1);
} else if(isAtom(formula[0])){
return genNode(formula,"","",0);
}else{
return formula;
}
}
/*
* 判断是否为析取或合取
*/
bool isOP2(char c){
for(int i=0;i<num2;i++){
if(c == op2[i])
return 1;
}
return 0;
}
/*
* 消去逻辑运算符号，在无括号，无蕴含符号的子式中，
* 消去所有的析取、合取符号（op2中的符号），
* 并将符号两侧的子式送到下一个函数处理
* 返回值，该子式的根节点id
*/
string elimination_symbol(string formula){
int n = formula.length();
stack<string> s;
int i=0;
while(i < n){
if(isOP2(formula[i])){
string value = "";
value += formula[i];
string sub1 = "";
while(!s.empty()){
sub1 = s.top()+sub1;
s.pop();
}
string sub2 = "";
for(i=i+1;i<n;i++){
if(isOP2(formula[i])){
i--;
break;
}
sub2 += formula[i];
}
string subid = genNode(value,elimination_non(sub1),elimination_non(sub2),2);
s.push(subid);
}else{
string tmp = "";
tmp += formula[i];
s.push(tmp);
}
i++;
}
string new_formula = "";
while(!s.empty()){
new_formula = s.top()+new_formula;
s.pop();
}
return elimination_non(new_formula);
}
bool isOP1(char c){
for(int i=0;i<num1;i++){
if(c == op1[i])
return 1;
}
return 0;
}
/*
* 消去蕴含，在无括号的子公式中消去所有的蕴含符号（op1中的符号），
* 并将蕴含两侧的子式送到下一个函数中处理
* 返回值，该子式的根节点id
*/
string elimination_implication(string formula){
int n = formula.length();
stack<string> s;
int i=0;
while(i < n){
if(isOP1(formula[i]) || (formula[i] == '-' && formula[i+1] == '>')){
string sub1 = "";
while(!s.empty()){
sub1 = s.top()+sub1;
s.pop();
}
string sub2 = "";
for(i=i+1;i<n;i++){
if(isOP1(formula[i]) || (formula[i] == '-' && formula[i+1] == '>')){
i--;
break;
}
if(formula[i] == '>'){
continue;
}
sub2 += formula[i];
}
string subid = genNode("->",elimination_symbol(sub1),elimination_symbol(sub2),2);
s.push(subid);
}else{
string tmp = "";
tmp += formula[i];
s.push(tmp);
}
i++;
}
string new_formula = "";
while(!s.empty()){
new_formula = s.top()+new_formula;
s.pop();
}
return elimination_symbol(new_formula);
}
/*
* 消去括号，在原始式中消去所有的括号，
* 并将括号中的子式送到下个函数中处理
* 返回值，根节点的id
*/
string elimination_brackets(string formula){
int n = formula.length();
stack<string> s;
int i = 0;
while(i < n){
if(formula[i] == ')'){
string subformula = "";
while(1){
string s_top = s.top();
s.pop();
if(s_top == "("){
break;
}else{
subformula = s_top+subformula;
}
}
string subid = elimination_implication(subformula);
s.push(subid);
}else if(formula[i] != ' '){
string tmp = "";
tmp += formula[i];
s.push(tmp);
}
i++;
}
string new_formula = "";
while(!s.empty()){
new_formula = s.top()+new_formula;
s.pop();
}
return elimination_implication(new_formula);
}
/*
* 格式化原始式，将一些符号进行替换
*/
string formats(string str){
string tmp = "";
while(str.find("→") != -1){
tmp = "→";
str.replace(str.find("→"),tmp.length(),"->");
}
while(str.find("∧") != -1){
str.replace(str.find("∧"),tmp.length(),"&");
}
while(str.find("∨") != -1){
str.replace(str.find("∨"),tmp.length(),"|");
}
while(str.find("￢") != -1){
str.replace(str.find("￢"),tmp.length(),"^");
} return str;
}
/*
* 将结果写入 dot 文件，并且通过dot 命令生成 png图片
*/
void writeToDot(){
cout<<"write to dot"<<endl;
ofstream fout("a.dot");
fout<<"digraph G{"<<endl;
for(int i=0;i<now_id;i++){
Node node = nodes[i];
cout<<node.id<<"\t"<<node.val<<"\t"<<node.left_child<<"\t"<<node.right_child<<endl;
if(node.child_num == 2){
fout<<node.id<<"[label=\""<<node.val<<"\"];"<<endl;
fout<<node.id<<"->"<<node.left_child<<";"<<endl;
fout<<node.id<<"->"<<node.right_child<<";"<<endl;
}
if(node.child_num == 1){
fout<<node.id<<"[label=\""<<node.val<<"\"];"<<endl;
fout<<node.id<<"->"<<node.left_child<<";"<<endl;
}
if(node.child_num == 0){
fout<<node.id<<"[label=\""<<node.val<<"\"];"<<endl;
}
}
fout<<"}";
fout.close();
system("dot a.dot -Tpng -o image.png");
}
int main(int argc, char** argv) {
string formula;
// cin>>formula;
formula = "(((^p)∧q) → (p∧(q∨(￢r))))";
formula = formats(formula);
cout<<formula<<endl;
elimination_brackets(formula);
writeToDot();
for(int i=0;i<now_id;i++){
Node node = nodes[i];
cout<<node.id<<"\t"<<node.val<<"\t"<<node.left_child<<"\t"<<node.right_child<<endl;
}
return 0;
}
生成的a.dot代码如下：1
digraph G{
0[label="p"];
1[label="￢"];
1->0;
2[label="q"];
3[label="∧"];
3->1;
3->2;
4[label="r"];
5[label="￢"];
5->4;
6[label="q"];
7[label="∨"];
7->6;
7->5;
8[label="p"];
9[label="∧"];
9->8;
9->7;
10[label="→"];
10->3;
10->9;
}
生成的图像如下: