侧边栏壁纸
  • 累计撰写 781 篇文章
  • 累计创建 1 个标签
  • 累计收到 1 条评论
标签搜索

有限状态机

Dettan
2021-04-10 / 0 评论 / 0 点赞 / 102 阅读 / 2,434 字
温馨提示:
本文最后更新于 2022-04-30,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

有限状态机分为 确定有限状态机和不确定有限状态机。它们只有一个区别:
在一个状态下,输入一个符号,是否会有不同的结果。例如(abc|aef) 在起始状态下,输入a会有两种不同结果,NFA会回溯,所以性能低一点。
NFA : 直观 , 好实现
DFA : 性能高
NFA 和 DFA 可以转换
正则表达式用的NFA
问题
验证给定的字符串是否可以解释为十进制数字。
例如:
"0" => true " 0.1 " => true "abc" => false "1 a" => false "2e10" => true " -90e3 " => true " 1e" => false "e3" => false " 6e-1" => true " 99e2.5 " => false "53.5e93" => true " --6 " => false "-+3" => false "95a54e53" => false
说明: 我们有意将问题陈述地比较模糊。在实现代码之前,你应当事先思考所有可能的情况。这里给出一份可能存在于有效十进制数字中的字符列表:
数字 0-9 指数 - "e" 正/负号 - "+"/"-" 小数点 - "." 当然,在输入中,这些字符的上下文也很重要。
链接:https://leetcode-cn.com/problems/valid-number
正则 ' *[+-]? ([0-9]+(\.[0-9]*)?|\.[0-9]+) (e[+-]?[0-9]+)? *$'
return bool(re.match(r' *[+-]?([0-9]*+(\.[0-9])?|\.[0-9]+)(e[+-]?[0-9]+)? *$', s))

本题可以采用《编译原理》里面的确定的有限状态机(DFA)解决。构造一个DFA并实现,构造方法可以先写正则表达式,然后转为 DFA,也可以直接写,我就是直接写的,虽然大概率不会是最简结构(具体请参考《编译器原理》图灵出版社),不过不影响解题。DFA 作为确定的有限状态机,比 NFA 更加实用,因为对于每一个状态接收的下一个字符,DFA 能确定唯一一条转换路径,所以使用简单的表驱动的一些方法就可以实现,并且只需要读一遍输入流,比起 NFA 需要回读在速度上会有所提升。
构建出来的状态机如封面图片所示(红色为 终止状态,蓝色为 中间状态)。根据《编译原理》的解释,DFA 从状态 0 接受串 s 作为输入。当s耗尽的时候如果当前状态处于中间状态,则拒绝;如果到达终止状态,则接受。
然后,根据 DFA 列出如下的状态跳转表,之后我们就可以采用 表驱动法 进行编程实现了。需要注意的是,这里面多了一个状态 8,是用于处理串后面的若干个多余空格的。所以,所有的终止态都要跟上一个状态 8。其中,有一些状态标识为-1,是表示遇到了一些意外的字符,可以直接停止后续的计算。状态跳转表如下:
最繁列举
1.
+8.8e-1
2.
+.8
3.
+8.

图里的数字和本文不对应!
红色是终止状态,达到这个状态的都是正确的。

所有可能的状态
2.
空格
3.
空格+正负号
4.
空格+正负号+数
5.
空格+正负号+.
6.
空格+正负号+数+.+数 和数+.合并了,一样
7.
空格+正负号+数+.+数+e
8.
空格+正负号+数+.+数+e+正负号
9.
空格+正负号+数+.+数+e+正负号+数
10.
空格+正负号+数+.+数+e+正负号+数+空格


-1 表示出错。
所有输入类型
2.
空格
3.
+-
4.
0-9
5.
.
6.
eE
7.
非法

class Solution {
    enum InputType { space, sign, digit, dot, exponent,invilid}
    public boolean isNumber(String s) {
       short[][] ss = new short[][]{
                {0, 1, 2, 3, -1, -1},
                {-1, -1, 2, 3, -1, -1},
                {8, -1, 2, 4, 5, -1},
                {-1, -1, 4, -1, -1, -1},
                {8, -1, 4, -1, 5, -1},
                {-1, 6, 7, -1, -1, -1},
                {-1, -1, 7, -1, -1, -1},
                {8, -1, 7, -1, -1, -1},
                {8, -1, -1, -1, -1, -1}
        };
    short state = 0;
    InputType inputType;
    for (short i = 0; i < s.length(); i++) {
        char v = s.charAt(i);
        switch (v) {
            case ' ':
                inputType = InputType.space;
                break;
            case '.':
                inputType = InputType.dot;
                break;
            case '+':
            case '-':
                inputType = InputType.sign;
                break;
            case 'e':
            case 'E':
                inputType = InputType.exponent;
                break;
            case '0':
            case '1':
            case '2':
            case '3':
            case '4':
            case '5':
            case '6':
            case '7':
            case '8':
            case '9':
                inputType = InputType.digit;
                break;
            default:
                inputType = InputType.invilid;
                break;
        }
        if ((state = ss[state][inputType.ordinal()]) == -1)
            return false;
    }
    return state == 2 || state == 4 || state == 7 || state == 8;
}

}

0

评论区