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
| '''
Used for judging a string whether be in the CFL (presented in CNF) using CYK algorithm
Author: Weijun-Lin
Time: 2019-4-27
Introduction:
For reading CNF you should use the format "A -> BC|a|b" (the blank space is allowed except "->")
The first character will be considered as CFL's Start Symbol
And end inputing by input "Ctrl + Z"
For testing strings, you can input as many as strings you want
And exit by using "ctrl + Z"
For Output, the output format is the .csv file whcih should be checked by Excel
The output file name can be changed in codes (the default is "result.csv")
Attention:
When you test a new string, you must closed the last .csv file
Otherwise you will meet a I/O Error because the read-write conflict
'''
class CNF:
def __init__(self, cnf: dict):
''' cnf: [str:list] '''
self.cnf = cnf
self.S = list(cnf.keys())[0]
def find_product(self, target: str):
''' find the productor '''
res = []
for key, value in self.cnf.items():
if target in value:
res.append(key)
return res
class CYK:
def __init__(self, cnf: CNF):
self.cnf = cnf
def find(self, target: str):
''' judge if the target is in the CNF '''
self.dp_mat = [[""]*len(target) for i in range(len(target))]
for i in range(len(target)):
self.dp_mat[i][i] = list(set(self.cnf.find_product(target[i])))
for length in range(2, len(target) + 1):
for i in range(len(target) - length + 1):
j = i + length - 1
temp = []
for k in range(i, j):
list1 = self.dp_mat[i][k]
list2 = self.dp_mat[k+1][j]
temp += self.find_product(list1, list2)
self.dp_mat[i][j] = list(set(temp))
if self.cnf.S in self.dp_mat[0][len(target) - 1]:
return True
return False
def find_product(self, list1: list, list2: list):
''' find all productions from Cartesian product of two lists '''
res = []
for i in range(len(list1)):
for j in range(len(list2)):
temp = self.cnf.find_product(list1[i]+list2[j])
if temp != None:
res += temp
return res
class Input:
''' my input class for reading the CNF '''
def getDictItemFromInput(self, s: str):
s = s.replace(' ', '')
temp = s.split("->")
return temp[0], temp[1].split("|")
def getInput(self):
''' return a dict CNF '''
res = {}
while True:
try:
s = input()
dict_item = self.getDictItemFromInput(s)
res[dict_item[0]] = dict_item[1]
except:
break
return res
class Visualization:
'''
make the deduction visualized
use dp_mat from class CYK to initialize
and creat .csv file to show in Excel
'''
def __init__(self, data: list):
self.data = [[""]*len(data) for i in range(len(data))]
for i in range(len(data)):
temp = data[i][i:]
for j in range(len(data) - i):
self.data[len(data) - j - 1][i] = temp[j]
def seeAsCsv(self, filename: str):
''' write data to filename as .csv '''
with open(filename, "w") as f:
for i in range(len(self.data)):
line = ""
for j in range(len(self.data[i])):
temp = ""
if type(self.data[i][j]) == str:
temp = self.data[i][j]
else:
temp = "\"X{},{}=".format(j+1,len(self.data)-i)+"{"
for k in range(len(self.data[i][j])):
temp = temp + self.data[i][j][k]
if k != len(self.data[i][j]) - 1:
temp = temp + ","
temp = temp + "}\""
line = line + temp + ","
f.write(line + "\n")
if __name__ == "__main__":
print("Please Input the CNF: (The First Character must be Start symbol until Ctrl+Z )")
myinput = Input()
data_dict = myinput.getInput()
cyk = CYK(CNF(data_dict))
print("input the string: (until Ctrl+Z)")
while True:
try:
target_str = input()
if cyk.find(target_str):
print("Yes")
else:
print("No")
visual = Visualization(cyk.dp_mat)
try:
visual.seeAsCsv("result.csv")
except:
print("Write Error: Please Close Last csv file")
except:
break
|