'''
核心思想是先给出一个初始状态q0，从原始的nfa表格中计算第一行转换的内容，以此计算a,b,...
在计算的过程中，会有新的状态出现，将新的状态加入state中，按照顺序计算state中第二个状态可以到达的
位置，在这个过程中，循环不能停止，应该手动设立结束循环的标志。标志是如果在state中计算到了最后一个状态
证明不能再往下循环，循环结束。

这里需要做说明，就算计算到最后一个状态，如果在最后一个状态中出现了新的状态，在此处停止循环就是错误的
但是算法的逻辑是先计算新的状态并将其加入state，如果在最后一个状态中出现了新的状态，在判断循环是否应该结束
之前，新的状态就会被加入state，所以上述假设不成立，算法依然正确。

在计算的具体步骤中，要考虑一个状态由几个q组成，如果是多个，就要把这些q单独取出来比较，获得一个状态中所有q的
转移状态作为此状态生成的新状态，中间用空格隔开，方便spilt。


'''
import os
import xlwt

#在计算过程中去掉重复状态
def temp_in_state(temp,state):
    for i in range(len(state)):
        if sorted(temp) == sorted(state[i]):
            return False
    return True


dfa_table = []#储存最终结果的数组
state = []#存放所有的状态,是table的第一列
#定义的nfc转移表,用编号表示q几，如果能到达，在其中填写到达所需要的字母
#可以从文件中读取
file = open("nfa.txt")
nfa_table = []#储存nfa数组
line = file.readline()
#在指定txt文件中按行读取，制作二维数组
while line:
    line = line.replace('\n', '')
    line = line.split('*')
    nfa_table.append(line)
    line = file.readline()
#sign = ['a','b']#输入，不一定只有两个
sign = input("输入转换条件字符").split(' ')#输入条件转移数组，用空格隔开
#制作state表头
input_num = len(sign)#转移字符的个数，可输入
state.append("0 ")
cnt = 0
while 1:#到达循环结束条件的时候退出
    flag = 0#flag=0，说明当前输入为a，flag = 1，说明当前输入为b以此类推
    for j in range(len(sign)):#遍历所有可能的输入
        length = len(state[cnt].split(' ')) - 1
        temp = ""#临时数组，存储新的状态
        for i in range(len(state[cnt].split(' ')) - 1):  # 遍历新的状态中的所有情况
            for k in range(len(nfa_table[0])):#在原始表中查询
                location = int(state[cnt].split(" ")[i])
                if sign[j] in nfa_table[location][k]:
                    if str(k) not in temp:
                        temp = temp + str(k) + " "
        a = state[cnt] + ',' + temp + ',' + sign[j]#规定输入，最后可以通过查找逗号分开
        if(a not in dfa_table):
            dfa_table.append(state[cnt] + ',' + temp + ',' + sign[j])
        if (temp_in_state(temp,state) and temp != ""):  # 出现新的状态，加入
            state.append(temp)
        else:
            flag += 1
    cnt += 1
    if (cnt == len(state) and flag == len(sign)):#当cnt到了状态数组的最后一行，并且flag已经计算过输入的最后一种情况，退出循环
        break
for i in range(len(dfa_table)):
    print(dfa_table[i])
print("格式化的内容储存在同目录下的excel文件‘dfa’中")
workbook = xlwt.Workbook()
sheet = workbook.add_sheet('test')
sheet.write(0,0,"始态")
sheet.write(0,1,"终态")
sheet.write(0,2,"转移条件")
for i in range(len(dfa_table)):
    dfa_table[i] = dfa_table[i].replace(" ","").split(",")
    for j in range(len(dfa_table[i])):
        sheet.write(i + 1,j,dfa_table[i][j])
workbook.save('dfa.xlsx')
print("表格写入成功")

os.system("pause")