|
|
确定有限状态自动机（以下简称「自动机」）是一类计算模型。它包含一系列状态，这些状态中：
有一个特殊的状态，被称作「初始状态」。
还有一系列状态被称为「接受状态」，它们组成了一个特殊的集合。其中，一个状态可能既是「初始状态」，也是「接受状态」。
起初，这个自动机处于「初始状态」。随后，它顺序地读取字符串中的每一个字符，并根据当前状态和读入的字符，按照某个事先约定好的「转移规则」，从当前状态转移到下一个状态；当状态转移完成后，它就读取下一个字符。当字符串全部读取完毕后，如果自动机处于某个「接受状态」，则判定该字符串「被接受」；否则，判定该字符串「被拒绝」。
注意：如果输入的过程中某一步转移失败了，即不存在对应的「转移规则」，此时计算将提前中止。在这种情况下我们也判定该字符串「被拒绝」。
此题有很多种情况，如果我们一一列举那么很容易出现漏掉的情况，所以我们采用状态机解决，从最左边的字符开始，每次遍历一个字符视为输入一种激励，使得他转移到另外一种状态，或者理解成为一个新的字符，那么最后我们只要规定有几种特殊的状态才能结束状态跳出状态机，即特殊的字符，也就是字符为数值时，才可以跳出状态机。
首先画出状态图：
字符类型：
空格 「 」、数字「 0—9 」 、正负号 「 ± 」 、小数点 「 . 」 、幂符号 「 eE 」 。（也称为激励类型）
所有状态定义：
1.起始的空格
2.符号位
3.整数部分
4.左侧有整数的小数点
5.左侧无整数的小数点（根据前面的第二条额外规则，需要对左侧有无整数的两种小数点做区分）
6.小数部分
7.字符 e和E
8.指数部分的符号位
9.指数部分的整数部分
10.末尾的空格
合法的结束状态有：3,4,6,9,10
设 tranfer[i] ，其中 i 为所处状态，tranfer[i] 使用哈希表存储可转移至的状态。键值对 (key, value)含义：若输入key ，则可从状态 i转移至状态value 。
state_blank,{typ_blank,state_blank}表示当前状态为state_blank，然后输入一个激励typ_blank，blank表示空格，状态转移至state_blank空格状态
#include <iostream>
#include<unordered_map>
using namespace std;
class Solution {
public:
enum state {
state_blank,
state_sign,
state_integer,
state_point_without_int,
state_point_with_int,
state_fraction,
state_exp,
state_exp_sign,
state_exp_int,
state_end_blank,
};
enum inputtyp {
typ_int,
typ_point,
typ_blank,
typ_exp,
typ_sign,
typ_illegal
};
inputtyp input(char ch) {
if (ch <= '9' && ch >= '0')return typ_int;
else if (ch == '.') return typ_point;
else if (ch == ' ') return typ_blank;
else if (ch == 'e' || ch == 'E') return typ_exp;
else if (ch == '+' || ch == '-') return typ_sign;
else return typ_illegal;
}
bool isNumber(string s) {
unordered_map<state, unordered_map<inputtyp, state>> tranfer{
{
state_blank,{
{typ_blank,state_blank},
{typ_int,state_integer},
{typ_point,state_point_without_int},
{typ_sign,state_sign}}
},
{
state_sign,{
{typ_point,state_point_without_int},
{typ_int,state_integer},
}
},
{
state_integer,{
{typ_int,state_integer},
{typ_point,state_point_with_int},
{typ_exp,state_exp},
{typ_blank,state_end_blank},
}
},
{
state_point_without_int,{
{typ_int,state_fraction},
}
},
{
state_point_with_int,{
{typ_int,state_fraction},
{typ_blank,state_end_blank},
{typ_exp,state_exp},
}
},
{
state_fraction,{
{typ_int,state_fraction},
{typ_exp,state_exp},
{typ_blank,state_end_blank},
}
},
{
state_exp,{
{typ_int,state_exp_int},
{typ_sign,state_exp_sign},
}
},
{
state_exp_sign,{
{typ_int,state_exp_int},
}
},
{
state_exp_int,{
{typ_int,state_exp_int},
{typ_blank,state_end_blank},
}
},
{
state_end_blank,{
{typ_blank,state_end_blank},
}
}
};
state start = state_blank;
for (int i = 0; i < s.size(); i++) {
inputtyp typ = input(s[i]);
if (tranfer[start].find(typ) == tranfer[start].end())
return false;
else
start = tranfer[start][typ];
}
return start == state_integer || start == state_point_with_int || start == state_fraction || start == state_exp_int || start == state_end_blank;
}
};
int main()
{
Solution* x = new Solution;
string s = "5e0";
cout << x->isNumber(s);
}
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
class Solution {
public boolean isNumber(String s) {
int idx=-1;
char []cs=s.toCharArray();
int low =0 ,high=cs.length-1;
while(low<=high&&cs[low]==' ') low++;
while(low<=high&&cs[high]==' ') high--;
for(int i=low;i<=high;i++){
if(cs[i]=='e'||cs[i]=='E'){
if(idx==-1)idx=i;
else return false;
}
}
boolean res=true;
if(idx==-1){
res &=judge(cs,low,high,false);
}
else{
res &=judge(cs,low,idx-1,false);
res &=judge(cs,idx+1,high,true);
}
return res;
}
public boolean judge(char []cs,int start,int end,boolean mustbeint){
if(start>end)return false;
if(cs[start]=='+'||cs[start]=='-')start++;
boolean haspot=false,isnum=false;
for(int i=start;i<=end;i++){
if(cs[i]=='.'){
if(haspot|| mustbeint)return false;
haspot=true;
}
else if(cs[i]>='0'&&cs[i]<='9'){
isnum=true;
}
else return false;
}
return isnum;
}
}
[code]原文链接：https://blog.csdn.net/qq_41884662/article/details/115314821[/code] |
|
发表于 2024-6-22 09:46:18
