自动机系列之一：自动机的模板代码及其demo

2019-04-13 21:07发布

站内文章 / 模拟电子
13997 0 1615
里面一个函数就是一个自动机，其中包括了正则的自动机，是否为数字的的自动机等 #include using namespace std; bool isNumber(string s) { enum InputType { INVALID, // 1. invalid input SIGN, // 2. '+' or '-' DIGIT, // 3. digits DOT, // 4. '.' EXP // 5. 'e' }; const int NUM_INPUT = 5; if(s == " ") return false; //get rid of space int start = s.find_first_not_of(" "); int end = s.find_last_not_of(" "); string ss = s.substr(start, end-start+1); int n = ss.size(); int state = 0; const int transitionTable[][NUM_INPUT] = { -1, 3, 1, 2, -1, -1, -1, 1, 4, 5, -1, -1, 4, -1, -1, -1, -1, 1, 2, -1, -1, -1, 4, -1, 5, -1, 6, 7, -1, -1, -1, -1, 7, -1, -1, -1, -1, 7, -1, -1, -1, -1, 7, -1, -1, }; for(int i = 0; i < n; ++i) { InputType type = INVALID; if(ss[i] == '+' || ss[i] == '-') { type = SIGN; } else if(isdigit(ss[i])) { type = DIGIT; } else if(ss[i] == '.') { type = DOT; } else if(ss[i] == 'e' || ss[i] == 'E') { type = EXP; } state = transitionTable[state][type]; if(state == -1) return false; } return state == 1 || state == 4 || state == 7; } bool isABAB(string s) { enum InputType { A, // input a B, // input b OTHER //other input }; const int NUM_INPUT = 3; if(s == " ") return false; //get rid of space int start = s.find_first_not_of(" "); int end = s.find_last_not_of(" "); string ss = s.substr(start, end-start+1); int n = ss.size(); int state = 0; const int transitionTable[][NUM_INPUT] = { 0, 1, -1, //技巧就是从0状态开始建可能效果更好 -1, 0, -1, }; for(int i = 0; i < n; ++i) { InputType type = OTHER; if(ss[i] == 'a') { type = A; } else if(ss[i]=='b') { type = B; } else{ type = OTHER; } state = transitionTable[state][type]; if(state == -1) return false; } return state == 0 ; } bool isABBA(string s) { enum InputType { A, // input a B, // input b OTHER //other input }; const int NUM_INPUT = 3; if(s == " ") return false; //get rid of space int start = s.find_first_not_of(" "); int end = s.find_last_not_of(" "); string ss = s.substr(start, end-start+1); int n = ss.size(); int state = 1; const int transitionTable[][NUM_INPUT] = { -1, -1, -1, //error state 1 , 2 , -1, 3 , 2 , -1, 3 , -1, -1 }; for(int i = 0; i < n; ++i) { InputType type = OTHER; if(ss[i] == 'a') { type = A; } else if(ss[i]=='b') { type = B; } else{ type = OTHER; } state = transitionTable[state][type]; if(state == -1) return false; } return state == 3 ||state==2; } bool isIpv4Add(string s) { enum InputType { NUM, // input umber DIGIT, // input igit OTHER //other input }; const int NUM_INPUT = 3; if(s == " ") return false; //get rid of space int start = s.find_first_not_of(" "); int end = s.find_last_not_of(" "); string ss = s.substr(start, end-start+1); int n = ss.size(); int state = 1; const int transitionTable[][NUM_INPUT] = { // d . other /*0*/ 0, 0, 0,//Error state /*1*/ 2, 0, 0, 3, 5, 0, 4, 5, 0, 0, 5, 0, /*5*/ 6, 0, 0, 7, 9, 0, 8, 9, 0, 0, 9, 0, /*9*/ 10,0, 0, 11,13,0, 12,13,0, 0, 13,0, /*13*/ 14,0, 0, 15,0, 0,//final state 16,0, 0,//final state 0, 0, 0 //final state }; for(int i = 0; i < n; ++i) { InputType type = OTHER; if((ss[i]-'0')>=0 && (ss[i]-'0')<=9) { type = NUM; } else if(ss[i]=='.') { type = DIGIT; } else{ type = OTHER; } state = transitionTable[state][type]; if(state == 0) return false; } return state == 14 || state==15 || state==16 ; } int main() { string s; for(int i=0;i<10;i++){ cin>>s; cout << "Hello world!" << endl; if(isABBA(s)){ cout<<"yes"<else{ cout<<"no"<return 0; }

热门文章