目录
题目描述
请你判断，哪些是合法的浮点数
浮点数的表示通常有以下两种形式：
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.