TSOJ 1057 合法浮点数判断 – 字符串匹配 DFA(maybe)

题目描述

请你判断，哪些是合法的浮点数

浮点数的表示通常有以下两种形式：

1) 十进制小数形式。由数字和小数点组成，必须有小数点，允许出现若干个前导零。例如（123.）（123.0）（.123）（00123.456）。

2) 指数形式。字母 e（或 E）之前必须有数字，允许出现若干个前导零，e 后面的指数必须为整数。例如（123e3）（00123e4）。

样例

样例输入:
8
1.234
+1.234
-12.3e+23
.2E34
E2
2.3e2.3
2e
001.1
样例输出:
Yes
Yes
Yes
No
No
No
No
Yes

分析

解法1 正则表达式

使用C++ regex 库可以实现

但问题是C++编译正则表达式的速度实在不快，实用性不高。

此题想正则表达式的时间和用DFA做实际上差不多。DFA(maybe)

解法2 DFA

看起来复杂 实际上很容易归纳

C++14  REQUIRED

#include <bits/stdc++.h>

using namespace std;

struct Node {
    function<bool(string::iterator)> check;
    size_t limit;
    vector<shared_ptr<Node>> next;

    Node(auto a, auto b): check(a), limit(b) {};

    bool exec(auto it) {
        for (size_t c = 0; check(it) && c < limit; ++c, ++it);
        if (next.size() == 0) return true;
        for (auto e : next) {
            if (e->check(it) && e->exec(it)) return true;
        }
        return false;
    }

    // auto attatch(initializer_list<shared_ptr<Node>> ns) {
    //     for (auto&& e : ns) next.push_back(e);
    // }

    template <typename ...Args>
    auto attatch(Args&& ...args) {
        for (auto&& ele : {args...}) next.push_back(ele);
    }

};


auto st = make_shared<Node>([](auto it) {return false;}, -1);
auto n1 = make_shared<Node>([](auto it) {return *it == '+' || *it == '-';}, 1);
auto n2 = make_shared<Node>([](auto it) {return *it == '+' || *it == '-';}, 1);
auto i1 = make_shared<Node>([](auto it) {return isdigit(*it);}, -1);
auto i2 = make_shared<Node>([](auto it) {return isdigit(*it);}, -1);
auto i3 = make_shared<Node>([](auto it) {return isdigit(*it);}, -1);
auto d1 = make_shared<Node>([](auto it) {return *it == '.';}, 1);
auto d2 = make_shared<Node>([](auto it) {return *it == '.';}, 1);
auto ee = make_shared<Node>([](auto it) {return *it == 'e' || *it == 'E';}, 1);
auto ed = make_shared<Node>([](auto it) {return *it == 0;}, -1);


void init() {
    st->attatch(n1, d2, i1);
    i1->attatch(ee, d1);
    d1->attatch(ed, ee, i2);
    d2->attatch(ed, ee, i2);
    i2->attatch(ed, ee);
    ee->attatch(i3, n2);
    n1->attatch(d2, i1);
    d2->attatch(i2);
    n2->attatch(i3);
    i3->attatch(ed);
}

int main() {
    init();
    string s;
    int i;
    while (cin >> i) {
        while (i--) {
            cin >> s;
            cout << (st->exec(s.begin()) ? "Yes" : "No") << endl;
        }
    };
    return 0;
}

很久之后的更新：

此题，我实际上是而为了用智能指针而用智能指针，花费了很多无用的努力，但是过程中也学到了很多东西。

这里使用 shared_ptr 实际上没有必要，而且如果自动机不是一个DAG的话，会出现内存泄露的问题。

智能指针是用来更智能地去管理动态分配内存的工具，用来处理引用关系或者指向的话实际上没有什么优势。使用裸指针也是可以的。

此代码为第二版本。第四版本已经解决上述问题，如下：

#include <bits/stdc++.h>

using namespace std;

struct Node {

    function<bool(string::iterator)> check;
    size_t limit;
    vector<Node*> next;

    Node(auto a, auto b): check(a), limit(b) {};

    bool exec(auto it) const {
        for (size_t c = 0; check(it) && c < limit; ++c, ++it);
        if (next.size() == 0) return true;
        for (auto e : next) {
            if (e->check(it) && e->exec(it)) return true;
        }
        return false;
    }

    void attatch() {}
        
    template <class T, class ...Args>
    void attatch(T&& head, Args&&... args) {
        next.push_back(&head);
        attatch(args...);
    }

};

Node st([](auto it) {return false;}, -1);
Node n1([](auto it) {return *it == '+' || *it == '-';}, 1);
Node n2([](auto it) {return *it == '+' || *it == '-';}, 1);
Node i1([](auto it) {return isdigit(*it);}, -1);
Node i2([](auto it) {return isdigit(*it);}, -1);
Node i3([](auto it) {return isdigit(*it);}, -1);
Node d1([](auto it) {return *it == '.';}, 1);
Node d2([](auto it) {return *it == '.';}, 1);
Node ee([](auto it) {return *it == 'e' || *it == 'E';}, 1);
Node ed([](auto it) {return *it == 0;}, -1);

void init() {
    st.attatch(n1, d2, i1);
    i1.attatch(ee, d1);
    d1.attatch(ed, ee, i2);
    i2.attatch(ed, ee);
    ee.attatch(i3, n2);
    n1.attatch(d2, i1);
    d2.attatch(i2);
    n2.attatch(i3);
    i3.attatch(ed);
}

int main() {
    init();
    string s;
    int i;
    cin >> i;
    while (i--) {
        cin >> s;
        cout << (st.exec(s.begin()) ? "Yes" : "No") << endl;
    }
    return 0;
}

解法3 很多 if else

略

本作品使用基于以下许可授权：Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.