状态机

Posted on | Edited on | In ,

最近刷题lc8写一个string–>int的函数，结题思路是用限自动机的方案

  1. 穷举有几种数字状态“ ”,”+/-“,”0-9”,”其他字符”，对应的 start、signin_number、end
  2. 穷举每种状态之间转化关系
  3. 遇到每种字符后，处理每种状态的逻辑

源码如下：

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
public class Solution {

    public static void main(String[] args) {
        System.out.println(Integer.MAX_VALUE);
        System.out.println(Integer.MIN_VALUE);
        System.out.println(new Solution().myAtoi("123213213213213211234"));
    }

    public int myAtoi(String s) {
        Automation automation=new Automation();
        return automation.cal(s);
    }

    private class Automation {
        private final Map<String, String[]> map = new HashMap<>();
        private String curState = "start";
        private long res = 0;
        private int sign = 1;


        public Automation() {
            initStatus();
        }

        public int cal(String s) {
            for (char c : s.toCharArray()) {
                parseChar(c);
            }
            return sign * (int) res;
        }

        //穷举当前状态和下一个状态的对应关系
        private void initStatus() {
            //' '、+/-、0-9、other"
            map.put("start", new String[]{"start", "sign", "innumber", "end"});
            map.put("sign", new String[]{"end", "end", "innumber", "end"});
            map.put("innumber", new String[]{"end", "end", "innumber", "end"});
            map.put("end", new String[]{"end", "end", "end", "end"});
        }

        //处理每种对应关系
        public void parseChar(char c) {
            String state = map.get(curState)[getNextState(c)];
            if (state.equals("innumber")) {
                res = res * 10 + (c - '0');
                res = sign == 1 ? Math.min(res, (long) Integer.MAX_VALUE) : Math.min(res, -(long) Integer.MIN_VALUE);
            } else if (state.equals("sign")) {
                sign = c == '-' ? -1 : 1;
            }
            curState = state;
        }

        private int getNextState(char c) {
            if (c == ' ') {
                return 0;
            } else if (c == '+' || c == '-') {
                return 1;
            } else if (Character.isDigit(c)) {
                return 2;
            } else {
                return 3;
            }
        }
    }
}

应用场景

当我们的系统复杂度到一定程度的时候，对象的状态分支会很多，我们可以选择用if，else来解决，但是最后往往会写出一堆几乎无法维护的屎山。那么我们可以将对象抽象成一个个状态，特殊情况实际上就是状态之间的转换。

比如上题，就是有限的状态之间的转换。
avator