By

看到一道判断数的有效性的问题
Some examples:
“0” => true
“ 0.1 “ => true
“abc” => false
“1 a” => false
“2e10” => true

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

这个题目类似于一个简化版的状态机（state machine）。可以人工画出来状态机。

代码实现的时候，有一个简单的方式，每个函数当作一个状态，参数是接受的字符，返回下一个状态（函数）。
状态机的一个应用，以前看过一篇介绍How browser works,里面说过浏览器建立文档树的时候，
document -> lexical analysis -> syntax analysis -> parse tree
其中词法分析lexical analysis的部分是上下文无关文法(context free grammer),所以可以用有穷状态机来tokenize。

本题的状态机：

state machine

普通实现：

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
var isNumber = function(s) {
    s = s.trim();
	var state = 0;
	for (var i=0; i<s.length; i++)
	{
		var c = s[i];
		if (state === 0)
		{
			if (c === '+' || c === '-')
			{
				state = 1;
			}
			else if (c >= '0' && c <= '9')
			{
				state = 2;
			}
			else if (c === '.')
			{
				state = 6;
			}
			else
			{
				return false;
			}
		}
		else if (state === 1)
		{
			if (c >= '0' && c <= '9')
			{
				state = 2;
			}
			else if (c === '.')
			{
				state = 6;
			}
			else
			{
				return false;
			}
		}
		else if (state === 2)
		{
			while (i < s.length && c >= '0' && c <= '9')
			{
				i++;
				c = s[i];
			}
			
			if (i === s.length)
			{
				break;
			}
			
			if (c === '.')
			{
				state = 3;
			}
			else if (c === 'e' || c === 'E')
			{
				state = 4;
			}
			else
			{
				return false;
			}
		}
		else if (state === 3)
		{
			while (i < s.length && c >= '0' && c <= '9')
			{
				i++;
				c = s[i];
			}
			
			if (i === s.length)
			{
				break;
			}
			
			if (c === 'e' || c === 'E')
			{
				state = 4;
			}
			else
			{
				return false;
			}
		}
		else if (state === 4)
		{
			if (c >= '0' && c <= '9')
			{
				state = 5;
			}
			else if (c === '+' || c === '-')
			{
				state = 7;
			}
			else
			{
				return false;
			}
		}
		else if (state === 5)
		{
			while (i < s.length && c >= '0' && c <= '9')
			{
				i++;
				c = s[i];
			}
			
			if (i === s.length)
			{
				break;
			}
			else
			{
				return false;
			}
		}
		else if (state === 6)
		{
			if (c >= '0' && c <= '9')
			{
				state = 3;
			}
			else
			{
				return false;
			}
		}
		else if (state === 7)
		{
			if (c >= '0' && c <= '9')
			{
				state = 5;
			}
			else
			{
				return false;
			}
		}
	}
	
	return state === 2 || state ===3 || state === 5;
};

更清晰的代码结构：

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
var isNumber = function(s) {
    s = s.trim();
	return S0(s, 0);
};

var S0 = function(s, index)
{
	if (index === s.length)
	{
		return false;
	}
	
	var char = s[index];
	if (char === '+' || char === '-')
	{
		return S1(s, index + 1);
	}
	else if (char >= '0' && char <= '9')
	{
		return S2(s, index + 1);
	}
	else if (char === '.')
	{
		return S6(s, index + 1);
	}
	
	return false;
}

var S1 = function(s, index)
{
	if (index === s.length)
	{
		return false;
	}
	
	var char = s[index];
	if (char >= '0' && char <= '9')
	{
		return S2(s, index + 1);
	}
	else if (char === '.')
	{
		return S6(s, index + 1);
	}
	
	return false;
}

var S2 = function(s, index)
{
	while (index < s.length && s[index] >= '0' && s[index] <= '9')
	{
		index ++;
	}
	
	if (index === s.length)
	{
		return true;
	}
	
	var char = s[index];
	if (char === '.')
	{
		return S3(s, index + 1);
	}
	else if (char === 'e' || char === 'E')
	{
		return S4(s, index + 1);
	}
	
	return false;
}

var S3 = function(s, index)
{
	while (index < s.length && s[index] >= '0' && s[index] <= '9')
	{
		index ++;
	}
	
	if (index === s.length)
	{
		return true;
	}
	
	var char = s[index];
	if (char === 'e' || char === 'E')
	{
		return S4(s, index + 1);
	}
	
	return false;
}

var S4 = function(s, index)
{
	if (index === s.length)
	{
		return false;
	}
	
	var char = s[index];
	if (char >= '0' && char <= '9')
	{
		return S5(s, index + 1);
	}
	else if (char === '+' || char === '-')
	{
		return S7(s, index + 1);
	}
	
	return false;
}

var S5 = function(s, index)
{
	while (index < s.length && s[index] >= '0' && s[index] <= '9')
	{
		index ++;
	}
	
	if (index === s.length)
	{
		return true;
	}
		
	return false;
}

var S6 = function(s, index)
{
	if (index === s.length)
	{
		return false;
	}
	
	var char = s[index];
	if (char >= '0' && char <= '9')
	{
		return S3(s, index + 1);
	}
	
	return false;
}

var S7 = function(s, index)
{
	if (index === s.length)
	{
		return false;
	}
	
	var char = s[index];
	if (char >= '0' && char <= '9')
	{
		return S5(s, index + 1);
	}
	
	return false;
}