aabzel Aug 27 2023 at 01:07

Техникум: Распознавание Вещественного Числа из Строчки

Easy

9 min

4.2K

Programming*Compilers*C*Industrial Programming*Programming microcontrollers*

Tutorial

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

Потом часто надо анализировать текстовые логи с SD-карты. Надо выхватывать вещественные числа из CSV строчек.

Еще это синтаксический разбор NMEA 0183 протокола, который есть во всех навигационных приемниках, чтобы банально прочитать широту и долготу.

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

Постановка задачи

Дана строка символов. Распознать вещественное (действительное) число из строчки символов. Если числа нет, то выдать ошибку. При этом прототип должен быть такой

bool try_str2real(const char* const text, double* const double_value);

Вот легальный алфавит символов в строчке: ' ', '+', '-', 0 1 2 3 4 5 6 7 8 9, 'e', 'E' '.' '\n' '\r'

Вот список тест кейсов:

№	Входная строка	Распознанное число	это вещественное число?
1	".0"	0.0	да
2	"+."	--	нет
3	"005047e+6"	5047000000	да
4	"-8115e957"	INF	да
5	"2e0"	2	да
6	"4e+"	--	нет
7	"."	--	нет
8	"12.5k"	12500	да
9	"100n"	0.0000001	да

Парсинг чисел из строки это еще тот классический случай когда без Test-driven development (TDD) эту задачу решить не просто нереально. Поэтому полный список тест-кейсов можно посмотреть тут.

По непонятной причине сайт LeetCode оценивает эту задачку уровня hard.

Хотя мне кажется, что тут нет ничего сложного. Вообще это тот редкий случай, когда на LeetCode мелькают реальные задачи из prod(а).

Решение

вещественное число- это по сути число для представления непрерывных физических величин (масса, напряжение, освещение и прочее).

Стандартная функция парсинга sscanf() ненадежная для ответственных систем. Функция sscanf() делает синтаксический разбор double тогда, когда это не требуется, да ещё и при этом выдает непредсказуемый результат. Вот отчет тестирования функции sscanf().

А если в sscanf() подать кириллическую 'е', то процесс и вовсе упадет в исключение!

Нужна более надежная реализация функции синтаксического разбора вещественных чисел из строчки.

Для начала определимся со схемой синтаксического разбора вещественного числа (DFS). Вот приблизительная схема разбора рационального числа

Глядя на эту схему можно выделить 5 или 6 четко выраженных состояния.

typedef enum{
	PARSE_NUMBER_STATE_PARSE_SIGN=1,
	PARSE_NUMBER_STATE_PARSE_INTEGER=2,
	PARSE_NUMBER_STATE_PARSE_FRACTION=3,
	PARSE_NUMBER_STATE_PARSE_EXPONENTA_SIGN=4,
	PARSE_NUMBER_STATE_PARSE_EXPONENTA_INTEGER=5,
	PARSE_NUMBER_STATE_DONE=6,

	PARSE_NUMBER_STATE_UNDEF=0
}ParseNumberStates_t;

Поэтому и решать эту задачу я буду при помощи конечно-автоматной методологии. Вот основная функция. Она прокручивает конечный автомат распознавания числа из строки.


typedef struct {
    double value;
    double mantissa;
    double exponenta;
    char cur_letter;
    int8_t sign;
    long double integer; /*uint64_t integer */
    uint32_t fraction_order;
    double fraction ;
    ParseNumberStates_t state;
    bool spot_mantissa;
    bool spot_exponent;
    int8_t exponent_sign;
    uint32_t exponent_integer;
}Text2NumberFsm_t;

bool try_str2real(const char* const text, double* const double_value){
    bool res = false;
    uint32_t len = 0;
    if(text){
        len = strlen(text);
        if(len){
            if(double_value){
                res = true;
            }
        }
    }

    if(res) {
        Text2NumberFsm_t Fsm;
        res = text_2_number_init(&Fsm);
        uint32_t i = 0;
        uint32_t ok = 0;
        uint32_t err = 0;
        LOG_DEBUG(STRING, "ParseDoubleIn:%u:[%s]", len, text);

        for(i=0; i<len; i++){
            Fsm.cur_letter = text[i];
            res = number_proc_one(&Fsm);
            if (res) {
                ok++;
            } else {
                err++;
                LOG_ERROR(STRING,"ProcErr: ch[%u]=%c ",i, text[i]);
                break;
            }
        }

        if(0==err) {
            Fsm.cur_letter ='\n';
            res = number_proc_one(&Fsm);
            if (res) {
                ok++;
            } else {
                err++;
            }
        }
        if (0==err) {
            *double_value = Fsm.value;
            res = true;
        } else {
            LOG_ERROR(STRING,"len:%u ok:%u",len, ok);
            res = false;
        }
    }
    return res;
}

Вот обработчик символа. Алгоритм меняется в зависимости от текущего состояния конечного автомата

static bool number_proc_one(Text2NumberFsm_t* Node){
    bool res = false;
    LOG_DEBUG(STRING, "Proc: %s",NumberParserFsm2Str(Node));
    if(Node) {
        switch (Node->state) {
            case PARSE_NUMBER_STATE_PARSE_SIGN:
                res = number_proc_parse_sign(Node); break;
            case PARSE_NUMBER_STATE_PARSE_INTEGER:
                res = number_proc_parse_integer(Node); break;
            case PARSE_NUMBER_STATE_PARSE_FRACTION:
                res = number_proc_parse_fracion(Node); break;
            case    PARSE_NUMBER_STATE_PARSE_EXPONENTA_SIGN:
                res = number_proc_parse_exponenta_sign(Node); break;
            case    PARSE_NUMBER_STATE_PARSE_EXPONENTA_INTEGER:
                res = number_proc_parse_exponenta_integer(Node); break;
            case PARSE_NUMBER_STATE_DONE:
                res = number_proc_done(Node); break;

        default: res = false; break;
        }

    }
    return res;
}

Вот инициализация конечного автомата для разбора вещественного числа.

static bool text_2_number_init(Text2NumberFsm_t* Node){
    bool res = false;
    if (Node) {
        Node->value = 0.0;
        Node->sign = 1;
        Node->integer = 0;
        Node->exponent_integer = 0;
        Node->fraction = 0.0;
        Node->fraction_order = 1;
        Node->spot_mantissa = false;
        Node->spot_exponent = false;
        Node->mantissa = 1.0;
        Node->exponent_sign = 1;
        Node->exponenta = 1.0;
        Node->cur_letter ='\0';
        Node->state = PARSE_NUMBER_STATE_PARSE_SIGN;
        res = true;
    }
    return res;
}

А это вспомогательные функции обработчики каждого отдельного состояния для того, чтобы всё функции в отдельности умещались на одном экране



bool  number_compose_result(Text2NumberFsm_t* Node){
    bool res = false;
    if(Node) {
    	if(Node->spot_mantissa) {
            Node->value = ( (double)Node->sign ) * (((double) Node->integer) + Node->fraction);
            LOG_DEBUG(STRING,"Val:%f",Node->value);
            Node->state = PARSE_NUMBER_STATE_DONE;
            res = true;
        } else {
            LOG_ERROR(STRING,"NoMantissa");
    	}
    }
    return res;
}

static bool number_proc_parse_sign(Text2NumberFsm_t* Node){
    bool res = false;
    switch(Node->cur_letter) {
    case 'E':
    case 'e': {
        Node->mantissa = 1.0;
        Node->spot_mantissa = false;
        Node->integer = 1;
        Node->fraction = 0.0;
        Node->state = PARSE_NUMBER_STATE_PARSE_EXPONENTA_SIGN;
        res = true;

    }break;

    case ' ': {
        res = true;
    }break;
    case '+': {
        Node->sign = 1;
        Node->state = PARSE_NUMBER_STATE_PARSE_INTEGER;
        res = true;
    }break;
    case '-': {
        Node->sign =-1;
        Node->state = PARSE_NUMBER_STATE_PARSE_INTEGER;
        res = true;
    }break;
    case '0':  {
        Node->sign =1;
        Node->spot_mantissa=true;
        Node->state = PARSE_NUMBER_STATE_PARSE_INTEGER;
        res = true;
    }break;
    case '1':
    case '2':
    case '3':
    case '4':
    case '5':
    case '6':
    case '7':
    case '8':
    case '9': {
        uint8_t digit = 0;
        Node->spot_mantissa = true;
        res= try_hex_char_to_u8((uint8_t) Node->cur_letter, &digit) ;
        Node->integer *=10;
        Node->integer += digit;

        Node->state = PARSE_NUMBER_STATE_PARSE_INTEGER;
    }break;
    case '.': {
    	Node->fraction_order = 1;
        Node->integer = 0;
        Node->spot_mantissa = false;
        Node->state = PARSE_NUMBER_STATE_PARSE_FRACTION;
        res = true;
    }break;
    case '\n':
        res = false;
        break;
    case '\r':
        res = false;
        break;
    default:
        res = false;
        break;
    }
    return res;
}

static bool number_mantissa_save(Text2NumberFsm_t* Node){
    bool res = false;
    if(Node) {
        Node->mantissa = ( (double)Node->sign   ) * (((double) Node->integer) + Node->fraction);
        LOG_DEBUG(STRING,"Mantissa:%f",Node->mantissa);
        res = true;
    }
    return res;
}

static bool number_proc_parse_integer(Text2NumberFsm_t* Node){
    bool res = false;
    switch(Node->cur_letter) {
    case 'E':
    case 'e': {
        res = number_mantissa_save(Node);
        Node->state =PARSE_NUMBER_STATE_PARSE_EXPONENTA_SIGN;
    }break;
    case ' ': {
        res = false;
    }break;
    case '.':{
    	Node->fraction_order=1;
        Node->state = PARSE_NUMBER_STATE_PARSE_FRACTION;
        res = true;
    } break;
    case '0':
    case '1':
    case '2':
    case '3':
    case '4':
    case '5':
    case '6':
    case '7':
    case '8':
    case '9': {
        uint8_t digit = 0;
        res= try_hex_char_to_u8((uint8_t) Node->cur_letter, &digit) ;
        LOG_PARN(STRING,"ParseInt %u", digit);
        Node->integer *= 10;
        Node->integer += digit;
        Node->spot_mantissa = true;
        res = true;
    }break;

    case '\r':
    case '\n':{
        res = number_compose_result(Node);
    } break;


    default:{
        res = false;
    } break;
    }
    return res;
}


static bool number_proc_parse_exponenta_sign(Text2NumberFsm_t* Node){
    bool res = false;
    switch(Node->cur_letter) {
    case '+': {
        Node->exponent_sign = 1;
        Node->state = PARSE_NUMBER_STATE_PARSE_EXPONENTA_INTEGER;
        res = true;
    }break;

    case '-': {
        Node->exponent_sign = -1;
        res = true;
        Node->state= PARSE_NUMBER_STATE_PARSE_EXPONENTA_INTEGER;
    }        break;

    case '0':{
    	Node->exponent_integer = 0;
    	Node->exponent_sign = 1;
    	Node->spot_exponent = true;
    	Node->state = PARSE_NUMBER_STATE_PARSE_EXPONENTA_INTEGER;
    	res = true;
    }break;
    case '1':
    case '2':
    case '3':
    case '4':
    case '5':
    case '6':
    case '7':
    case '8':
    case '9':{
        uint8_t digit = 0;
        res= try_hex_char_to_u8((uint8_t) Node->cur_letter, &digit) ;
        LOG_PARN(STRING,"ParseExpInt %u",digit);
        Node->exponent_integer *=10;
        Node->spot_exponent = true;
        Node->exponent_integer += digit;
        Node->state= PARSE_NUMBER_STATE_PARSE_EXPONENTA_INTEGER;
        res = true;
    }break;

    case '\r':
    case '\n':{res = false;} break;
    default: res = false; break;
    }
    return res;
}

static bool number_exponenta_calc(Text2NumberFsm_t* Node){
    bool res = false;
    if(Node) {
    	if(Node->spot_exponent ){
            int32_t rank = ((int32_t)Node->exponent_integer) * ((int32_t)Node->exponent_sign);
            LOG_DEBUG(STRING,"ExpRank %d",rank);
            double power = (double )rank;
            LOG_DEBUG(STRING,"power %f",power);
            if(rank < 306) {
                if(-306 < rank) {
                    Node->exponenta = pow(10.0,power);
                    LOG_DEBUG(STRING,"Exponenta: %f",Node->exponenta);
                    res = true;
                } else {
                	Node->exponenta = 0.0;
                    LOG_ERROR(STRING,"MathError:TooSmalExpPower %d",rank);
                    res = false;
                }
            } else {
                LOG_ERROR(STRING,"MathError:TooBigExpPower %d",rank);
                res = false;
            }
    	} else {
    		LOG_ERROR(STRING,"NoExponents");
    	}
    }
    return res ;
}

static bool number_proc_parse_exponenta_integer(Text2NumberFsm_t* Node){
    bool res = false;
    switch(Node->cur_letter) {
    case '0':
    case '1':
    case '2':
    case '3':
    case '4':
    case '5':
    case '6':
    case '7':
    case '8':
    case '9': {
        uint8_t digit = 0;
        res= try_hex_char_to_u8((uint8_t) Node->cur_letter, &digit) ;
        LOG_PARN(STRING,"ParseExpInt %u",digit);
        Node->exponent_integer *=10;
        Node->exponent_integer += digit;
        Node->spot_exponent = true;
        Node->state= PARSE_NUMBER_STATE_PARSE_EXPONENTA_INTEGER;
        res = true;
    }break;

    case '\r':
    case '\n': {
        res = number_exponenta_calc(Node);
        if (res) {
        	if(Node->spot_mantissa) {
                double mantissa = 0.0;
                mantissa =((double)Node->sign)*(((double)Node->integer)+((double)Node->fraction));
                LOG_DEBUG(STRING,"mantissa %f", mantissa);
                Node->value = mantissa*(Node->exponenta);
                Node->state= PARSE_NUMBER_STATE_DONE;
        	}else {
        		LOG_DEBUG(STRING,"NoMantissa");
        		res = false;
        	}
        }
    }break;
    default:
        res = false;
        break;
    }
    return res;
}

bool number_compose_mantissa(Text2NumberFsm_t* Node){
    bool res = false;
    if(Node) {
    	Node->mantissa =((double)Node->sign)*(((double)Node->integer)+((double)Node->fraction));
    	res = true;
    }
    return res;
}

static bool  number_proc_parse_fracion(Text2NumberFsm_t* Node){
    bool res = false;
    switch(Node->cur_letter){
    case 'E':
    case 'e':{
    	res = number_compose_mantissa(Node);
    	Node->state = PARSE_NUMBER_STATE_PARSE_EXPONENTA_SIGN;
    }break;
    case ' ': {
    	LOG_ERROR(STRING,"TornFlowErr!");
    	res = false;
    }break;
    case '.': {
    	LOG_ERROR(STRING,"DoubleDotErr!");
    	res = false;}break;
    case '0':
    case '1':
    case '2':
    case '3':
    case '4':
    case '5':
    case '6':
    case '7':
    case '8':
    case '9': {
        uint8_t digit = 0;
        res = try_hex_char_to_u8((uint8_t) Node->cur_letter, &digit) ;
        double fraction_digit =  (    (double)digit  ) / (   pow(10.0, (double) Node->fraction_order) );
        LOG_DEBUG(STRING,"+ %f",fraction_digit);
        Node->spot_mantissa= true;
        Node->fraction += fraction_digit;

        Node->fraction_order++;
        res = true;
    }break;
    case '-':
    case '+': {res = false;}break;

    case '\r':
    case '\n':{
        res = number_compose_result(Node);
    } break;

    }
    return res;
}

static bool number_proc_done(Text2NumberFsm_t* Node){
    bool res = false;
    LOG_DEBUG(STRING, "Proc: %s",NumberParserFsm2Str(Node));
    switch(Node->cur_letter){
        case '\n':
        case '\r':{
            res = true;
        } break;
        default:{
            res = false;
        }break;
    }
    return res;
}

Я очень рад, что нашел эту задачу на LeetCode (65. Valid Number). Там уже заготовлено очень много тестов. Их сайт просто пытался разбомбить unit тестами моё решение и тем не менее оно выстояло!

Моё решение прошло верификацию на сайте LeetCode и оказалось быстрее всех решений на языке программирования Си!

Если знаете оригинальные тестовые данные для задачи распознавания вещественного числа из строки, то пишите, пожалуйста, их в комментариях.

Вывод

Конечные автоматы идеально подходят для синтаксического разбора (парсинга) разнообразных типов данных из строчек, в частности типа данных double. Если вы научились распознавать тип double, то можно сразу утверждать, что вы этим же кодом научились и распознавать и uint8_t int8_t int32_t, uint64_t, float. Один парсер double является универсальным!

Потом, кода Вы пишите свой парсер double чисел из строки, то Вы можете совершенно спокойно добавить распознавание размерных суффиксов (p ,n, u, m, k, M, G и т. п.). Например строчку "100n" распознать как 100e-9 = 0.0000001. Стандартная функция scanf Вам такое не сделает.

Словарь

Акроним	Расшифровка
DFA	Deterministic finite automaton
CSV	Comma-separated values
NMEA	National Marine Electronics Association
TDD	Test-driven development

Links

https://leetcode.com/problems/valid-number/description/

https://docs.google.com/spreadsheets/d/1rbEw8p8CMHzM5DJUYGxDX-BCQ8sZsp4jDMRsbifJD9k/edit#gid=0

https://www.onlinegdb.com/

Вопросы для обсуждения

--Вам известны примеры практических задач на LeetCode решение которых пригодилось бы в реальных embedded проектах?

Only registered users can participate in poll. Log in, please.

Вам приходилось распознавать вещественные числа из строчек?

72.06% да49

27.94% нет19

68 users voted. 7 users abstained.

Only registered users can participate in poll. Log in, please.

Вы решали задачи с сайта LeetCode?

37.14% да26

62.86% нет44

70 users voted. 2 users abstained.

Tags:

Hubs: