AI工程软件系统

责任链模式

字数统计: 2.3k字   |   阅读时长: 10分
, ,

摘要: 用责任链模式解决力扣中的一道题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

$1 题目

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

  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 。

示例 1：
输入：s = “0”
输出：true

示例 2：
输入：s = “e”
输出：false

示例 3：
输入：s = “.”
输出：false

提示：

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

$2 题解

算法1: 正则表达式/有限自动机

参考文章：词法分析-有限自动机。

算法2: 责任链模式

责任链模式是行为型设计模式中的一种。行为型模式关注做事的过程，也就是算法和对象间的交互。

常见的行为型设计模式有责任链模式、命令模式、解释器模式、观察者模式、状态模式(本题第一种解法)、策略模式、模板模式。

当外部程序请求进行某个处理，但是程序不知道应该由那个对象进行处理时，可以考虑将多个对象组成一条职责链，然后按照它们在职责链上的顺序一个一个地找，应该由谁负责处理。这种模式称为责任链模式。

使用责任链模式可以弱化请求方和处理方的关系，将请求方和处理方解耦，让双方各自都成为可独立复用的组件。请求方无需调用别的函数，直接把请求发给一个由多个处理请求的对象组成的链条，链条上每个对象都负责一种请求，当前请求应该由那个对象处理由责任链来决定，请求方不用再关心了。

例如用户界面接收到一个要处理的事件，事件有三种：用户触发的鼠标事件、键盘事件，系统触发的计时器事件。有三个对象分别处理这三种事件：TimerHandler, KeyHandler, MouseHandler。处理事件的一种可能的责任链如下图：

总结一下：当需要让多个对象处理单个请求时，或者不知道改用那个对象处理特定请求时，可以用责任链模式，例如基于事件编程。责任链的价值在于将请求方和处理方解耦。请求方可以直接访问链中的首个节点，若首节点不能处理请求，则下传给下一节点，直到请求被某个节点处理或者整个链上的对象都遍历完了。

按照责任链模式，本题要做的事情有两步：

  • 分析输入字符串总共有几种情况，分别写出处理特定类输入字符串的对象
  • 写一个链，驱动所有的处理输入字符串的对象

输入的字符串有以下几种情况：

  1. 无内容串，即空串和全都是空格的串
  2. 整数
  3. 浮点数
  4. 科学计数法
  5. 有内容，但是不合法

因此最核心的是判断整数、判断浮点数、判断科学计数法这三个对象。此外还有一个特判情况：空串，也用一个对象专门处理，并且放在首位。此外还有一个非法字符串处理对象，如果前面的所有对象都没有处理，则传给该对象，该对象不论接到什么字符串，均返回 false。

接下来一个一个实现即可。除了末位的对象，每个对象中都有一个 nxt 字段，它是一个指针，指向责任链的下一个对象，当需要将请求下传时，调用 nxt -> validate()。

所有处理对象的基类

1
2
3
4
5
6
class Validator
{
public:
    virtual ~Validator(){}
    virtual bool validate(const string&) const =0;
};

末位的非法串处理对象

注意因为到了链条末位，没有 nxt。

1
2
3
4
5
6
7
8
class FalseValidator:public Validator
{
public:
    bool validate(const string& s) const
    {
        return false;
    }
};

首位的空串处理对象

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class EmptyValidator:public Validator
{
public:
    EmptyValidator(Validator* p=nullptr):nxt(p){}
    bool validate(const string& s) const
    {
        if(s.empty())
            return false;
        int n = s.size();
        int i = 0;
        while(i < n)
        {
            if(s[i] != ' ')
                return nxt -> validate(s);
            ++i;
        }
        return false;
    }

private:
    Validator *nxt;
};

整数处理对象

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
class IntegerValidator:public Validator
{
public:
    IntegerValidator(Validator* p=nullptr):nxt(p){}
    bool validate(const string& s) const
    {
        int i = s.find_first_not_of(' ');
        if(s[i] == '+' || s[i] == '-') ++i;
        int d = 0;
        while(i < (int)s.length() && isdigit(s[i]))
        {
            ++d;
            ++i;
        }
        while(i < (int)s.length() && s[i]==' ')
            ++i;
        if(i == (int)s.length() && d > 0)
            return true;
        else
            return nxt -> validate(s);
    }

private:
    Validator *nxt;
};

浮点数处理对象

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
class FloatValidator:public Validator
{
public:
    FloatValidator(Validator* p=nullptr):nxt(p){}
    bool validate(const string& s) const
    {
        if(s.empty()) return nxt -> validate(s);
        int i = s.find_first_not_of(' ');
        if(s[i] == '+' || s[i] == '-') ++i;
        int d1 = 0, point = 0, d2 = 0;
        while(i < (int)s.length() && isdigit(s[i]))
        {
            ++d1;
            ++i;
        }
        while(i < (int)s.length() && s[i] == '.')
        {
            ++point;
            ++i;
        }
        if(point !=0 && point != 1) return false;
        while(i < (int)s.length() && isdigit(s[i]))
        {
            ++d2;
            ++i;
        }
        while(i < (int)s.length() && s[i] == ' ')
        {
            ++point;
            ++i;
        }
        if(i == (int)s.length() && ((point && (d1 || d2)) || d1))
            return true;
        else
            return nxt -> validate(s);
    }

private:
    Validator *nxt;
};

科学计数法处理对象

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
class ScienceValidator:public Validator
{
public:
    ScienceValidator(Validator* p=nullptr):nxt(p){}
    bool validate(const string& s) const
    {
        int i = s.find_first_of('e');
        FalseValidator false_validator;
        FloatValidator before(&false_validator);
        IntegerValidator after(&false_validator);
        string before_e = s.substr(0, i);
        string after_e = s.substr(i + 1, s.size() - i - 1);
        if(before_e.size() - 1 == before_e.find_last_of(' '))
            return false;
        if(after_e.find_first_of(' ') == 0)
            return false;
        if(before_e.empty() || after_e.empty())
            return false;
        if(before.validate(before_e) && after.validate(after_e))
            return true;
        else
            return nxt -> validate(s);
    }

private:
    Validator *nxt;
};

整合责任链

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class NumberValidator
{
private:
    FalseValidator false_validator;
    IntegerValidator integer_validator;
    EmptyValidator empty_validator;
    FloatValidator float_validator;
    ScienceValidator science_validator;
public:
    NumberValidator()
    {
        false_validator = FalseValidator();
        empty_validator = EmptyValidator(&integer_validator);
        integer_validator = IntegerValidator(&float_validator);
        float_validator = FloatValidator(&science_validator);
        science_validator = ScienceValidator(&false_validator);
    }
    bool operator()(const string& s) const
    {
        return empty_validator.validate(s);
    }
};

使用责任链模式，责任链上的对象可以推卸请求，将请求下传给下一个对象，这会使得处理请求发生延迟。这是需要权衡的问题，如果请求方和处理方的关系是确定的，而且需要非常快的处理速度时候，不用责任链模式更好。

代码(C++)

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
class Validator
{
public:
    virtual ~Validator(){}
    virtual bool validate(const string&) const =0;
};

class FalseValidator:public Validator
{
public:
    bool validate(const string& s) const
    {
        return false;
    }
};

class EmptyValidator:public Validator
{
public:
    EmptyValidator(Validator* p=nullptr):nxt(p){}
    bool validate(const string& s) const
    {
        if(s.empty())
            return false;
        int n = s.size();
        int i = 0;
        while(i < n)
        {
            if(s[i] != ' ')
                return nxt -> validate(s);
            ++i;
        }
        return false;
    }

private:
    Validator *nxt;
};

class IntegerValidator:public Validator
{
public:
    IntegerValidator(Validator* p=nullptr):nxt(p){}
    bool validate(const string& s) const
    {
        int i = s.find_first_not_of(' ');
        if(s[i] == '+' || s[i] == '-') ++i;
        int d = 0;
        while(i < (int)s.length() && isdigit(s[i]))
        {
            ++d;
            ++i;
        }
        while(i < (int)s.length() && s[i]==' ')
            ++i;
        if(i == (int)s.length() && d > 0)
            return true;
        else
            return nxt -> validate(s);
    }

private:
    Validator *nxt;
};

class FloatValidator:public Validator
{
public:
    FloatValidator(Validator* p=nullptr):nxt(p){}
    bool validate(const string& s) const
    {
        if(s.empty()) return nxt -> validate(s);
        int i = s.find_first_not_of(' ');
        if(s[i] == '+' || s[i] == '-') ++i;
        int d1 = 0, point = 0, d2 = 0;
        while(i < (int)s.length() && isdigit(s[i]))
        {
            ++d1;
            ++i;
        }
        while(i < (int)s.length() && s[i] == '.')
        {
            ++point;
            ++i;
        }
        if(point !=0 && point != 1) return false;
        while(i < (int)s.length() && isdigit(s[i]))
        {
            ++d2;
            ++i;
        }
        while(i < (int)s.length() && s[i] == ' ')
        {
            ++point;
            ++i;
        }
        if(i == (int)s.length() && ((point && (d1 || d2)) || d1))
            return true;
        else
            return nxt -> validate(s);
    }

private:
    Validator *nxt;
};

class ScienceValidator:public Validator
{
public:
    ScienceValidator(Validator* p=nullptr):nxt(p){}
    bool validate(const string& s) const
    {
        int i = s.find_first_of('e');
        FalseValidator false_validator;
        FloatValidator before(&false_validator);
        IntegerValidator after(&false_validator);
        string before_e = s.substr(0, i);
        string after_e = s.substr(i + 1, s.size() - i - 1);
        if(before_e.size() - 1 == before_e.find_last_of(' '))
            return false;
        if(after_e.find_first_of(' ') == 0)
            return false;
        if(before_e.empty() || after_e.empty())
            return false;
        if(before.validate(before_e) && after.validate(after_e))
            return true;
        else
            return nxt -> validate(s);
    }

private:
    Validator *nxt;
};

class NumberValidator
{
private:
    FalseValidator false_validator;
    IntegerValidator integer_validator;
    EmptyValidator empty_validator;
    FloatValidator float_validator;
    ScienceValidator science_validator;
public:
    NumberValidator()
    {
        false_validator = FalseValidator();
        empty_validator = EmptyValidator(&integer_validator);
        integer_validator = IntegerValidator(&float_validator);
        float_validator = FloatValidator(&science_validator);
        science_validator = ScienceValidator(&false_validator);
    }
    bool operator()(const string& s) const
    {
        return empty_validator.validate(s);
    }
};

class Solution {
public:
    bool isNumber(string &s) {
        NumberValidator validator;
        return validator(s);
    }
};
Share