剑指53-表示数值的字符串

Posted on | In |

题目描述

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。

模式匹配

Python语言关于字符串是否是数值的判断（float(str)），有如下规则：

  • e和E大小写不敏感，e后面必须是任意整数，e前面必须有个任意整数或浮点数。如e2非法，1e2.6非法。
  • 整型数的第一个数字位，如果不是各位，不能为0。如03非法，0合法。然而012e01合法，
  • .1合法

然后查看官方教程，觉得要求不像python的float方法那么完善。具体的，

  • 没有这一条要求：整型数的第一个数字位，如果不是个位，不能为0。如03非法，0合法。然而012e01合法，
  • 没有考虑字符串中有空格的情形

这就简单很多了。表示数值的字符串遵循如下模式：

1
[sign]integeral-digits[.[fractional-digits]][eE[sign]exponential-digits]

那么，一路按上述模式进行匹配就行了。不在分析线上的，或者在分析线上就有问题的，就是不符合标准的。

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
class Solution:
    # s字符串
    def isNumeric(self, s):
        lens = len(s)
        
        if lens == 0: #空字符串直接返回False
            return False
        
        idx = 0 # 首位是符号位
        if s[0] in '+-':
            if lens == 1:
                return False
            idx += 1
    
        while idx < lens: # 往下走到遇到小数点或者E
            if s[idx] in '0123456789':
                idx += 1
            else:
                break          
        if idx == lens:
            return True
        
        if s[idx] == '.': # 小数点及之后，知道遇到E
            idx += 1
            while idx < lens:
                if s[idx] in '0123456789':
                    idx += 1
                else:
                    break
            if idx == lens:
                return True

                
        if s[idx] in 'eE': # 检查E
            idx += 1
            if idx < lens:
                if s[idx] in '+-':
                    idx += 1
            if idx == lens:
                return False
            while idx < lens:
                if s[idx] in '0123456789':
                    idx += 1
                else:
                    break
            if idx == lens:
                return True
            else:
                return False
        
        return False # 不在上述分析线上的，返回False

有限状态机

有七个状态：

  • state_0: 开始。
  • state_1: 已有正负号。
  • state_2: 已有数字。
  • state_3：已有小数点。
  • state_4：已有e
  • state_5：已有e和正负号
  • state_6: 已有e和[正负号]和数字

可以得到状态切换矩阵：

正负号 数字 小数点 E 结束
state_0 1 2 3 F F
state_1 F 2 3 F F
state_2 F 2 3 4 T
state_3 F 3 F 4 T
state_4 5 6 F F F
state_5 F 6 F F F
state_6 F 6 F F 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
class Solution:
    # s字符串
    def isNumeric(self, s):
        F, T = False, True
        tx = [
            [1, 2, 3, F, F],
            [F, 2, 3, F, F],
            [F, 2, 3, 4, T],
            [F, 3, F, 4, T],
            [5, 6, F, F, F],
            [F, 6, F, F, F],
            [F, 6, F, F, T]
        ]
        state = 0
        for c in s:
            if c in '+-':
                state = tx[state][0]
            elif c in '0123456789':
                state = tx[state][1]
            elif c in '.':
                state = tx[state][2]
            elif c in 'eE':
                state = tx[state][3]
            else:
                return False
            if state == False:
                return False
        if state in [0, 1, 4, 5]:
            return False
        else:
            return True