正规表达式 转 NFA C++
时间: 2023-09-12 17:06:39 浏览: 67
实现正则表达式转NFA的算法有很多种,其中比较常用的是Thompson算法。下面是一个简单的C++实现:
```c++
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
// NFA的状态结构体
struct State {
char symbol; // 转移符号
State* out; // 普通转移
State* out1; // 分支转移1
State* out2; // 分支转移2
};
// NFA的起始状态和接受状态
struct Nfa {
State* start;
State* accept;
};
// 正则表达式转NFA的函数
Nfa regexToNfa(string regex) {
stack<Nfa> nfaStack;
for (int i = 0; i < regex.size(); i++) {
char c = regex[i];
switch (c) {
case '(': {
Nfa nfa;
nfa.start = new State();
nfa.accept = new State();
nfaStack.push(nfa);
break;
}
case ')': {
Nfa nfa = nfaStack.top();
nfaStack.pop();
if (!nfaStack.empty()) {
Nfa parent = nfaStack.top();
if (parent.accept->out == nullptr) {
parent.accept->out = nfa.start;
} else {
parent.accept->out1 = nfa.start;
}
if (nfa.accept->out == nullptr) {
nfa.accept->out = parent.start;
} else {
nfa.accept->out1 = parent.start;
}
parent.start = nfa.start;
parent.accept = nfa.accept;
nfaStack.pop();
nfaStack.push(parent);
} else {
nfaStack.push(nfa);
}
break;
}
case '|': {
Nfa nfa = nfaStack.top();
nfaStack.pop();
Nfa parent = nfaStack.top();
parent.accept->out1 = nfa.start;
nfa.accept->out = parent.start;
parent.start = nfa.start;
nfaStack.pop();
nfaStack.push(parent);
break;
}
case '*': {
Nfa nfa = nfaStack.top();
nfaStack.pop();
State* newStart = new State();
State* newAccept = new State();
newStart->out1 = nfa.start;
newStart->out2 = newAccept;
nfa.accept->out1 = nfa.start;
nfa.accept->out2 = newAccept;
nfa.start = newStart;
nfa.accept = newAccept;
nfaStack.push(nfa);
break;
}
default: {
Nfa nfa;
nfa.start = new State();
nfa.accept = new State();
nfa.start->symbol = c;
nfa.start->out = nfa.accept;
nfaStack.push(nfa);
break;
}
}
}
Nfa nfa = nfaStack.top();
return nfa;
}
int main() {
Nfa nfa = regexToNfa("a(b|c)*d");
return 0;
}
```
这个实现非常简单,只考虑了正则表达式中的括号、或、闭包和字母,没有处理转义字符和其他高级功能。实际使用时需要根据需要进行扩展。
相关推荐
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)