шаблоны проектирования — код C ++ для конечного автомата

Рассмотрите возможность использования таблиц вместо switch заявления. Один столбец может быть критерием перехода, а другой столбец — состоянием назначения.

Это хорошо масштабируется, потому что вам не нужно менять функцию обработки таблицы; просто добавьте еще одну строку в таблицу.

+------------------+---------------------+---------------+
| Current state ID | transition criteria | Next state ID |
+------------------+---------------------+---------------+
|                  |                     |               |
+------------------+---------------------+---------------+

В моем рабочем коде мы используем столбец указателей на функции, а не «Идентификатор следующего состояния». Таблица представляет собой отдельный файл с определенными функциями доступа. Существует один или несколько операторов включения для разрешения каждого указателя на функцию.

Редактировать 1: Пример отдельных файлов таблиц.

table.h

#ifndef TABLE_H
#define TABLE_H

struct Table_Entry
{
unsigned int  current_state_id;
unsigned char transition_letter;
unsigned int  next_state_id;
};

Table_Entry const *    table_begin(void);
Table_Entry const *    table_end(void);

#endif // TABLE_H

table.cpp:

#include "table.h"
static const Table_Entry    my_table[] =
{
//  Current   Transition     Next
//  State ID    Letter     State ID
{    0,          'A',        1}, // From 0 goto 1 if letter is 'A'.
{    0,          'B',        2}, // From 0 goto 2 if letter is 'B'.
{    0,          'C',        3}, // From 0 goto 3 if letter is 'C'.
{    1,          'A',        1}, // From 1 goto 1 if letter is 'A'.
{    1,          'B',        3}, // From 1 goto 3 if letter is 'B'.
{    1,          'C',        0}, // From 1 goto 0 if letter is 'C'.
};

static const unsigned int  TABLE_SIZE =
sizeof(my_table) / sizeof(my_table[0]);Table_Entry const *
table_begin(void)
{
return &my_table[0];
}Table_Entry const *
table_end(void)
{
return &my_table[TABLE_SIZE];
}

state_machine.cpp

#include "table.h"#include <iostream>

using namespace std;  // Because I'm lazy.

void
Execute_State_Machine(void)
{
unsigned int current_state = 0;
while (1)
{
char transition_letter;
cout << "Current state: " << current_state << "\n";
cout << "Enter transition letter: ";
cin >> transition_letter;
cin.ignore(1000, '\n'); /* Eat up the '\n' still in the input stream */
Table_Entry const *  p_entry = table_begin();
Table_Entry const * const  p_table_end =  table_end();
bool state_found = false;
while ((!state_found) && (p_entry != p_table_end))
{
if (p_entry->current_state_id == current_state)
{
if (p_entry->transition_letter == transition_letter)
{
cout << "State found, transitioning"<< " from state " << current_state
<< ", to state " << p_entry->next_state_id
<< "\n";
current_state = p_entry->next_state_id;
state_found = true;
break;
}
}
++p_entry;
}
if (!state_found)
{
cerr << "Transition letter not found, current state not changed.\n";
}
}
}

Однажды я написал конечный автомат на C ++, где мне понадобился один и тот же переход для множества пар состояний (пары источник-цель). Я хочу проиллюстрировать пример:

4 -> 8   \
5 -> 9    \_ action1()
6 -> 10   /
7 -> 11  /

8 -> 4   \
9 -> 5    \_ action2()
10 -> 6   /
11 -> 7  /

Я придумал набор (критерии перехода + следующее состояние + функция «действие», которую нужно вызвать). Для простоты оба критерия перехода и следующее состояние были записаны как функторы (лямбда-функции):

typedef std::function<bool(int)> TransitionCriteria;
typedef std::function<int(int)>  TransitionNewState;
typedef std::function<void(int)> TransitionAction;   // gets passed the old state

Это решение хорошо, если у вас есть много переходов, которые применяются для множества различных состояний, как в примере выше. Однако для каждого «шага» этот метод требует линейного сканирования списка всех различных переходов.

Для приведенных выше примеров будет два таких перехода:

struct Transition {
TransitionCriteria criteria;
TransitionNewState newState;
TransitionAction action;

Transition(TransitionCriteria c, TransitionNewState n, TransitionAction a)
: criteria(c), newState(n), action(a) {}
};
std::vector<Transition> transitions;

transitions.push_back(Transition(
[](int oldState){ return oldState >= 4 && oldState < 8; },
[](int oldState){ return oldState + 4; },
[](int oldState){ std::cout << "action1" << std::endl; }
));
transitions.push_back(Transition(
[](int oldState){ return oldState >= 8 && oldState < 12; },
[](int oldState){ return oldState - 4; },
[](int oldState){ std::cout << "action2" << std::endl; }
));

Я не знаю, помогло бы это вам пройти собеседование, но я лично воздерживался бы от кодирования любого автомата вручную, особенно если он в профессиональной обстановке. Конечные автоматы — это хорошо изученная проблема, и существуют хорошо протестированные инструменты с открытым исходным кодом, которые часто генерируют код, превосходящий то, что вы создадите сами, а также помогают диагностировать проблемы с вашим конечным автоматом, например. возможность генерировать диаграммы состояния автоматически.

Мои инструменты goto для решения этой проблемы:

• Ragel
• SMC

Я написал множество конечных автоматов, используя эти методы. Но когда я написал Transceiver Library для Nexus 7000 (коммутатор стоимостью $ 117 000), я использовал метод, который изобрел в 80-х годах. Это было использование макроса, который делает конечный автомат больше похожим на многозадачный код блокировки. Макросы написаны для C, но я использовал их с небольшими изменениями для C ++, когда работал на DELL. Вы можете прочитать больше об этом здесь: https://www.codeproject.com/Articles/37037/Macros-to-simulate-multi-tasking-blocking-code-at

#include <stdio.h>
#include <iostream>

using namespace std;
class State;

enum state{ON=0,OFF};
class Switch {
private:
State* offState;
State* onState;
State* currState;
public:
~Switch();
Switch();
void SetState(int st);
void on();
void off();
};
class State{
public:
State(){}
virtual void on(Switch* op){}
virtual void off(Switch* op){}
};
class OnState : public State{
public:
OnState(){
cout << "OnState State Initialized" << endl;
}
void on(Switch* op);
void off(Switch* op);
};
class OffState : public State{
public:
OffState(){
cout << "OffState State Initialized" << endl;
}
void on(Switch* op);
void off(Switch* op);
};
Switch::Switch(){
offState = new OffState();
onState = new OnState();
currState=offState;
}
Switch::~Switch(){
if(offState != NULL)
delete offState;
if(onState != NULL)
delete onState;
}
void Switch::SetState(int newState){
if(newState == ON)
{
currState = onState;
}
else if(newState == OFF)
{
currState = offState;
}
}
void Switch::on(){
currState->on(this);
}
void Switch::off(){
currState->off(this);
}
void OffState::on(Switch* op){
cout << "State transition from OFF to ON" << endl;
op->SetState(ON);
}
void OffState::off(Switch* op){
cout << "Already in OFF state" << endl;
}
void OnState::on(Switch* op){
cout << "Already in ON state" << endl;
}
void OnState::off(Switch* op){
cout << "State transition from ON to OFF" << endl;
op->SetState(OFF);
}
int main(){
Switch* swObj = new Switch();
int ch;
do{
switch(ch){
case 1:     swObj->on();
break;
case 0:     swObj->off();
break;
default :   cout << "Invalid choice"<<endl;
break;
}
cout << "Enter 0/1: ";
cin >> ch;
}while(true);`enter code here`
delete swObj;
return 0;
}