有效数字—状态机

发布: 分类: 评论次数： 阅读次数： 本文字数： 2.1k

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

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

不说烦心事了，说点开心的，额，，今天刚打完一天工，又有小钱可以拿了，算嘛？不算的话，今天把部分作业搞完了？错！今天我又一次在不知觉中将自己的闹钟给关了（绝对定了的）！！这才是大事（本来是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

结束

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