VPF::Пример для теории конечных автоматов

ZVano

Дата 5.10.2011, 09:37 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 259
Регистрация: 11.12.2006
Где: Украина, Кривой Р ог

Репутация: 1
Всего: 4

Наткнулся на статью, в которой "на пальцах" объясняют принцип теории конечных автоматов.
Решил поделиться.

Этот принцип программирования удобно использовать для парсинга структурированых текстов (исходники на разных языках программирования, XML, HTML и т.п.)

Статья: "Психология автоматного программирования"
Автор: Кузнецов Б.П.
URL: тут
Пример на liveworkspace.org: тут

Задача:
Даны два массива. Каждый из них содержит последовательность неповторяющихся чисел, завершающуюся нулем.
Второй массив содержит ту же, что и в первом, последовательность, но включает вставки из чисел, отсутствующих в первом массиве.
Программа должна сравнить два массива и напечатать встречающиеся вставки.
Для упрощения полагаем, что точно известно: какой из двух массивов содержит вставки.

Код решения:

Код


// collation.cpp Сличение числовых массивов, завершающихся нулем.
// (Пример автоматного программирования)
// Copyright © Кузнецов Б.П. Санкт-Петербург 06.08.2000 
// [email protected]
// 20111005 - Загляда И.М. Изменено для использования на liveworkspace.org в режиме с++ 
#include <stdio.h>
#include <iostream>

/**
 * вывод на экран вставки ====
**/ 
void insert(int s2, int c2, int *m2) 
{
  int i;
  std::cout << std::endl; 
  printf("insert: ");
  for(i = s2; i <= c2; i++)
    printf("%d ",m2[i]);
}


/**
 * подпрограмма сличения ==========
 * m1, m2 - сличаемые масивы
**/ 
void collation(int *m1, int *m2) 
                                 
{ 
  static char state = 'A'; // символ состояния подпрограммы сличения
  int cycle = 1; // 0 - признак окончания цикла
  int s1, s2; // текущие номера элементов двух массивов
  int c1, c2; // запоминаемые номера элементов двух массивов

  while(cycle) // локальный цикл подпрограммы
    switch(state) // распознавание текущего состояния графа переходов
    {
    case 'A': // исходное состояние
        s1 = s2 = -1; // подготовка к счету элементов массивов
        state = 'B'; // переход к состоянию В
        break;

    case 'B': // состояние ожидания неравенства элементов массивов
                // (вставки)
        s1++; s2 ++; // переход к очередной паре элементов массивов
        if(!m2[s2] && m1[s1]) // конец второго массива
        {
          printf("n Массив М1 надо сличать на удалениеn");
          state = 'A'; // перевод подпрограммы в исходное состояние
          cycle = 0; // обеспечение выхода из цикла
        }
        else if(m1[s1] == m2[s2] && !m1[s1]) // конец обоих массивов
        {
          state = 'A'; // перевод подпрограммы в исходное состояние
          cycle = 0; // обеспечение выхода из цикла
        }
        else if(m1[s1] != m2[s2]) // достигли очередной вставки
        { 
          c1 = s1;
          c2 = s2; // запоминаем текущие номера элементов массивов
          state = 'C'; // переход к состоянию С
        }
        else ; // элементы массивов равны и не нулевые
        // продолжаем цикл в состоянии В
        break;

    case 'C': // состояние ожидания равенства элементов после вставки
        c2++; // переход к очередной строке второго массива
        if(!m2[c2]) // конец второго массива - вставка до его конца
        {
          insert(s2, c2 - 1, m2); // печать вставки
          state = 'A'; // перевод подпрограммы в исходное состояние
          cycle = 0; // обеспечение выхода из цикла
        }
        else if(m1[c1] == m2[c2]) // конец вставки
        {
          insert(s2, c2 - 1, m2); // печать вставки
          s1 = c1;
          s2 = c2; // подготовка к продолжению сравнения массивов
          state = 'B'; // возврат к состоянию В
        }
        else ; // пока еще "продолжается" вставка 
               // продолжаем цикл в состоянии С
        break;
    }
} 



int main (void){
   int m1[10] = {1,2,3,4,5,6,7,8,9,0};
   int m2[15] = {1,2,3, 31, 32, 33, 4,5, 51, 52, 6,7,8,9,0};
   collation(&m1[0], &m2[0]);
}

Это сообщение отредактировал(а) ZVano - 5.10.2011, 09:40

--------------------

НЕ ФЛУДИМ. Пользуемся кнопками "+" или "-" для выражения своего отношения к теме или сообщению.
Гуглим "Как правильно задавать вопросы"

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »