65_有效数字

难度：困难

题目

有效数字（按顺序）可以分成以下几个部分：

  1. 一个 小数 或者 整数
  2. （可选）一个 'e' 或 'E' ，后面跟着一个 整数

小数（按顺序）可以分成以下几个部分：

  1. （可选）一个符号字符（'+' 或 '-'）
  2. 下述格式之一：
    • 至少一位数字，后面跟着一个点 '.'
    • 至少一位数字，后面跟着一个点 '.' ，后面再跟着至少一位数字
    • 一个点 '.' ，后面跟着至少一位数字

整数（按顺序）可以分成以下几个部分：

  1. （可选）一个符号字符（'+' 或 '-'）
  2. 至少一位数字

部分有效数字列举如下：

  • ["2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789"]

部分无效数字列举如下：

  • ["abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53"]

给你一个字符串 s ，如果 s 是一个 有效数字 ，请返回 true 。

示例

示例一：

输入：s = “0”
输出：true

示例二：

输入：s = “e”
输出：false

示例三：

输入：s = “.”
输出：false

示例四：

输入：s = “.1”
输出：true

提示

  • 1 <= s.length <= 20
  • s 仅含英文字母（大写和小写），数字（0-9），加号 '+' ，减号 '-' ，或者点 '.' 。

解题

确定有限状态自动机

确定有限状态自动机（以下简称「自动机」）是一类计算模型。它包含一系列状态，这些状态中：

  • 有一个特殊的状态，被称作「初始状态」。
  • 还有一系列状态被称为「接受状态」，它们组成了一个特殊的集合。其中，一个状态可能既是「初始状态」，也是「接受状态」。

起初，这个自动机处于「初始状态」。随后，它顺序地读取字符串中的每一个字符，并根据当前状态和读入的字符，按照某个事先约定好的「转移规则」，从当前状态转移到下一个状态；当状态转移完成后，它就读取下一个字符。当字符串全部读取完毕后，如果自动机处于某个「接受状态」，则判定该字符串「被接受」；否则，判定该字符串「被拒绝」。

并且如果没有匹配到转移规则，也拒绝该字符串。

自动机驱动的编程，可以看成是一种暴力解法。

合法数值字符串

一个合法的数值字符串，包含以下部分：

  • 符号位，即 +、−两种符号
  • 整数部分，即由若干字符 0−9 组成的字符串
  • 小数点
  • 小数部分，其构成与整数部分相同
  • 指数部分，其中包含开头的字符 e（大写小写均可）、可选的符号位，和整数部分

上面五个部分每个都不是必需的，但是受一些额外规则制约：

  • 如果符号位存在，其后面必须跟着数字或者小数点
  • 小数点的前后两侧，至少有一侧是数字

自动机状态转换

根据这些规则，罗列出自动机的所有状态：

  1. 初始状态
  2. 符号位
  3. 整数部分
  4. 左侧有整数的小数点
  5. 左侧无整数的小数点
  6. 小数部分
  7. 字符 e
  8. 指数部分的符号位
  9. 指数部分的整数部分

fig1

初始状态即状态0，接受状态为状态2、状态3、状态5、状态8。

  • 当输入正负号时：
    • 如果当前状态是初始状态0，则状态切换为1
    • 如果当前状态是状态6，则切换到状态7
    • 其他则拒绝
  • 当输入数字时：
    • 如果当前状态是状态0，1，2，则切换到状态2
    • 如果当前状态是状态3，4，5，则切换到状态5
    • 如果当前状态是状态6，7，8，则切换到状态8
  • 当输入小数点时：
    • 如果当前状态是状态0，1，则切换到状态4
    • 如果当前状态是状态2，则切换到状态3
    • 其他则拒绝
  • 当输入字符 E | e 时：
    • 如果当前状态是 2，3，5，则切换到状态6
    • 其他则拒绝
  • 其他字符：
    • 拒绝 
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
public static boolean isNumber(String s){
  int state = 0;
  s = s.trim(); // 去除头尾空格
  // 遍历所有字符，当作输入
  for (int i=0; i<s.length(); i++){
    switch (s.charAt(i)) {
        // 正负号
      case '+':
      case '-':
        if (state == 0){
          state = 1;
        }else if (state ==6){
          state = 7;
        }else {
          return false;
        }
        break;
        // 数字
      case '0':
      case '1':
      case '2':
      case '3':
      case '4':
      case '5':
      case '6':
      case '7':
      case '8':
      case '9':
        if (state==0||state==1||state==2){
          state = 2;
        }else if (state==3||state==4||state==5){
          state = 5;
        }else if (state==6||state==7||state==8){
          state = 8;
        }else {
          return false;
        }
        break;
        // 小数点
      case '.':
        if (state==0||state==1){
          state = 4;
        }else if (state==2){
          state = 3;
        }else {
          return false;
        }
        break;
        // E e
      case 'E':
      case 'e':
        if (state==2||state==3||state==5){
          state=6;
        }else {
          return false;
        }
        break;
      default:
        return false;
    }
  }
  // 返回接受状态
  return state==2||state==3||state==5||state==8;
}