Код С++ для конечного автомата

Ответ 1

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

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

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

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

Изменить 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";
         }
    }
}

Ответ 2

Я думал о более OO-подходе, используя State Pattern:

Машина:

// machine.h
#pragma once

#include "MachineStates.h"

class AbstractState;
class Machine {
    friend class AbstractState;
    public:
        Machine(int inStockQuantity);
        void sell(int quantity);
        void refill(int quantity);
        int getCurrentStock();
        ~Machine();
    private:
        int mStockQuantity;
        AbstractState* mState;
};

// machine.cpp
#include "Machine.h"

Machine::Machine(int inStockQuantity) :
    mStockQuantity(inStockQuantity), mState(new Normal()) {
}

Machine::~Machine() {
    delete mState;
}

void Machine::sell(int quantity) {
    mState->sell(*this, quantity);
}

void Machine::refill(int quantity) {
    mState->refill(*this, quantity);
}

int Machine::getCurrentStock() {
    return mStockQuantity;
}

Государства:

// MachineStates.h
#pragma once

#include "Machine.h"
#include <exception>
#include <stdexcept>

class Machine;

class AbstractState {
    public:
        virtual void sell(Machine& machine, int quantity) = 0;
        virtual void refill(Machine& machine, int quantity) = 0;
        virtual ~AbstractState();
    protected:
        void setState(Machine& machine, AbstractState* st);
        void updateStock(Machine& machine, int quantity);
};

class Normal : public AbstractState {
    public:
        virtual void sell(Machine& machine, int quantity);
        virtual void refill(Machine& machine, int quantity);
        virtual ~Normal();
};

class SoldOut : public AbstractState {
    public:
        virtual void sell(Machine& machine, int quantity);
        virtual void refill(Machine& machine, int quantity);
        virtual ~SoldOut();
};

// MachineStates.cpp
#include "MachineStates.h"

AbstractState::~AbstractState() {
}

void AbstractState::setState(Machine& machine, AbstractState* state) {
    AbstractState* aux = machine.mState;
    machine.mState = state; 
    delete aux;
}

void AbstractState::updateStock(Machine& machine, int quantity) {
    machine.mStockQuantity = quantity;
}

Normal::~Normal() {
}

void Normal::sell(Machine& machine, int quantity) {
    int currStock = machine.getCurrentStock();
    if (currStock < quantity) {
        throw std::runtime_error("Not enough stock");
    }

    updateStock(machine, currStock - quantity);

    if (machine.getCurrentStock() == 0) {
        setState(machine, new SoldOut());
    }
}

void Normal::refill(Machine& machine, int quantity) {
    int currStock = machine.getCurrentStock();
    updateStock(machine, currStock + quantity);
}

SoldOut::~SoldOut() {
}

void SoldOut::sell(Machine& machine, int quantity) {
    throw std::runtime_error("Sold out!");
}

void SoldOut::refill(Machine& machine, int quantity) {
    updateStock(machine, quantity);
    setState(machine, new Normal());
}

Я не привык программировать на С++, но этот код явно компилируется против GCC 4.8.2, а valgrind не показывает утечек, поэтому я думаю, это нормально. Я не деньги, но мне это не нужно, чтобы показать вам эту идею.

Чтобы проверить это:

#include <iostream>
#include <stdexcept>
#include "Machine.h"
#include "MachineStates.h"

int main() {
    Machine m(10);

    m.sell(10);
    std::cout << "Sold 10 items" << std::endl;

    try {
        m.sell(1);
    } catch (std::exception& e) {
        std::cerr << e.what() << std::endl;
    }

    m.refill(20);
    std::cout << "Refilled 20 items" << std::endl;

    m.sell(10);
    std::cout << "Sold 10 items" << std::endl;
    std::cout << "Remaining " << m.getCurrentStock() << " items" << std::endl;

    m.sell(5);
    std::cout << "Sold 5 items" << std::endl;
    std::cout << "Remaining " << m.getCurrentStock() << " items" << std::endl;

    try {
        m.sell(10);
    } catch (std::exception& e) {
        std::cerr << e.what() << std::endl;
    }

    return 0;
}

Выход:

Sold 10 items
Sold out!
Refilled 20 items
Sold 10 items
Remaining 10 items
Sold 5 items
Remaining 5 items
Not enough stock

Теперь, если вы хотите добавить состояние Broken, вам нужен еще один AbstractState ребенок. Возможно, вам также нужно добавить свойство Broken на Machine.

Чтобы добавить больше продуктов, у вас должна быть карта продуктов и их количество в запасе и т.д.

Ответ 3

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

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; }
));

Ответ 4

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

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

• Ragel
• SMC

Ответ 5

#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;
}

Ответ 6

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