有效数字—状态机

不得不说,上海这几天的天气是真的有毒,时不时超级冷,还时不时下几滴雨,烦得很。最近临近期末,还有好多大作业啦,项目啦,小作业啦,各种实验啦,烦得不要不要的,整的我连看番的时间都快没了(⁎⁍̴̛ᴗ⁍̴̛⁎)~

今天呢,本科母校竟然又因为这种奇葩原因久居热搜,真的是服了网友们的“奇思妙想”,这迫击炮逮谁轰谁啊?又是烦心事 》**《

不说烦心事了,说点开心的,额,,今天刚打完一天工,又有小钱可以拿了,算嘛?不算的话,今天把部分作业搞完了?错!今天我又一次在不知觉中将自己的闹钟给关了(绝对定了的)!!这才是大事(本来是7.25的闹钟,8.30开工,结果,一觉睡醒8.30了,呵呵~)

今天呢,要讲的是昨天做的一道题,蛮有意思的,竟然和我本科学的编译原理扯上关系了,害我还去看了会本科知识(因为我本科编译原理学的贼差)

题目介绍

有效数字(按顺序)可以分成以下几个部分:

  1. 一个 小数 或者 整数
  2. (可选)一个 ‘e’ 或 ‘E’ ,后面跟着一个 整数

小数(按顺序)可以分成以下几个部分:

  1. (可选)一个符号字符(’+’ 或 ‘-‘)

  2. 下述格式之一:

    1. 至少一位数字,后面跟着一个点 ‘.’

    2. 至少一位数字,后面跟着一个点 ‘.’ ,后面再跟着至少一位数字

    3. 一个点 ‘.’ ,后面跟着至少一位数字

整数(按顺序)可以分成以下几个部分:

  1. (可选)一个符号字符(’+’ 或 ‘-‘)
  2. 至少一位数字

我的思路

其实我的思路比较直接,相信我一说大家也都能懂

这道题无非就是给定有效数字的模式,需要我们自己去比对,因此我们可以按照以下几个步骤对给定的字符串s作出判断

  • 首先判断s中是否包含非法字符,合法字符包括:0-9,+-号,小数点,E与e,其余的字符都可被认定为非法字符

  • 接着判断s中是否包含E或者e,如果E或e的数量超过1,直接false,否则,借助E或e,将s划分,如果划分后,只有一个字符串,则只可能是E或e在结尾,返回false

  • 划分后,判断前一个字符串是否为小数或者整数,判断后一个字符串是否为整数,如果都是,则true,反之,false

  • 如果没有E或者e,则直接判断s是否为整数或者小数

相信明眼人已经看清重点在哪了,没错,关键在于如何判断一个字符串是否为整数或者小数呢?

整数判断:

首先判断开头是否为+或-,是的话,直接从第二位判断,不是的话直接从第一位判断,判断方式很直接,只要每一位字符都是0-9就可以。当然开始需要对s的length做出判断,如果长度为0肯定就直接false啦,如果只有一个+或-号自然也是false,代码如下,其中map是一个key为0-9,value为0的哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private Boolean isInteger(String s, Map<Character,Integer> map){
if(s.length() == 0){
return false;
}else if(s.length() == 1 && (s.charAt(0) == '+' || s.charAt(0) == '-')){
return false;
}
for(int i=0;i<s.length();i++){
if((s.charAt(i) == '+' || s.charAt(i) == '-') && i == 0){
continue;
}else if(!map.containsKey(s.charAt(i))){
return false;
}
}
return true;
}

小数判断:

小数判断相对而言较为麻烦点,因为存在可能性会稍微有点多,相信大家对小数都很熟悉,我们以小数点为界,将字符串分为两部分,一般而言,只要前后两部分都是整数就是一个小数,不过这里需要做出一些额外的判断

  • 小数点个数大于1直接false

  • 分割后如果没有字符串,直接false(表示原本就一个小数点)

  • 分割后如果只有一个字符串,表示小数点只能在结尾,这时,只需要判断分割后的那个字符串是否为整数即可(原因是split时,如果分割符在开头,则第一个分割出来的字符串是空串””)

  • 如果是正常的两个字符串,也有多种情况:

    • 第一个字符串:

      • 第一个字符串是空串

      • 第一个字符串是整数

      • 第一个字符串是+或-

    • 第二个字符串:

      • 第二个字符串是整数,并且第一个字符不是+或-号
  • 满足上述情况的两个字符串即可返回true,其余直接false

具体代码如下:

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
private Boolean isFloat(String s, Map<Character,Integer> map){
if(s.length() == 0){
return false;
}
int index = 0;
int count = 0;
for(int i=0;i<s.length();i++){
if(s.charAt(i) == '.'){
count++;
index = i;
}
if(count > 1){
return false;
}
}
String[] temp = s.split("\\.");
if(temp.length == 0){
return false;
}else if(temp.length == 1){
return isInteger(temp[0],map);
}else{
if((isInteger(temp[0],map) || temp[0].length() == 0 || (temp[0].length() == 1 && (temp[0].charAt(0) == '+' || temp[0].charAt(0) == '-'))) && (isInteger(temp[1],map) && temp[1].charAt(0) != '+' && temp[1].charAt(0) != '-')){
return true;
}else{
return false;
}
}
}

好思路

利用有限状态自动机来进行解题,这是一种比较好的思路,具体的实现如下:

首先,我们需要根据题目的含义,将有效数字的所有可能性,以状态转换图的形式画出来,便于得到后续的状态转换表:

我相信各位大佬的理解能力应该都很强,关于这个图我就不细讲了,毕竟确实很容易理解(就是自己来画,蛮难的,编译原理没学好~)

额,要真的需要解释下的话,其实也没啥解释的,不就是一开始是个空的串,可以加入0-9数字,也可以一开始加入+或-号,其实就是构造一个有效数字的路径图

根据状态转换图可以得出下表:

state blank +/- 0-9 . e/E other
0 0 1 6 2 -1 -1
1 -1 -1 6 2 -1 -1
2 -1 -1 3 -1 -1 -1
3 -1 -1 3 -1 4 -1
4 -1 7 5 -1 -1 -1
5 -1 -1 5 -1 -1 -1
6 -1 -1 6 3 4 -1
7 -1 -1 5 -1 -1 -1
8 8 -1 -1 -1 -1 -1

其中,状态8是用来处理字符串s结尾多余的的空格,因此所有终止态都必须跟上一个状态8,部分值为-1表示遇到一些不合法的字符(就是前面说的那些),直接返回false

具体代码如下:

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
class Solution {
public int make(char c) {
switch(c) {
case ' ': return 0;
case '+':
case '-': return 1;
case '.': return 3;
case 'e': return 4;
default:
if(c >= 48 && c <= 57) return 2;
}
return -1;
}

public boolean isNumber(String s) {
int state = 0;
int finals = 0b101101000;
int[][] transfer = new int[][]{{ 0, 1, 6, 2,-1},
{-1,-1, 6, 2,-1},
{-1,-1, 3,-1,-1},
{ 8,-1, 3,-1, 4},
{-1, 7, 5,-1,-1},
{ 8,-1, 5,-1,-1},
{ 8,-1, 6, 3, 4},
{-1,-1, 5,-1,-1},
{ 8,-1,-1,-1,-1}};
char[] ss = s.toCharArray();
for(int i=0; i < ss.length; ++i) {
int id = make(ss[i]);
if (id < 0) return false;
state = transfer[state][id];
if (state < 0) return false;
}
return (finals & (1 << state)) > 0;
}
}

注意:final的取值是有意义的,在上面的状态转换图中,我们可以得知:状态3,5,6,8可以作为正常的终止态,因此可以通过位操作来判断最终的状态是否在这几个选择中。具体上来说:final的值与1左移3位,1左移5位,1左移6位,1左移8位得到的是3,5,6,8;而其他的状态值与操作后都是0

结束

以上便是这道题的全部内容啦!给我留下印象最深的就是有限状态机在算法中竟然还可以这么使用,学到了~