III Международная студенческая научная конференция Студенческий научный форум - 2011
ПРИМЕР ПРОГРАММИРОВАНИЕ КОНЕЧНОГО АВТОМАТА ДЛЯ ПОИСКА И ПРЕОБРАЗОВАНИЯ ДАТ НА ЯЗЫКЕ PYTHON 2.7
КомментарииПолная версия работы доступна во вкладке "Файлы работы" в формате PDF
Рассмотрим применение конечных автоматов на примере такой задачи как поиск даты в разном формате в текстовом файле и перевод её в формат dd.mm.yyyy, реализованной на языке Python 2.7.
В файле может содержаться дата в разном формате:
1) dd.MM.yy
2) dd-MM-yy
3) dd/MM/yy
4) dd-MM-yyyy
5) dd.MM.yyyy
6) dd/MM/yyyy
7) yyyy -MM-dd
8) yyyy .MM.dd
9) yyyy /MM/dd
10) yy -MM-dd
11) yy .MM.dd
12) yy/MM/dd
Дата в представленных выше форматах заменяется в формате dd.MM.yyyy.
Определим возможные состояния, в которых может находиться автомат, для простоты, состояния названы так, что показывают на какому формату они подходят в данном состоянии, например состояние XX. - это значит последовательно было найдено 2 числа и один из символов использующихся в указании даты: ‘.´, ´-´ ,´/´.
Состояния:
State = Enum
(´start´, #базовое состояние входящий текст
´X´, #состояние когда встретилась одна цифра
´XX´, #состояние когда встретилось две цифры
´X.´, #состояние когда встретилась одна цифра и разделитель
´X.X´, #состояние когда встретилась одна цифра, разделитель и снова цифра
´X.X.´,
´X.X.X´,
´XXX´,
´XXXX´,
´XXXX.´,
´XXXX.X´,
´XXXX.XX´,
´XXXX.XX.´,
´XXXX.XX.X´,
´XXXX.XX.XX´, #состояние когда встретилась дата вида : 1998.1.2,1998-1-2 или 1998/1/2
´X.X.XX´,
´X.X.XXX´,
´X.X.XXXX´, #состояние когда встретилась дата вида : 2.1.1998,2-1-1998 или 2/1/1998
´XX.´,
´XX.X´,
´XX.XX´,
´XX.XX.´,
´XX.XX.X´,
´XX.XX.XX´, #состояние когда встретилась дата вида : 12.11.98, 12-11-98 или 12/11/98
´XX.XX.XXX´,
´XX.XX.XXXX´) #состояние когда встретилась дата вида : 12.11.2010, 12-11-2010 или 12/11/2010
Граф переходов состояний в автомате показан на рисунке:
Из состояния ´start´ автомат может перейти:
- в состояние ´X´
- остаться в состоянии ´start´
Из состояния ´X´ автомат может перейти:
- в состояние ´XX´
- в состояние ´X.´
- в состоянии ´start´
Из состояния ´XX´ автомат может перейти:
- в состояние ´XX.´
- в состояние ´XXX´
- в состоянии ´start´
Из состояния ´X.´ автомат может перейти:
- в состояние ´X.X´
- в состоянии ´start´
Из состояния ´X.X´ автомат может перейти:
- в состояние ´X.X.´
- в состоянии ´start´
Из состояния ´X.X.X´автомат может перейти:
- в состояние ´X.X.XX´
- в состоянии ´start´
Из состояния ´X.X.XX´ автомат может перейти:
- в состояние ´X.X.XXX´
- в состоянии ´start´
Из состояния ´X.X.XXX´ автомат может перейти:
- в состояние ´X.X.XXXX´
- в состоянии ´start´
Из состояния ´X.X.XXXX´ автомат может перейти:
- в состоянии ´start´
Из состояния ´X.X.XXX´ автомат может перейти:
- в состояние ´X.X.XXXX´
- в состоянии ´start´
Из состояния ´XXX´ автомат может перейти:
- в состояние ‘XXXX´
- в состоянии ´start´
Из состояния ´XXXX´ автомат может перейти:
- в состояние ‘XXXX.´
- в состоянии ´start´
Из состояния ´XXXX.´ автомат может перейти:
- в состояние ‘XXXX.X´
- в состоянии ´start´
Из состояния ´XXXX.X´ автомат может перейти:
- в состояние ‘XXXX.XX´
- в состоянии ´start´
Из состояния ´XXXX.XX´ автомат может перейти:
- в состояние ‘XXXX.XX.´
- в состоянии ´start´
Из состояния ´XXXX.XX.´ автомат может перейти:
- в состояние ‘XXXX.XX.X´
- в состоянии ´start´
Из состояния ´XXXX.XX.X´ автомат может перейти:
- в состояние ‘XXXX.XX.XX´
- в состоянии ´start´
Из состояния ´XX. автомат может перейти:
- в состояние ‘XX.X.´
- в состоянии ´start´
Из состояния ´XX.X автомат может перейти:
- в состояние ‘XX.XX´
- в состоянии ´start´
Из состояния ´XX.XX автомат может перейти:
- в состояние ‘XX.XX.´
- в состоянии ´start´
Из состояния ´XX.XX. автомат может перейти:
- в состояние ‘XX.XX.X´
- в состоянии ´start´
Из состояния ´XX.XX.X автомат может перейти:
- в состояние ‘XX.XX.XX´
- в состоянии ´start´
Из состояния ´XX.XX.XX автомат может перейти:
- в состояние ‘XX.XX.XXX´
- в состоянии ´start´
Из состояния ´XX.XX.XXX автомат может перейти:
- в состояние ‘XX.XX.XXXX´
- в состоянии ´start´
Программный код:
#coding=windows-1251
import os
from enum import Enum
in_file1="E:\1\in_file.txt" # файл
out_file1="E:\1\out_file.txt" # файл
if os.path.exists(in_file1): #проверка существования файла для чтение входных данных
in_file = open(in_file1,´r´)
if os.path.exists(out_file1): #проверка существования файла для записи
out_file = open(out_file1,´w´)
Hislo = (´1´,´2´,´3´,´4´,´5´,´6´,´7´,´8´,´9´,´0´) #массив чисел
EDate = (´ ´,´.´)
Raz = (´.´,´-´,´/´)
State = Enum
(´start´, #базовое состояние(обычный текст)
´X´, #состояние когда встретилась одна цифра
´XX´, #состояние когда встретилось две цифры
´X.´, #состояние когда встретилась одна цифра и разделитель
´X.X´, #состояние когда встретилась одна цифра, разделитель и снова цифра
´X.X.´,
´X.X.X´,
´XXX´,
´XXXX´,
´XXXX.´,
´XXXX.X´,
´XXXX.XX´,
´XXXX.XX.´,
´XXXX.XX.X´,
´XXXX.XX.XX´, #состояние когда встретилась дата вида : 1998.1.2,1998-1-2 или 1998/1/2
´X.X.XX´,
´X.X.XXX´,
´X.X.XXXX´, #состояние когда встретилась дата вида : 2.1.1998,2-1-1998 или 2/1/1998
´XX.´,
´XX.X´,
´XX.XX´,
´XX.XX.´,
´XX.XX.X´,
´XX.XX.XX´, #состояние когда встретилась дата вида : 12.11.98, 12-11-98 или 12/11/98
´XX.XX.XXX´,
´XX.XX.XXXX´) #состояние когда встретилась дата вида : 12.11.2010, 12-11-2010 или 12/11/2010
state= ´start´
while True:
f= in_file.read(1)
out_file.write(f)
if f == ´ ´:
break
elif state==´start´:
if f in Hislo:
state=´X´
else:
state= ´start´
elif state==´X´: #когда найдена одна цифра
if f in Hislo:
state=´XX´
elif f in Raz:
state=´X.´
else:
state= ´start´
elif state==´XX´: #когда найдено 2 числа подряд
if f in Hislo:
state=´XXX´
elif f in Raz:
state="XX."
else:
state= ´start´
elif state ==´X.´: #когда найдено X.
if f in Hislo:
state=´X.X´
else:
state= ´start´
elif state ==´X.X´: #когда найдено X.
if f in Raz:
state=´X.X.´
else:
state= ´start´
elif state ==´X.X.´: #когда найдено X.
if f in Hislo:
state=´X.X.X´
else:
state= ´start´
elif state ==´X.X.X´: #когда найдено X.
if f in Hislo:
state=´X.X.XX´
else:
state= ´start´
elif state ==´XXX´: #когда найдено XXX
if f in Hislo:
state=´XXXX´
else:
state= ´start´
elif state ==´XXXX´: #когда XXXX
if f in Raz:
state=´XXXX.´
else:
state=´start´
elif state ==´XXXX.´: #когда XXXX.
if f in Hislo:
state=´XXXX.X´
else:
state=´start´
elif state ==´XXXX.X´: #
if f in Hislo:
state=´XXXX.XX´
else:
state=´start´
elif state ==´XXXX.XX´: #
if f in Raz:
state=´XXXX.XX.´
else:
state=´start´
elif state ==´XXXX.XX.´: #
if f in Hislo:
state=´XXXX.XX.X´
else:
state=´start´
elif state ==´XXXX.XX.X´: #
if f in Hislo:
state=´XXXX.XX.XX´
else:
state=´start´
elif state ==´XXXX.XX.XX´: #записываем дату
if f in EDate: #если после даты точка или пробел
out_file.seek(-11, 1) # смещение на 11 байт относительно указателя
in_file.seek(-3, 1)
v= in_file.read(2)
out_file.write(v)
out_file.write(´.´)
in_file.seek(-5, 1)
v= in_file.read(2)
out_file.write(v)
out_file.write(´.´)
in_file.seek(-7, 1)
v= in_file.read(4)
out_file.write(v)
in_file.seek(6, 1)
state=´start´
else:
state=´start´
elif state ==´X.X.XX´: #записываем дату
if f in EDate: #если после даты точка или пробел
out_file.seek(-7, 1) # смещение на 7 байт относительно указателя
in_file.seek(-7, 1)
v= in_file.read(1)
out_file.write(´0´)
out_file.write(v)
out_file.write(´.´)
in_file.seek(1, 1)
v= in_file.read(1)
out_file.write(´0´)
out_file.write(v)
out_file.write(´.´)
in_file.seek(1, 1)
v= in_file.read(2)
out_file.write(´19´)
out_file.write(v)
state=´start´
elif f in Hislo:
state=´X.X.XXX´
else:
state=´start´
elif state ==´X.X.XXX´: #
if f in Hislo:
state=´X.X.XXXX´
else:
state=´start´
elif state ==´X.X.XXXX´: #записываем дату
if f in EDate: #если после даты точка или пробел
out_file.seek(-9, 1) # смещение на 9 байт относительно указателя
in_file.seek(-9, 1)
v= in_file.read(1)
out_file.write(´0´)
out_file.write(v)
out_file.write(´.´)
in_file.seek(1, 1)
v= in_file.read(1)
out_file.write(´0´)
out_file.write(v)
out_file.write(´.´)
in_file.seek(1, 1)
v= in_file.read(4)
out_file.write(v)
state=´start´
else:
state=´start´
elif state ==´XX.´: #
if f in Hislo:
state=´XX.X´
else:
state=´start´
elif state ==´XX.X´: #
if f in Hislo:
state=´XX.XX´
else:
state=´start´
elif state ==´XX.XX´: #
if f in Raz:
state=´XX.XX.´
else:
state=´start´
elif state ==´XX.XX.´: #
if f in Hislo:
state=´XX.XX.X´
else:
state=´start´
elif state ==´XX.XX.X´: #
if f in Hislo:
state=´XX.XX.XX´
else:
state=´start´
elif state ==´XX.XX.XX´: #
if f in Hislo:
state=´XX.XX.XXX´
elif f in EDate: #если после даты точка или пробел
out_file.seek(-9, 1) # смещение на 9 байт относительно указателя
in_file.seek(-9, 1)
v= in_file.read(2)
out_file.write(v)
out_file.write(´.´)
in_file.seek(1, 1)
v= in_file.read(2)
out_file.write(v)
out_file.write(´.´)
in_file.seek(1, 1)
out_file.write(´19´)
v= in_file.read(2)
out_file.write(v)
state=´start´
else:
state=´start´
elif state ==´XX.XX.XXX´: #
if f in Hislo:
state=´XX.XX.XXXX´
else:
state=´start´
elif state ==´XX.XX.XXXX´: #
if f in EDate: #если после даты точка или пробел
out_file.seek(-11, 1) # смещение на 11 байт относительно указателя
in_file.seek(-11, 1)
v= in_file.read(2)
out_file.write(v)
out_file.write(´.´)
in_file.seek(1, 1)
v= in_file.read(2)
out_file.write(v)
out_file.write(´.´)
in_file.seek(1, 1)
v= in_file.read(4)
out_file.write(v)
state=´start´
else:
state=´start´
else:
pass # ничего не делаем
in_file.close() # закрытие файла
out_file.close() # закрытие файла
Тестирование