Форум программистов, компьютерный форум CyberForum.ru

Построить детерминированный конечный распознаватель - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Анкета http://www.cyberforum.ru/cpp-beginners/thread319758.html
Анкета для опроса населения содержит две группы вопросов. Первая группа содержит сведения о респонденте: • возраст; • пол; • образование (начальное, среднее, высшее). Вторая группа содержит собственно вопрос анкеты, ответ на который либо ДА, либо НЕТ. Составить программу, используя последовательные классы стандартной библиотеки шаблонов С++, которая: • обеспечивает начальный ввод...
C++ Начало Си++ Я понимаю что данные задачи очень просты, но помогите пожалуйста...Я просто совсем нечего не шарю.. Задача 1 Дан массив X из N целых чисел. Найти индекс максимального элемента в массиве Х. Задача 2 Дан массив А из N элементов. Переставить элементы массива A в обратном порядке. Задача 3 Дан массив А из N элементов и число X. Определить, имеются ли в массиве A два расположенных рядом значения... http://www.cyberforum.ru/cpp-beginners/thread319728.html
C++ Сумма элементов
Найти сумму элементов массива между первым и вторым отрицательным элементом. Преобразование. Преобразовать массив так чтобы сначала стояли элементы по модулю меньше единицы потом все остальные. Прошу помощи,заранее благодарен.
C++ Строки
В алфавитной строке удалить строчные буквы и удвоить заглавные Пожалуйста, помогите
C++ двумерные массивы http://www.cyberforum.ru/cpp-beginners/thread319718.html
Характеристикой столбца целочисленной матрицы назовем сумму модулей его отрицательных нечетных элементов. Переставляя столбцы заданной матрицы, расположить их в соответствии с ростом характеристик. Найти сумму элементов в тех столбцах, которые содержат хотя бы один отрицательный элемент Помогите, пожалуйста
C++ Геометрическая фигура Постановка задачи. Разработать программу, которая выводит на экран геометрическую фигуру, заполняя ее символом ‘*’ или пробелом. Размер фигуры (n) определяется при вводе. Ниже приведены варианты: 1. Пустой параллелограмм. Основание n и высота n подробнее

Показать сообщение отдельно
ValeryLaptev
Эксперт С++
1040 / 819 / 48
Регистрация: 30.04.2011
Сообщений: 1,659
18.06.2011, 07:20
Вот ликбез. Тут и проги найдешь.

Перевод дробных констант
Перевод дробных констант немного сложнее целых: нужно отдельно вычислять целую и дробную часть числа, а так же показатель степени. Пусть, как ранее, целая часть числа накапливается в переменной N, дробная часть накапливается в переменной F, а показатель степени — в переменной P. Символы входной строки можно разделить на следующие классы:
- знак числа;
- цифра;
- точка;
- порядок — символы «E» или «е»;
- знак порядка — символы «+» или «-»;
- другой — все остальные символы.
Набор правил перехода можно записать так (не показаны переходы по ошибкам):
// start – начальное состояние
// допустимы: цифра – переход в s2
// точка – переход в s1
start: цифра -> s2; N = digit(ch); // заносим первую цифру
start: знак -> s1; если ch ==’-’ signN = -1; // учет знака
------------------
// s1: после знака
// допустимы: цифра – переход в s2
s1: цифра -> s2; N = digit(ch); // заносим первую цифру
------------------
// s2: после первой цифры
// допустимы: цифра – остаемся в s2
// точка - переход в s3
// порядок - переход в s5
// другой - конец числа, переход в finish
s2: цифра -> s1; N = N*10+digit(ch); // вычисляем целую часть
s2: точка -> s2; // закончилась целая часть
s2: E -> s5; // начался порядок
s2: другой -> finish; // завершаем
------------------
// s3: после точки
// допустимы: цифра - переход в s4
s3: цифра -> s4; FP = 0.1;
F = F+digit(ch)*0.1; // накапливаем дробную часть
------------------
// s4: после первой дробной цифры
// допустимы: цифра - остаемся в s4
// порядок - переход в s5
// другой - конец числа, переход в finish
s4: цифра -> s3; FP = FP/10;
F = F+digit(ch)*FP; // накапливаем дробную часть
s4: E -> s5; signP = знак; // запомнили знак порядка
s4: другой -> finish; // завершаем
------------------
// s5: после E
// допустимы: знак - переход в s6
цифра - переход в s7
s5: знак -> s6; signP = знак; // знак порядка
s5: цифра -> s7; P = digit(ch); // первая цифра порядка
------------------
// s6: после знака порядка
// допустимы: цифра - переход в s6
s6: цифра –> s7
------------------
// s7: после первой цифры порядка
// допустимы: цифра - остаемся в s7
// другой - конец числа, переход в finish
s7: цифра -> s7; P = P*10+digit(ch); // вычисляем порядок
s7: другой -> finish; // завершаем
Первый выбираемый из строки символ может быть только знаком или цифрой — тем самым мы запрещаем начинать число непосредственно с точки. Если первый символ — не знак и не цифра, то имеем ошибку. Аналогично, после точки тоже должна быть хотя бы одна цифра — таким образом, мы запрещаем записывать и константы, завершающиеся точкой. Описание остальных состояний приведено в комментариях.
На финише окончательно вычисляется число по формуле:
C++
1
2
3
4
5
D = (N + F);
// учли знак порядка
если signP = +1, то D = D *(10^P);      
если signP = -1, то D = D /(10^P);
D = D * signN;                  // учли знак числа
Реализация выполнена новым способом — с помощью матрицы переходов. Матрица переходов представляет собой прямоугольную матрицу, строки которой определяют классы символов, а столбцы — состояния . Значением каждого элемента является состояние, в которое должен перейти автомат из текущего при заданном входном символе. При этом состояния finish и error можно не заполнять.

Представление автомата в виде матрицы переходов очень наглядно и часто помогает увидеть то, что трудно понять при изображении автомата в виде графа или в виде набора правил. Например, переходы в состояние ошибки должны быть определены во всех состояниях при всех входных символах. Матрица описанного автомата представлена в табл. 5.1.
Таблица 5.1. Матрица переходов преобразователя
start s1 s2 s3 s4 s5 s6 s7 finish error
цифра s2 s2 s2 s4 s4 s7 s7 s7
точка error error s3 error error error error error
порядок error error s5 error s5 error error error
знак s1 error error error error s6 error error
другой error error finish error finish error error finish
Обратите внимание, что столбцы матрицы, соответствующие состояниям s1, s3 и s5 отличаются только первым элементом. Такие столбцы — первые кандидаты на сокращение. Для автомата-распознавателя такой матрицы вполне достаточно — в листинге 5.4 показана функция-автомат вместе с функцией type(), определяющей тип символа.
C++
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
Листинг 5.4.  Распознаватель дробного числа
enum State              // состояния
{ start, s1, s2, s3, s4, s5, s6, s7, fin, err, statesCount = fin };
enum Symbol                 // классы символов
{ Digit, Point, Exp, Sign, Other, ClassCount };
Symbol type(char ch)            // определение класса символа
{ if(isdigit(ch))           return Digit;
  if(ch =='.')              return Point;
  if((ch =='e')||(ch =='E'))    return Exp; 
  if((ch =='-')||(ch =='+'))    return Sign;
  return Other;
}
// распознаватель дробного числа
bool Double(const string &str)
{ State matrix[ClassCount][statesCount] =       // матрица переходов
  {{s2,   s2,  s2,  s4,  s4,     s7,  s7,  s7 },    // цифра Digit 
   {err, err, s3,  err, err, err, err, err},    // точка Point
   {err, err, s5,  err, s5,  err, err, err},    // порядок Exp
   {s1,  err, err, err, err, s6,  err, err},    // знак Sign
   {err, err, fin, err, fin, err, err, fin}     // другой Other
  };
  size_t n = 0;
  State s = start;              // начальное состояние
  while(s != finish)
  {  Symbol t = type(str[n++]);     // получили класс символа
     s = matrix[t][s];          // следующее состояние
     if (s == err) return false;
  }
  return true;          // сюда попадаем только в состоянии finish;
}
Здесь не учтен вариант, когда отсутствует «другой» символ и последним символом строки является цифра. Для устранения этой небольшой проблемы достаточно проверять переменную n — индекс символа в строке
Реализация, как и предыдущий вариант с функциями-состояниями (см. листинг 5.3 и 5.4), тоже проста — в основном цикле ДКА всего 3 строки.
Для преобразователя помимо матрицы переходов нужно определить функции для вычисления числа. Пусть все данные для числа содержатся в следующей структуре:
C++
1
2
3
4
5
6
7
8
9
10
struct Number
{   int signN;      // знак числа
       double N;        // целая часть числа
    double F;       // дробная часть числа
    double FP;      // коэффициент умножения дробной части
    bool signP;     // знак порядка
    double P;       // порядок
    // конструктор по умолчанию
    Number():signN(+1),N(),FP(),F(),signP(true),P() {}
}
;
Каждая функция, реализующая свою часть преобразования, должна получать в качестве параметров такую структуру и очередной символ. Функции требуется вызывать в основном цикле в определенных состояниях. Поэтому если функция возвращает следующее состояние, то вместо матрицы состояний можно инициализировать матрицу указателей на функции:
C++
1
2
3
4
5
6
7
8
typedef State (*Action)(const char &ch, Number &D);
Action matrix[Class][states];
Тогда вызов функции выполняется в цикле таким образом:
while((s != finish))
{  Symbol t = type(str[n]);     // класс символа
   s = matrix[t][s](str[n], D);     // вызов функции
   ++n;                 // следующий символ
}
Функций требуется реализовать меньше, чем элементов в матрице состояний, так как в ней много одинаковых элементов.

Главная функция преобразователя Double() возвращает число типа double. Если во входной строке обнаружены ошибки, то возвращается 0. В этом случае устанавливается глобальный флаг ошибки flagError, который может проверить вызывающая функция. Полная реализация преобразователя (структура Number показана выше) представлена в листинге 5.5.
C++
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
Листинг 5.5. Реализация конечного преобразователя для перевода дробных чисел
// автомат-преобразователь для дробных констант
// функция вычисления цифры
const int notDigit = -1;            // не цифра
int digit(char ch)
{ string digits = "0123456789";
  int d;
  for(d = 0; d < 10; ++d)
    if(ch == digits[d]) return d;
  return notDigit;              // символ - не цифра
}
// функция вычисления класса символа
enum Symbol { D, P, E, S, O, Class };
Symbol type(char ch)
{ if(isdigit(ch)) return D;
  if(ch =='.')    return P;
  if((ch =='e')||(ch=='E')) return E; 
  if((ch =='-')||(ch=='+')) return S;
  return O;
}
// состояния
enum State { start, s1, s2, s3, s4, s5, s6, s7, finish, error }; 
// обработка состояния ошибки
State Error(const char &ch, Number &D) 
{ Error.set();      // установка флага ошибки 
  return error; 
}
// завершение обработки
State Other(const char &ch, Number &D)
{ return finish; }
// в состоянии start – обработка знака
State startS(const char &ch, Number &D)
{ if (ch == '-') D.signN = -1; 
  return s1;    // первая цифра
}
// в состоянии start и s1 – обработка первой цифры
State startD(const char &ch, Number &D) 
{ D.N = digit(ch);
  return s2;    // целая часть
}
// в состоянии s2 – обработка цифр целой части
State intD(const char &ch, Number &D)
{ D.N = D.N * 10 + digit(ch);
  return s2;    // целая часть
}
// в состоянии s2 – обработка точки
State Point(const char &ch, Number &D)
{ return s3; }  // после точки
 
// в состоянии s2 – обработка E
State Exp(const char &ch, Number &D)
{ return s5; }  // после E
// в состоянии s3 – обработка первой цифры после точки
State float1D(const char &ch, Number &D)
{ D.FP = 0.1;  D.F = digit(ch) * D.FP;
  return s4;    // дробная часть
}
// в состоянии s4 – обработка цифр дробной части
State floatD(const char &ch, Number &D) 
{ D.FP/=10; D.F = D.F + digit(ch) * D.FP;
  return s4;    // дробная часть
}
// в состоянии s5 и s6 – обработка первой цифры порядка
State exp1D(const char &ch, Number &D) 
{ D.P = digit(ch);
  return s7;    // порядок     
}
// в состоянии s6 – обработка знака порядка
State expS(const char &ch, Number &D) 
{ if(ch == '-') D.signP = false;
  return s7;    // порядок 
}
// в состоянии s7 – обработка цифр порядка
State expD(const char &ch, Number &D) 
{ D.P = D.P * 10 + digit(ch);
  return s7;    // порядок
}
typedef State (*Action)(const char &ch, Number &D); 
double Double(const string &str)
{ Action matrix[Class][states] =
//start   s1      s2     s3       s4      s5     s6     s7
//перед   после   целая  после    дроб.   после  после  порядок
//числом  знака   часть  точки    часть   Е      знака Е
{{startD, startD, intD,  float1D, floatD, exp1D, exp1D, expD },// цифра 
 {Error,  Error,  Point, Error,   Error,  Error, Error, Error},// точка
 {Error,  Error,  Exp,   Error,   Exp,    Error, Error, Error},// порядок
 {startS, Error,  Error, Error,   Error,  expS,  Error, Error},// знак
 {Error,  Error,  Other, Error,   Other,  Error, Error, Other} // другой 
};
  Number D;
  double result;            // возвращаемый результат
  size_t n = 0;         // индекс символа в строке
  State s = start;          // начальное состояние
  while((s != finish)&&(s != error)&&(n < str.size()))
  { Symbol t = type(str[n]);        // получили класс символа
    s = matrix[t][s](str[n], D);    // вызов функции
    ++n;                // след символ
  }
// проверка состояния при выходе  
  if ((s==s2)||(s==s4)||(s==s7)||   // финишные состояния
      (s==finish))
  { result = D.N+D.F;
    if(!D.signP) D.P = -D.P;
    result = D.signN * result * pow(10.0, D.P);
  }
  else result = 0;
  return result;
}
Для получения цифры преобразователь использует функцию digit(), аналогичную описанной в листинге 5.3.
Обратите внимание на то, что функции Point() и Exp(), обрабатывающие символы точки и экспоненты, фактически не делают ничего, кроме перехода в новое состояние. Это довольно частое явление при разработке конечных преобразователей. Функция отражает некоторое состояние. «Пустые» состояния необходимы для отслеживания правильной последовательности символов во входной строке.

Заметим, что состояния, в которых вызывается функция, обрабатывающая «другой» символ (s2, s4, s7), являются финишными — это хорошо видно в матрице состояний автомата-распознавателя. Если во входной строке в конце нет «другого» символа, то автомат выходит из цикла при исчерпании символов строки. Поэтому в основной функции после цикла обработки выполняется проверка, в каком состоянии находился автомат после обработки всей строки.
Хотя преобразователь прекрасно работает с правильными аргументами, однако в нем нет проверки на диапазон порядка. Как известно, порядок числа типа double должен быть в диапазоне от -308 до +308.

Поэтому если пользователь напишет число с порядком вне этого диапазона, наш автомат-преобразователь выдаст неверный результат. Таким образом, автомат должен отслеживать количество цифр порядка (не более 3) и проверять численное значение порядка. Оставляем читателю эту модификацию преобразователя в качестве упражнения (см. «Контрольные вопросы и упражнения»).

Несмотря на то, что реализация выглядит простой и прозрачной, в ней есть свои сложности. Во-первых, теряется наглядность перехода в новое состояние — переход спрятан в функции. Во-вторых, если матрица состояний имеет большую размерность, и функций-обработчиков достаточно много, то заполнение матрицы представляет серьезную проблему. Чтобы избежать ошибок, приходится подробно выписывать правила перехода: в состоянии State при наличии символа S вызвать функцию f(), перейти в состояние Next.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru