一个有限状态机判断字符串是否数字的例子

106 阅读 0 评论 70 点赞

我是靠谱客的博主愉快大树，这篇文章主要介绍一个有限状态机判断字符串是否数字的例子，现在分享给大家，希望可以做个参考。

这几天看到有朋友在讨论这样的问题，如何快速匹给定的字符串是一个有效的科学记数法表示的数字。

如“ -1.2e-3 ”就是一个有效的数字（注意其中的空格）。

一个符合科学记数法的字符串可以包含如下字符：符号（+、-）、数字（1~9）、小数点（.)、指数（e)、以及空格。

常规方法使用分支结构进行逻辑判断的问题在于其判断的逻辑树过于复杂。而且如果需要加入新的规则，成堆的if——else无法顺利的更新与维护。

此时可考虑使用状态机来解决该问题。

为了简化，下面不考虑指数e和小数点的情况，以整数（只有符号、空格、数字位）为例，该状态机不难画出：

注意该状态机的如下状态：

[0]开始状态：只能接受空格、符号、数字；

[1]符号状态：只能接受符号；

[2]数字状态：只能接受空格、数字、结束；

[3]空格状态：只能接受空格、结束；

注意2个空格的区别。左边的空格表示第一个字符开始为空格，右边的表示中间或者后面出现的空格。二者状态不同。

这样的状态机实际上是一个有向图。可以使用矩阵来实现状态机。如下图，每行表示一个状态，每列表示一个输入条件。T表示字符串为数字；F表示不是数字。

例如，“ -1 “（首字母、末字母为空格）在该状态机中的判断路径为：0B-->0C-->1D-->2B-->3F-->T,如上图红色线条所示。

知道状态机的原理与实现，现在就可以回到开头的问题来完整解决判断字符串是否科学记数法表示的问题了。

科学记数法相比整数而言，多了不少状态。比如：

小数点（出现于数字前）的状态。如已经输入了"."，此时后面必须接数字，不能接收其他输入。

小数点（出现于数字后）的状态。如已经输入了"5."，此时后面可以不接数字，表示省略0。

数字（出现于小数点前）的状态。如已经输入了"5"，此时后面可以接小数点。

数字（出现于小数点后）的状态。如已经输入了".5"，此时后面可以不可接小数点。

数字（出现于e前）的状态。如已经输入了"5"，此时后面可以接e。

数字（出现于e后）的状态。如已经输入了"e5"，此时后面不可接e。

......

状态机并不唯一，主要取决于你如何将所有状态都囊括进去。

状态机很复杂，这里就不画了，最终代码如下，状态机的实现请看代码：

复制代码

enum enum_Status
    {
        Blank   = 0,
        Signal  = 1,
        Dot     = 2,
        Epsinal = 3,
        Number  = 4,
        Alphabet= 5,
        End     = 6,

T       = 98,
        F       = 99
    };
    enum_Status GetStatus(char c)
    {
        if (c >= '0' && c <= '9')
        {
            return Number;
        }
        else if (c == ' ')
        {
            return Blank;
        }
        else if (c == '+' || c == '-')
        {
            return Signal;
        }
        else if (c == '.')
        {
            return Dot;
        }
        else if (c == 'e')
        {
            return Epsinal;
        }
        else if (c == '')
        {
            return End;
        }
        else
        {
            return Alphabet;
        }
    }

bool isNumber(const char *s) 
    {    
        int statusTable[10][7] = {
           //   +  .  e  0  a  end
            {0, 1, 2, F, 8, F, F},// 0: Begin
            {F, F, 2, F, 8, F, F},// 1: Signal
            {F, F, F, F, 9, F, F},// 2: Dot [before number]
            {7, F, 4, 5, 3, F, T},// 3: number[before e]
            {7, F, F, 5, 9, F, T},// 4: Dot [after number]
            {F, 1, F, F, 6, F, F},// 5: e
            {7, F, F, F, 6, F, T},// 6: number[after e]
            {7, F, F, F, F, F, T},// 7: Blank
            {7, F, 4, 5, 8, F, T},// 8: number[before dot]
            {7, F, F, 5, 9, F, T},// 9: number[after dot]
        };
        const char *p = s;
        int status = statusTable[0][GetStatus(*p)];

while (status != (int)T && status != (int)F)
        {
            ++p;
            status = statusTable[status][GetStatus(*p)];
        }
        return (status == T);
    }

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
enum enum_Status
    {
        Blank   = 0,
        Signal  = 1,
        Dot     = 2,
        Epsinal = 3,
        Number  = 4,
        Alphabet= 5,
        End     = 6,

        T       = 98,
        F       = 99
    };
    enum_Status GetStatus(char c)
    {
        if (c >= '0' && c <= '9')
        {
            return Number;
        }
        else if (c == ' ')
        {
            return Blank;
        }
        else if (c == '+' || c == '-')
        {
            return Signal;
        }
        else if (c == '.')
        {
            return Dot;
        }
        else if (c == 'e')
        {
            return Epsinal;
        }
        else if (c == '')
        {
            return End;
        }
        else
        {
            return Alphabet;
        }
    }

    bool isNumber(const char *s) 
    {    
        int statusTable[10][7] = {
           //   +  .  e  0  a  end
            {0, 1, 2, F, 8, F, F},// 0: Begin
            {F, F, 2, F, 8, F, F},// 1: Signal
            {F, F, F, F, 9, F, F},// 2: Dot [before number]
            {7, F, 4, 5, 3, F, T},// 3: number[before e]
            {7, F, F, 5, 9, F, T},// 4: Dot [after number]
            {F, 1, F, F, 6, F, F},// 5: e
            {7, F, F, F, 6, F, T},// 6: number[after e]
            {7, F, F, F, F, F, T},// 7: Blank
            {7, F, 4, 5, 8, F, T},// 8: number[before dot]
            {7, F, F, 5, 9, F, T},// 9: number[after dot]
        };
        const char *p = s;
        int status = statusTable[0][GetStatus(*p)];

        while (status != (int)T && status != (int)F)
        {
            ++p;
            status = statusTable[status][GetStatus(*p)];
        }
        return (status == T);
    }