fork(1) download
copy 
  1. #include <iostream>
  2. #include <string>
  3. using namespace std;
  4.  
  5. #define MAXSIZE 100
  6. #define ERROR 0
  7. #define OK 1
  8.  
  9. typedef struct{
  10.     int s;//边的起始点
  11.     int f;//边的终止点
  12.     char ch;//边上的字母
  13. }arc;
  14.  
  15. typedef struct{
  16.     int state[MAXSIZE];//状态数组
  17.     int size;//状态实际容量
  18.     char chars[MAXSIZE];//合法字符集{a,b,c...}
  19.     int charNum;//合法字符数目
  20.     int start,finish;//起始点下标 完成点下标
  21.     arc move[MAXSIZE]; //转移边
  22.     int arcnum; //边的数目
  23. }NFA;
  24.  
  25. typedef char Operator;
  26. //操作数栈S2
  27. typedef struct{
  28.     NFA elem[MAXSIZE];
  29.     int top;
  30.     int stacksize;
  31. }OPND;
  32.  
  33. //运算符栈S1
  34. typedef struct{
  35.     Operator elem[MAXSIZE];
  36.     int top;
  37.     int stacksize;
  38. }OPTR;
  39.  
  40.  
  41.  
  42. //每个状态可达点集合类型
  43. typedef struct{
  44.     int accessPoint[MAXSIZE];//可达点集合 要求内部按序排列
  45.     int accessPointnum;//内含可达点个数
  46. }accessType;
  47.  
  48. //状态转移矩阵
  49. typedef struct{
  50.     char chars[MAXSIZE];
  51.     int charnum;
  52.     int states[MAXSIZE];
  53.     bool isFinished[MAXSIZE]; //state与isFinished下标对应元素一一对应
  54.     int statenum;
  55.     accessType arc[MAXSIZE][MAXSIZE];
  56. }SCGraph;
  57. //单个状态类型
  58. typedef struct{
  59.     int allStates[MAXSIZE]; //状态序号集合
  60.     int StatesNum;//该状态集合中含有状态数目
  61. }stateType;
  62. //确定化路径的矩阵(与状态转移矩阵的区别在于其表格最左侧的起始状态列可以由多个状态构成数组组成)
  63. typedef struct{
  64.     char chars[MAXSIZE];
  65.     int charnum;
  66.     stateType states[MAXSIZE];//Maxsize个 由最多Maxsize个状态构成的状态数组 构成的二维数组
  67.     bool isFinished[MAXSIZE]; //state与isFinished下标对应元素一一对应
  68.     int statenum;
  69.     accessType arc[MAXSIZE][MAXSIZE];
  70. }DFGraph;
  71.  
  72. typedef struct{
  73.     stateType state[MAXSIZE];//用来存储分裂的各个状态集合
  74.     int length; //目前分裂出的状态集合的数量
  75.     int target[MAXSIZE][MAXSIZE];//对于每个state数组中按顺序每个元素在每种条件下的终点集合
  76. }ProStateType;
  77.  
  78.  
  79. //初始化OPND和OPTR
  80. int InitSqstack2(OPND &S){
  81.     S.top=0;
  82.     S.stacksize=MAXSIZE;
  83.     return OK;
  84. }
  85. int InitSqstack1(OPTR &S){
  86.     S.top=0;
  87.     S.stacksize=MAXSIZE;
  88.     return OK;
  89. }
  90. //OPND和OPTR的进栈函数
  91. int Push2(OPND &S,NFA e){
  92.     if(S.top>=S.stacksize) return ERROR;
  93.     S.elem[S.top++]=e;
  94.     return OK;
  95. }
  96. int Push1(OPTR &S,Operator e){
  97.     if(S.top>=S.stacksize) return ERROR;
  98.     S.elem[S.top++]=e;
  99.     return OK;
  100. }
  101. //OPND和OPTR的出栈函数
  102. int Pop2(OPND &S,NFA &e){
  103.     if(S.top==0) return ERROR;
  104.     e=S.elem[S.top-1];
  105.     S.top--;
  106.     return OK;
  107. }
  108. int Pop1(OPTR &S,Operator &e){
  109.     if(S.top==0) return ERROR;
  110.     e=S.elem[S.top-1];
  111.     S.top--;
  112.     return OK;
  113. }
  114. //getTop函数
  115. int getTop2(OPND S,NFA &t){
  116.     if(S.top==0) return ERROR;
  117.     t=S.elem[S.top-1];
  118.     return OK;
  119. }
  120. int getTop1(OPTR S,Operator &t){
  121.     if(S.top==0) return ERROR;
  122.     t=S.elem[S.top-1];
  123.     return OK;
  124. }
  125.  
  126. int getIndex(char ch){
  127.     switch(ch){
  128.         case '*': return 0;
  129.         case '|': return 1;
  130.         case '.': return 2;
  131.         case '(': return 3;
  132.         case ')': return 4;
  133.         case '#': return 5;
  134.         default:return ERROR;
  135.     }
  136.  
  137. }
  138. bool IsOperate(char ch){
  139.     switch(ch){
  140.         case '*': return true;
  141.         case '|': return true;
  142.         case '.': return true;
  143.         case '(': return true;
  144.         case ')': return true;
  145.         case '#': return true;
  146.         default: return false;
  147.     }
  148. }
  149. //第一维表示栈内
  150. char operate[6]={'*','|','.','(',')','#'};
  151. char prior[6][6] = {
  152.          {'@','>','>','@','>','>'}
  153.         ,{'<','>','<','<','>','>'}
  154.         ,{'<','>','>','<','>','>'}
  155.         ,{'<','<','<','<','=','>'}
  156.         ,{'>','>','>','@','>','@'}
  157.         ,{'<','<','<','<','@','='}
  158. };
  159. int stateNum = 0;
  160. void displayNFA(NFA result){
  161.     cout<<"start:"<<result.start<<endl;
  162.     cout<<"finish:"<<result.finish<<endl;
  163.     cout<<"charNum:"<<result.charNum<<endl;
  164.     cout<<"chars:";
  165.     for (int i = 0; i < result.charNum; ++i) {
  166.         cout<<result.chars[i]<<" ";
  167.     }
  168.     cout<<endl<<"size:"<<result.size<<endl;
  169.     cout<<"states:";
  170.     for (int l = 0; l < result.size; ++l) {
  171.         cout<<result.state[l]<<" ";
  172.     }
  173.     cout<<endl<<"arcnum:"<<result.arcnum<<endl;
  174.     cout<<"moves:"<<endl;
  175.     for (int j = 0; j < result.arcnum; ++j) {
  176.         cout<<"move("<<result.move[j].s<<","<<result.move[j].f<<","<<result.move[j].ch<<")"<<endl;
  177.     }
  178.     cout<<endl;
  179. }
  180. NFA initNFA(char char1){
  181.     NFA nfa;
  182.     nfa.charNum = 1;
  183.     nfa.chars[0] = char1;
  184.     nfa.start = stateNum++;
  185.     nfa.finish = stateNum++;
  186.     nfa.state[0] = nfa.start;
  187.     nfa.state[1] = nfa.finish;
  188.     nfa.size = 2;
  189.     nfa.move[0].s = nfa.start;
  190.     nfa.move[0].f = nfa.finish;
  191.     nfa.move[0].ch = char1;
  192.     nfa.arcnum = 1;
  193.     displayNFA(nfa);
  194.     return nfa;
  195. }
  196. NFA ex1(string str,int i){
  197.     char char1,char2;
  198.     char1 = str[i];
  199.     char2= str[i+1];
  200.     if ((int)char2>96&&(int)char2<123)
  201.         cout<<"该式子不符合规则 操作数应为单字母";
  202.     return initNFA(char1);
  203. }
  204.  
  205. void merge(char char1[MAXSIZE],int char1num, char char2[MAXSIZE],int char2num,char (&char3)[MAXSIZE],int &char3num){
  206.     for(int i = 0;i < char1num;i++){
  207.         char3[i] = char1[i];
  208.     }
  209.     char3num = char1num;
  210.     for(int l = 0;l < char2num;l++){
  211.         for(int j = 0;j < char1num;j++){
  212.             if(char2[l] == char1[j])
  213.                 break;
  214.             else if(j == char1num-1)
  215.                 char3[char3num++] = char2[l];
  216.         }
  217.     }
  218. }
  219.  
  220. NFA OperOr(NFA eL,NFA eR){
  221.     NFA result;
  222.     result.start = stateNum++;
  223.     result.finish = stateNum++;
  224.     result.size = eL.size + eR.size + 2;
  225.     for(int i = 0;i < result.size;i++){
  226.         if(i == 0){
  227.             result.state[i] = result.start;
  228.         }
  229.         else if(i == 1){
  230.             result.state[i] = result.finish;
  231.         }
  232.         else{
  233.             if(i < (2+eL.size))
  234.                 result.state[i] = eL.state[i-2];
  235.             else
  236.                 result.state[i] = eR.state[i-2-eL.size];
  237.         }
  238.     }
  239.     merge(eL.chars,eL.charNum,eR.chars,eR.charNum,result.chars,result.charNum);
  240.     result.arcnum = eL.arcnum + eR.arcnum + 4;
  241.     for (int j = 0; j < result.arcnum; ++j) {
  242.         if(j == 0){
  243.             result.move[j].s = result.start;
  244.             result.move[j].f = eL.start;
  245.             result.move[j].ch = '@';
  246.         }
  247.         else if(j == 1){
  248.             result.move[j].s = result.start;
  249.             result.move[j].f = eR.start;
  250.             result.move[j].ch = '@';
  251.         }
  252.         else if(j == 2){
  253.             result.move[j].s = eL.finish;
  254.             result.move[j].f = result.finish;
  255.             result.move[j].ch = '@';
  256.         }
  257.         else if(j == 3){
  258.             result.move[j].s = eR.finish;
  259.             result.move[j].f = result.finish;
  260.             result.move[j].ch = '@';
  261.         }
  262.         else{
  263.             if(j < (4+eL.arcnum))
  264.                 result.move[j] = eL.move[j-4];
  265.             else
  266.                 result.move[j] = eR.move[j-4-eL.arcnum];
  267.         }
  268.     }
  269.     return result;
  270. }
  271.  
  272. NFA OperJoint(NFA eL,NFA eR){
  273.     NFA result;
  274.     result.start = eL.start;
  275.     result.finish = eR.finish;
  276.     result.size = eL.size + eR.size;
  277.     for(int i = 0;i < result.size;i++){
  278.         if(i < eL.size)
  279.             result.state[i] = eL.state[i];
  280.         else
  281.             result.state[i] = eR.state[i-eL.size];
  282.     }
  283.     merge(eL.chars,eL.charNum,eR.chars,eR.charNum,result.chars,result.charNum);
  284.     result.arcnum = eL.arcnum + eR.arcnum + 1;
  285.     for (int j = 0; j < result.arcnum; ++j) {
  286.         if(j == 0){
  287.             result.move[0].s = eL.finish;
  288.             result.move[0].f = eR.start;
  289.             result.move[0].ch = '@';
  290.         }
  291.         else{
  292.             if(j < (1+eL.arcnum))
  293.                 result.move[j] = eL.move[j-1];
  294.             else
  295.                 result.move[j] = eR.move[j-1-eL.arcnum];
  296.         }
  297.     }
  298.     return result;
  299. }
  300.  
  301. NFA OperClosure(NFA eR){
  302.     NFA result;
  303.     result.start = stateNum++;
  304.     result.finish = stateNum++;
  305.     result.size = eR.size + 2;
  306.     for(int i = 0;i < result.size;i++){
  307.         if(i == 0){
  308.             result.state[i] = result.start;
  309.         }
  310.         else if(i == 1){
  311.             result.state[i] = result.finish;
  312.         }
  313.         else{
  314.             result.state[i] = eR.state[i-2];
  315.         }
  316.     }
  317.     result.charNum = eR.charNum;
  318.     for (int k = 0; k < result.charNum; ++k) {
  319.         result.chars[k] = eR.chars[k];
  320.     }
  321.     result.arcnum = eR.arcnum + 4;
  322.     for (int j = 0; j < result.arcnum; ++j) {
  323.         if(j == 0){
  324.             result.move[j].s = result.start;
  325.             result.move[j].f = eR.start;
  326.             result.move[j].ch = '@';
  327.         }
  328.         else if(j == 1){
  329.             result.move[j].s = result.start;
  330.             result.move[j].f = result.finish;
  331.             result.move[j].ch = '@';
  332.         }
  333.         else if(j == 2){
  334.             result.move[j].s = eR.finish;
  335.             result.move[j].f = eR.start;
  336.             result.move[j].ch = '@';
  337.         }
  338.         else if(j == 3){
  339.             result.move[j].s = eR.finish;
  340.             result.move[j].f = result.finish;
  341.             result.move[j].ch = '@';
  342.         }
  343.         else{
  344.             result.move[j] = eR.move[j-4];
  345.         }
  346.     }
  347.     return result;
  348. }
  349.  
  350. NFA count1(NFA eR){
  351.     return OperClosure(eR);
  352. }
  353. NFA count2(Operator ch,NFA eL,NFA eR){
  354.     switch(ch){
  355.         case '|': return OperOr(eL,eR);
  356.         case '.': return OperJoint(eL,eR);
  357.         default:
  358.             cout<<"error";
  359.             return eL;
  360.     }
  361. }
  362.  
  363. int EvalutionExpression(string str,NFA &result){
  364.     OPTR S1;
  365.     OPND S2;//S1:运算符，S2：操作数
  366.     InitSqstack1(S1);
  367.     InitSqstack2(S2);
  368.     char ch;
  369.     Push1(S1,'#');
  370.  
  371.     //在表达式末尾插入'#'可用->【strCat(str,'#');】或者
  372.     int i;
  373.     for(i=0;str[i]!='\0';i++) ;
  374.     str=str+'#';
  375. //	 strcat(str,"#");
  376.     //将i归零，一会儿要用
  377.     i=0;
  378.     //获取运算符栈里栈顶的运算符ch
  379.     getTop1(S1,ch);
  380.     while(ch!='#' || str[i]!='#'){
  381.         //自左向右扫描str
  382.         if(IsOperate(str[i]))//判断str[i]是运算符
  383.         {
  384.             //是运算符 :与运算符栈的栈顶元素比较优先级
  385.             int m = getIndex(ch); //栈顶元素
  386.             int n = getIndex(str[i]);//遍历到的运算符
  387.             NFA eL,eR;
  388.             switch(prior[m][n])
  389.             {
  390.                 case '>'://栈内的更好
  391.                     if(ch == '*'){
  392.                         if(!Pop2(S2,eR)) return ERROR;
  393.                         result = count1(eR);
  394.                     }else{
  395.                         if(!Pop2(S2,eR)) return ERROR;
  396.                         if(!Pop2(S2,eL)) return ERROR;
  397.                         result = count2(ch,eL,eR);
  398.                     }
  399.                     Pop1(S1,ch);
  400.                     Push2(S2,result);
  401.                     getTop1(S1,ch);
  402.                     break;
  403.                 case '<':
  404.                     Push1(S1,str[i]);
  405.                     i++;
  406.                     getTop1(S1,ch);
  407.                     break;
  408.                 case '='://栈内是（，栈外是）
  409.                     Pop1(S1,ch) ;//(出栈
  410.                     i++;
  411.                     getTop1(S1,ch);
  412.             }
  413.  
  414.         }
  415.         else{//是操作数
  416.             NFA temp = ex1(str,i);
  417.             Push2(S2,temp);
  418.             i++;
  419.         }
  420.     }
  421.     Push2(S2,result);
  422.     NFA a;
  423.     getTop2(S2,a);
  424.     result=a;
  425.     return 0;
  426. }
  427.  
  428. //由状态数字从状态数组中获取下标
  429. int getNumIndex(int num,int array[MAXSIZE], int arrLength){
  430.     for (int i = 0; i < arrLength; ++i) {
  431.         if(num == array[i])
  432.             return i;
  433.     }
  434.     return -1;
  435. }
  436. int getChIndex(char ch,char array[MAXSIZE], int arrLength){
  437.     for (int i = 0; i < arrLength; ++i) {
  438.         if(ch == array[i])
  439.             return i;
  440.     }
  441.     return -1;
  442. }
  443. //向数组中插入一个数 要求从小到大排列
  444. void insertNum(int num,int (&array)[MAXSIZE],int &arrLength){
  445.     int i;
  446.     for (i = 0; i < arrLength; ++i) {
  447.         if(num > array[i])
  448.             continue;
  449.         else if(num == array[i]){
  450.             return;
  451.         }
  452.         else{
  453.             break;
  454.         }
  455.     }
  456.     arrLength++;
  457.     for (int j = arrLength; j > i ; --j) {
  458.         array[j] = array[j-1];
  459.     }
  460.     array[i] = num;
  461. }
  462. //初始化矩阵
  463. void initSC(SCGraph &sc){
  464.     for (int i = 0; i < sc.statenum; ++i) {
  465.         for (int j = 0; j < sc.charnum; ++j) {
  466.             sc.arc[i][j].accessPointnum = 0;
  467.         }
  468.     }
  469. }
  470. //NFA=>状态转移矩阵
  471. SCGraph changeNFAtoSCGraph(NFA result,SCGraph &sc){
  472.     int x = 0,y = 0;
  473.     for (int i = 0; i < result.charNum; ++i) {
  474.         sc.chars[i] = result.chars[i];
  475.     }
  476.     sc.chars[result.charNum] = '@';
  477.     sc.charnum = result.charNum+1;
  478.     for (int l = 0; l < result.size; ++l) {
  479.         sc.states[l] = result.state[l];
  480.         if (result.state[l] == result.finish)
  481.             sc.isFinished[l] = true;
  482.     }
  483.     sc.statenum = result.size;
  484.  
  485.     initSC(sc);
  486.     for (int j = 0 ; j < result.arcnum; ++j) {
  487.         x = getNumIndex(result.move[j].s, sc.states, sc.statenum);
  488.         y = getChIndex(result.move[j].ch,sc.chars,sc.charnum);
  489.  
  490.         insertNum(result.move[j].f,sc.arc[x][y].accessPoint,sc.arc[x][y].accessPointnum);
  491.     }
  492.     return sc;
  493. }
  494. //去除空转移（对于无死循环）
  495. void deleteEmptytrans(int from,SCGraph &sc){
  496.     int empty = getChIndex('@', sc.chars,sc.charnum);
  497.     int to;
  498.     if(sc.arc[from][empty].accessPointnum > 0){
  499.         while(sc.arc[from][empty].accessPointnum > 0) {
  500.             to = getNumIndex(sc.arc[from][empty].accessPoint[sc.arc[from][empty].accessPointnum - 1], sc.states,
  501.                              sc.statenum);
  502.             if (sc.isFinished[to])
  503.                 sc.isFinished[from] = true;
  504.             if (sc.arc[to][empty].accessPointnum == 0) {
  505.                 for (int i = 0; i < sc.charnum; ++i) {
  506.                     for (int j = 0; j < sc.arc[to][i].accessPointnum; ++j) {
  507.                         //向原格子中合并入空转移所到格子的可达点
  508.                         insertNum(sc.arc[to][i].accessPoint[j], sc.arc[from][i].accessPoint,
  509.                                   sc.arc[from][i].accessPointnum);
  510.                     }
  511.                 }
  512.                 sc.arc[from][empty].accessPointnum--;
  513.             }else
  514.                 deleteEmptytrans(to,sc);
  515.         }
  516.     }
  517. }
  518.  
  519. void deleteAllEmpty(SCGraph &sc){
  520.     for (int i = 0; i < sc.statenum; ++i) {
  521.         deleteEmptytrans(i,sc);
  522.     }
  523.     int empty = getChIndex('@', sc.chars,sc.charnum);
  524.     for (int j = empty; j < sc.charnum-1; ++j) {
  525.         sc.chars[j] = sc.chars[j+1]; //将原表格中空转移那一列删除
  526.     }
  527.     sc.charnum--;
  528. }
  529. //比对已知一维数组是否存在于已知二位数组中
  530. bool isExist(int one[MAXSIZE],int onelength,stateType two[MAXSIZE],int twolength){
  531.     int j;
  532.     for (int i = 0; i < twolength; ++i) {
  533.         for (j = 0; j < onelength; ++j) {
  534.             if(two[i].allStates[j] != one[j]){
  535.                 break;
  536.             }
  537.         }
  538.         if(j == onelength && two[i].StatesNum==onelength)
  539.             return true;
  540.     }
  541.     return false;
  542. }
  543. void DefineOneRow(NFA result,SCGraph sc,DFGraph &df,int newline[MAXSIZE],int newlinelength,bool &isFirst){
  544.     if(newlinelength <= 0)
  545.         return;
  546.     int x;
  547.     int index;
  548.     //两种情况：1.将原来的去空转移终点矩阵第一行照搬过来
  549.     //2.当前该种状态集合未产生过且未被插入到矩阵的状态列表中
  550.     if(!isExist(newline,newlinelength,df.states,df.statenum)||isFirst){
  551.         df.states[df.statenum].StatesNum = 0;
  552.         //如果是第二种情况就将该集合先插入到矩阵的状态列表中
  553.         if(!isFirst){
  554.             for (int l = 0; l < newlinelength; ++l) {
  555.                 insertNum(newline[l],df.states[df.statenum].allStates,df.states[df.statenum].StatesNum);
  556.             }
  557.             df.statenum++;
  558.         }
  559.         isFirst = false;
  560.         //为新添加到状态列表中的新状态填入对应条件的可达状态集
  561.         for (int j = 0; j < sc.charnum; ++j) {
  562.             df.arc[df.statenum-1][j].accessPointnum = 0;
  563.             for (int i = 0; i < newlinelength; ++i) {
  564.                 x =  getNumIndex(newline[i],sc.states,sc.statenum);
  565.                 if(sc.isFinished[x])
  566.                     df.isFinished[df.statenum-1] = true;
  567.                 for (int k = 0; k < sc.arc[x][j].accessPointnum; ++k) {
  568.                     insertNum(sc.arc[x][j].accessPoint[k],df.arc[df.statenum-1][j].accessPoint,df.arc[df.statenum-1][j].accessPointnum);
  569.                 }
  570.             }
  571.         }
  572.         //(已解决)新问题：只有前一个条件下状态集存在时候下一个条件的状态集才会被判断，不然不会递归回来，好奇怪
  573.         index = df.statenum-1;
  574.         for (int l = 0; l < sc.charnum; ++l) {
  575. //
  576.             if(!isExist(df.arc[index][l].accessPoint,df.arc[index][l].accessPointnum,df.states,df.statenum)){
  577.  
  578.                 DefineOneRow(result,sc,df,df.arc[index][l].accessPoint,df.arc[index][l].accessPointnum,isFirst);
  579.             }
  580.         }
  581.  
  582.     }
  583.  
  584. }
  585. void defNFA(NFA result,SCGraph sc,DFGraph &df){
  586.     //初始化df
  587.     df.statenum = 0;
  588.     for (int i = 0; i < result.charNum; ++i) {
  589.         df.chars[i] = result.chars[i];
  590.     }
  591.     df.charnum = result.charNum;
  592.     //将矩阵中初态作为第一个状态
  593.     df.states[0].allStates[0] = result.start;
  594.     df.statenum++;
  595.     df.states[0].StatesNum = 1;
  596.     bool isFirst = true;
  597.     DefineOneRow(result,sc,df,df.states[0].allStates,df.states[0].StatesNum,isFirst);
  598. }
  599.  
  600.  
  601. void displaySC(SCGraph &sc){
  602.     cout<<endl<<"                          ";
  603.     for (int i = 0; i < sc.charnum; ++i) {
  604.         cout<<sc.chars[i]<<"         ";
  605.     }
  606.     cout<<endl;
  607.     for (int j = 0; j < sc.statenum; ++j) {
  608.         if(sc.isFinished[j])
  609.             cout<<"(终态)";
  610.         else
  611.             cout<<"(非终)";
  612.         cout<<sc.states[j];
  613.  
  614.         cout<<":    ";
  615.         for (int i = 0; i < sc.charnum; ++i) {
  616.             for (int k = 0; k < sc.arc[j][i].accessPointnum; ++k) {
  617.                 cout<<sc.arc[j][i].accessPoint[k]<<",";
  618.             }
  619.             cout<<"             ";
  620.         }
  621.         cout<<endl;
  622.     }
  623.     cout<<endl;
  624. }
  625. void displayDF(DFGraph df){
  626.     cout<<"                   ";
  627.     for (int i = 0; i < df.charnum; ++i) {
  628.         cout<<df.chars[i]<<"                 ";
  629.     }
  630.     cout<<endl;
  631.     for (int j = 0; j < df.statenum; ++j) {
  632.         if(df.isFinished[j])
  633.             cout<<"(终态)";
  634.         else
  635.             cout<<"(非终)";
  636.         for (int l = 0; l < df.states[j].StatesNum; ++l) {
  637.             cout<<df.states[j].allStates[l]<<",";
  638.         }
  639.  
  640.         cout<<":  ";
  641.         for (int i = 0; i < df.charnum; ++i) {
  642.             for (int k = 0; k < df.arc[j][i].accessPointnum; ++k) {
  643.                 cout<<df.arc[j][i].accessPoint[k]<<",";
  644.             }
  645.             cout<<"                   ";
  646.         }
  647.         cout<<endl;
  648.     }
  649.     cout<<endl;
  650. }
  651. //比对已知一维数组存在于已知二位数组中的下标
  652. int isExistIndex(int one[MAXSIZE],int onelength,stateType two[MAXSIZE],int twolength){
  653.     int j;
  654.     for (int i = 0; i < twolength; ++i) {
  655.         for (j = 0; j < onelength; ++j) {
  656.             if(two[i].allStates[j] != one[j]){
  657.                 break;
  658.             }
  659.         }
  660.         if(j == onelength && two[i].StatesNum==onelength)
  661.             return i;
  662.     }
  663.     return -1;
  664. }
  665. //重命名
  666. void Rename(DFGraph &df){
  667.     int index;
  668.     for (int i = 0; i < df.statenum; ++i) {
  669.         for (int j = 0; j < df.charnum; ++j) {
  670.             index = isExistIndex(df.arc[i][j].accessPoint,df.arc[i][j].accessPointnum,df.states,df.statenum);
  671.             if(index < 0)
  672.                 continue;
  673.             df.arc[i][j].accessPoint[0] = index;
  674.             df.arc[i][j].accessPointnum = 1;
  675.         }
  676.     }
  677.     for (int k = 0; k < df.statenum; ++k) {
  678.         df.states[k].StatesNum = 1;
  679.         df.states[k].allStates[0] = k;
  680.     }
  681. }
  682. //由状态数字从状态数组中获取下标
  683. int getNumIndex(int num,stateType array[MAXSIZE], int arrLength){
  684.     for (int i = 0; i < arrLength; ++i) {
  685.         if(num == array[i].allStates[0])
  686.             return i;
  687.     }
  688.     return -1;
  689. }
  690. //判断数字是否存在于一维数组中
  691. bool isExist(int num,int array[MAXSIZE],int arrlength){
  692.     for (int i = 0; i < arrlength; ++i) {
  693.         if(num == array[i])
  694.             return true;
  695.     }
  696.     return false;
  697. }
  698. //将一个状态从另一个状态集中剥离出来成为新状态的处理：
  699. void DepartStates(ProStateType &pst,int Delete,int num){
  700.     //已知Add的数值获取Add在state【num】中的下标
  701.     int a = getNumIndex(Delete,pst.state[num].allStates,pst.state[num].StatesNum);
  702.     pst.state[pst.length++].allStates[0] = Delete;
  703.     pst.state[pst.length-1].StatesNum = 1;
  704.     for (int i = a; i < pst.state[num].StatesNum-1; ++i) {
  705.         pst.state[num].allStates[i] = pst.state[num].allStates[i+1];
  706.     }
  707.     pst.state[num].StatesNum--;
  708. }
  709. //将一个状态从一个状态中分离出来与另一个状态合并的处理：
  710. void MergeStates(ProStateType &pst,int DeleteState,int from,int to){
  711.     int d = getNumIndex(DeleteState,pst.state[from].allStates,pst.state[from].StatesNum);
  712.     pst.state[to].allStates[pst.state[to].StatesNum++] = DeleteState;
  713.     for (int i = d; i < pst.state[from].StatesNum-1; ++i) {
  714.         pst.state[from].allStates[i] = pst.state[from].allStates[i+1];
  715.     }
  716.     pst.state[from].StatesNum--;
  717.  
  718. }
  719.  
  720. //该函数用来判断当前要从原来集合中分离出来的那个状态是否可以与其它分离出来的状态合并为一个状态
  721. int EnableMerge(ProStateType pst,int state,DFGraph df){
  722.     int index = getNumIndex(state,df.states,df.statenum);
  723.     for(int i = 0; i < pst.length; ++i) {
  724.  
  725.         for (int j = 0; j < df.charnum;++j) {
  726.             if(!isExist(df.arc[index][j].accessPoint[0],pst.state[pst.target[i][j]].allStates,pst.state[pst.target[i][j]].StatesNum)){
  727.                 if(!df.arc[index][j].accessPoint[0]){
  728.                     if(j == df.charnum-1 )
  729.                         return i;
  730.                     continue;
  731.                 }
  732.                 break;
  733.             }
  734.             else if(j == df.charnum-1 )
  735.                 return i;
  736.         }
  737.     }
  738.     return -1;
  739. }
  740. //新问题：每当集合一分裂所有现存集合的target就需要更新！！
  741. //解决方法：遍历状态列表看看当前状态的target是哪个状态集合
  742. void updateTarget(ProStateType &pst,DFGraph df){
  743.     for (int i = 0; i < pst.length; ++i) {
  744.         for (int k = 0; k < df.charnum; ++k) {
  745.             for (int j = 0; j < pst.length; ++j) {
  746.                 if(isExist(df.arc[pst.state[i].allStates[0]][k].accessPoint[0],pst.state[j].allStates,pst.state[j].StatesNum)){
  747.                     pst.target[i][k] = j;
  748.                     break;
  749.                 }
  750.                 else if(!df.arc[pst.state[i].allStates[0]][k].accessPoint[0]){
  751.                     continue;
  752.                 }
  753.             }
  754.  
  755.         }
  756.  
  757.     }
  758.  
  759. }
  760. //该函数用来判断一个集合是否已经最小化完成
  761. void isleast(DFGraph df,ProStateType &pst,int num){
  762.     int index;
  763.     //第一步：为当前的集合选取每个条件下的唯一目标集合 填入target 和这个目标不一样的状态都分裂出去
  764.     for (int j = 0; j < df.charnum; ++j) {
  765.         for (int i = 0; i < pst.state[num].StatesNum; ++i) {
  766.             for (int k = 0; k < pst.length; ++k) {
  767.                 if(!df.arc[getNumIndex(pst.state[num].allStates[i],df.states,df.statenum)][j].accessPoint[0]||pst.target[num][j])
  768.                     break;
  769.                 else if(isExist(df.arc[getNumIndex(pst.state[num].allStates[i],df.states,df.statenum)][j].accessPoint[0],pst.state[k].allStates,pst.state[k].StatesNum)){
  770.                     pst.target[num][j] = k;
  771.                     break;
  772.                 }
  773.             }
  774.         }
  775.     }
  776.  
  777.  
  778.     for (int l = 0; l < pst.state[num].StatesNum; ++l) {
  779.         for (int i = 0; i < df.charnum; ++i) {
  780.             if(!isExist(df.arc[getNumIndex(pst.state[num].allStates[l],df.states,df.statenum)][i].accessPoint[0],pst.state[pst.target[num][i]].allStates,pst.state[pst.target[num][i]].StatesNum)){
  781.                 if(EnableMerge(pst,pst.state[num].allStates[l],df) >= 0){
  782.                     MergeStates(pst,pst.state[num].allStates[l],num,EnableMerge(pst,pst.state[num].allStates[l],df));
  783.                     updateTarget(pst,df);
  784.                 }
  785.                 else{
  786.                     DepartStates(pst,pst.state[num].allStates[l],num);
  787.                     updateTarget(pst,df);
  788.                     if(pst.state[num].StatesNum <= 0){
  789.                         for (int j = num; j < pst.length-1; ++j) {
  790.                             pst.state[j].StatesNum = pst.state[j+1].StatesNum;
  791.                             for (int k = 0; k < pst.state[j+1].StatesNum; ++k) {
  792.                                 pst.state[j].allStates[k] = pst.state[j+1].allStates[k];
  793.                             }
  794.                         }
  795.                         pst.length--;
  796.                     }
  797.                     else
  798.                         isleast(df,pst,num);
  799.                     break;
  800.                 }
  801.             }
  802.         }
  803.     }
  804.  
  805. }
  806.  
  807. void Simplify(DFGraph &df,ProStateType &pst){
  808.     for (int l = 0; l < df.statenum; ++l) {
  809.         pst.state[l].StatesNum = 0;
  810.     }
  811.     //先按照终态和非终态分为两个状态集
  812.     for (int i = 0; i < df.statenum; ++i) {
  813.         if(df.isFinished[i]){
  814.             pst.state[0].allStates[pst.state[0].StatesNum++] = df.states[i].allStates[0];
  815.         }else{
  816.             pst.state[1].allStates[pst.state[1].StatesNum++] = df.states[i].allStates[0];
  817.         }
  818.     }
  819.     pst.length = 2;
  820.     isleast(df,pst,0);
  821.     isleast(df,pst,1);
  822. }
  823. void displaypst(ProStateType &pst,DFGraph df){
  824.     cout<<"statenum:"<<pst.length<<endl;
  825.     cout<<"DFA简化后各个集合中分别包含以下状态"<<endl;
  826.     for (int k = 0; k < pst.length; ++k) {
  827.  
  828.         cout<<k<<": ";
  829.         for (int i = 0; i < pst.state[k].StatesNum; ++i) {
  830.             cout<<pst.state[k].allStates[i]<<",";
  831.         }
  832.         cout<<endl;
  833.     }
  834.     cout<<"DFA经简化以及对多状态集合重命名得到:"<<endl;
  835.     cout<<"     ";
  836.     for (int i = 0; i < df.charnum; ++i) {
  837.         cout<<df.chars[i]<<"                 ";
  838.     }
  839.     cout<<endl;
  840.     for (int j = 0; j < pst.length; ++j) {
  841.  
  842. //        for (int i = 0; i < pst.state[j].StatesNum; ++i) {
  843. //            cout<<pst.state[j].allStates[i]<<",";
  844. //        }
  845. //        cout<<":";
  846.         cout<<j<<":  ";
  847.  
  848.         for (int i = 0; i < df.charnum; ++i) {
  849.             cout<<pst.target[j][i];
  850.             cout<<"                   ";
  851.         }
  852.         cout<<endl;
  853.     }
  854.     cout<<endl;
  855. }
  856.  
  857. int main() {
  858.     string str = "(a|b)*.a.b.b.(a|b)*";//"(a|b).c*";//;
  859.     cout<<"请输入表达式（要求操作数都为 单个 小写 字母，中间用符号* . ( ) |连接）："<<endl;
  860.     //  cin>>str;
  861.     NFA result;
  862.     EvalutionExpression(str,result);
  863.     displayNFA(result);
  864.  
  865.     SCGraph sc;
  866.     changeNFAtoSCGraph(result,sc);
  867.     cout<<"将NFA转换成状态转移矩阵如下:"<<endl;
  868.     displaySC(sc);
  869.     deleteAllEmpty(sc);
  870.     cout<<"去除空转移如下:"<<endl;
  871.     displaySC(sc);
  872.     DFGraph df;
  873.     cout<<"确定化路径后如下:"<<endl;
  874.     defNFA(result,sc,df);
  875.     displayDF(df);
  876.     Rename(df);
  877.     cout<<"重命名后："<<endl;
  878.     displayDF(df);
  879.     ProStateType pst;
  880.     Simplify(df,pst);
  881.     displaypst(pst,df);
  882.     return 0;
  883. }
Success #stdin #stdout 0.02s 43212KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
请输入表达式（要求操作数都为 单个 小写 字母，中间用符号* . ( ) |连接）：
start:0
finish:1
charNum:1
chars:a 
size:2
states:0 1 
arcnum:1
moves:
move(0,1,a)

start:2
finish:3
charNum:1
chars:b 
size:2
states:2 3 
arcnum:1
moves:
move(2,3,b)

start:8
finish:9
charNum:1
chars:a 
size:2
states:8 9 
arcnum:1
moves:
move(8,9,a)

start:10
finish:11
charNum:1
chars:b 
size:2
states:10 11 
arcnum:1
moves:
move(10,11,b)

start:12
finish:13
charNum:1
chars:b 
size:2
states:12 13 
arcnum:1
moves:
move(12,13,b)

start:14
finish:15
charNum:1
chars:a 
size:2
states:14 15 
arcnum:1
moves:
move(14,15,a)

start:16
finish:17
charNum:1
chars:b 
size:2
states:16 17 
arcnum:1
moves:
move(16,17,b)

start:6
finish:21
charNum:2
chars:a b 
size:22
states:6 7 4 5 0 1 2 3 8 9 10 11 12 13 20 21 18 19 14 15 16 17 
arcnum:27
moves:
move(13,20,@)
move(11,12,@)
move(9,10,@)
move(7,8,@)
move(6,4,@)
move(6,7,@)
move(5,4,@)
move(5,7,@)
move(4,0,@)
move(4,2,@)
move(1,5,@)
move(3,5,@)
move(0,1,a)
move(2,3,b)
move(8,9,a)
move(10,11,b)
move(12,13,b)
move(20,18,@)
move(20,21,@)
move(19,18,@)
move(19,21,@)
move(18,14,@)
move(18,16,@)
move(15,19,@)
move(17,19,@)
move(14,15,a)
move(16,17,b)

将NFA转换成状态转移矩阵如下:

                          a         b         @         
(非终)6:                              4,7,             
(非终)7:                              8,             
(非终)4:                              0,2,             
(非终)5:                              4,7,             
(非终)0:    1,                                       
(非终)1:                              5,             
(非终)2:                 3,                          
(非终)3:                              5,             
(非终)8:    9,                                       
(非终)9:                              10,             
(非终)10:                 11,                          
(非终)11:                              12,             
(非终)12:                 13,                          
(非终)13:                              20,             
(非终)20:                              18,21,             
(终态)21:                                           
(非终)18:                              14,16,             
(非终)19:                              18,21,             
(非终)14:    15,                                       
(非终)15:                              19,             
(非终)16:                 17,                          
(非终)17:                              19,             

去除空转移如下:

                          a         b         
(非终)6:    1,9,             3,             
(非终)7:    9,                          
(非终)4:    1,             3,             
(非终)5:    1,9,             3,             
(非终)0:    1,                          
(非终)1:    1,9,             3,             
(非终)2:                 3,             
(非终)3:    1,9,             3,             
(非终)8:    9,                          
(非终)9:                 11,             
(非终)10:                 11,             
(非终)11:                 13,             
(非终)12:                 13,             
(终态)13:    15,             17,             
(终态)20:    15,             17,             
(终态)21:                              
(非终)18:    15,             17,             
(终态)19:    15,             17,             
(非终)14:    15,                          
(终态)15:    15,             17,             
(非终)16:                 17,             
(终态)17:    15,             17,             

确定化路径后如下:
                   a                 b                 
(非终)6,:  1,9,                   3,                   
(非终)1,9,:  1,9,                   3,11,                   
(非终)3,11,:  1,9,                   3,13,                   
(终态)3,13,:  1,9,15,                   3,17,                   
(终态)1,9,15,:  1,9,15,                   3,11,17,                   
(终态)3,11,17,:  1,9,15,                   3,13,17,                   
(终态)3,13,17,:  1,9,15,                   3,17,                   
(终态)3,17,:  1,9,15,                   3,17,                   
(非终)3,:  1,9,                   3,                   

重命名后：
                   a                 b                 
(非终)0,:  1,                   8,                   
(非终)1,:  1,                   2,                   
(非终)2,:  1,                   3,                   
(终态)3,:  4,                   7,                   
(终态)4,:  4,                   5,                   
(终态)5,:  4,                   6,                   
(终态)6,:  4,                   7,                   
(终态)7,:  4,                   7,                   
(非终)8,:  1,                   8,                   

statenum:4
DFA简化后各个集合中分别包含以下状态
0: 3,4,5,6,7,
1: 0,8,
2: 2,
3: 1,
DFA经简化以及对多状态集合重命名得到:
     a                 b                 
0:  0                   0                   
1:  3                   1                   
2:  3                   0                   
3:  3                   2
https://ideone.com/hp4pee
language:
C++ (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!