最一般合一算法C++版

/*×îÒ»°ãºÏÒ»(mgu)Ë㷨ʵÏÖ*/#includeiostream#includestring#includevectorusingnamespacestd;structtransform//Ò»×éÖû»{stringt_f1;stringt_f2;};//º¯ÊýÉùÃ÷boolsame(conststringf1,conststringf2);transformdif(conststringf1,conststringf2);stringchange(stringf,transformq);stringchange2(stringf,transformq);boolsyncretism(conststringf1,conststringf2,vectortransform&);intlegal(transform&);boolvar(conststrings);stringvarData(strings);intmain(){coutconst:capital\tvarible:lowercase.endl;//ÊäÈëÁ½¸öν´Ê¹«Ê½stringf1,f2;coutintputF1:;cinf1;coutintputF2:;cinf2;vectortransformmgu;if(syncretism(f1,f2,mgu))//´æÔÚ×îÒ»°ãºÏÒ»£¬²¢Êä³ö½á¹û{coutmgu={;inti=0;for(i=0;imgu.size()-1;i++)coutmgu[i].t_f1/mgu[i].t_f2,;coutmgu[i].t_f1/mgu[i].t_f2}endl;}else//²»´æÔÚ×îÒ»°ãºÏÒ»{coutcannotbesyncretizedendl;}return0;}boolsyncretism(conststringtf1,conststringtf2,vectortransform&mgu)//ºÏÒ»·½·¨£¬ÅжÏÊÇ·ñ¿É½øÐкÏÒ»{stringf1=tf1,f2=tf2;while(!same(f1,f2))//f1Óëf2ÖеķûºÅ²»ÍêÈ«Ïàͬʱ²Å½øÈëwhileÑ­»·{transformt=dif(f1,f2);//µÃµ½f1ºÍf2µÄÒ»¸ö²îÒ켯£¬²¢°ÑËü¸³¸øtintflag=legal(t);if(flag==0)returnfalse;else{mgu.push_back(t);f1=change(f1,mgu.back());f2=change(f2,mgu.back());coutafterchange:endl;coutf1:f1endl;coutf2:f2endl;if(same(f1,f2))break;//f1ºÍf2Ïàͬʱ¾Íֹͣѭ»·}}returntrue;}boolsame(conststringf1,conststringf2)//ÅжÏÁ½¸öν´Êf1ºÍf2ÊÇ·ñÏàͬ{if(f1.length()==f2.length()){inti=0;while(if1.length()&&f1.at(i)==f2.at(i))i++;if(i==f1.length())returntrue;else{returnfalse;}}elsereturnfalse;}transformdif(conststringf1,conststringf2)//Çó½âf1ºÍf2µÄ²îÒ켯{inti=0;transformt;while(f1.at(i)==f2.at(i))//µÚi¸öÏàµÈʱ¾ÍתÏò±È½Ïi+1£¬Ö±µ½Óöµ½²»ÏàµÈʱ¾ÍÌø³öwhileÑ­»·i++;intj1=i;while(j1f1.length()-1&&f1.at(j1)!=',')//´Ó²»ÏàµÈµÄ²¿·Ö¿ªÊ¼£¬Ö±µ½Óöµ½¡®£¬¡¯»òµ½´ï½áβʱÌø³öwhileÑ­»·j1++;if(j1-i==0)returnt;t.t_f1=f1.substr(i,j1-i);//½«f1ÖеIJ»ÏàͬµÄÏî½ØÈ¡³öÀ´·ÅÈë±äÁ¿t.t_f1ÖÐintj2=i;while(j2f2.length()-1&&f2.at(j2)!=',')j2++;if(j2-i==0)returnt;t.t_f2=f2.substr(i,j2-i);//½«f2ÖеIJ»ÏàͬµÄÏî½ØÈ¡³öÀ´·ÅÈë±äÁ¿t.t_f2ÖÐwhile(t.t_f1[j1-i-1]==t.t_f2[j2-i-1])//È¥³ýÏàͬµÄ²¿·Ö{t.t_f1.erase(j1-1-i);t.t_f2.erase(j2-i-1);j1--;j2--;}returnt;}intlegal(transform&t)//ÅжÏÖû»tÊÇ·ñºÏ·¨{if(t.t_f1.length()==0||t.t_f2.length==0)return0;if(var(t.t_f2)){if(var(t.t_f1)&&(varData(t.t_f1)==varData(t.t_f2)))//²»ÄÜ´ú»»ºÏÒ»return0;elsereturn2;}if(!var(t.t_f1))//Èôt_f1ºÍt_f2¶¼²»ÊDZäÁ¿£¬Ò²²»ÄܺÏÒ»return0;stringtemp;temp=t.t_f1;t.t_f1=t.t_f2;t.t_f2=temp;//ÔÚt_f1ÊDZäÁ¿¶øt_f2²»ÊDZäÁ¿µÄÇé¿öÏ£¬½»»»t_f1ºÍt_f2return1;}stringvarData(strings)//¸Ãº¯ÊýÊÇ°þÈ¥Íâ²ãÀ¨ºÅ{if(s.length()==1||s.length()==0)returns;if(s.length()1){inti=0;while(is.length()&&s.at(i)!='(')i++;intj=i;while(js.length()&&s.at(j)!=')')j++;stringss=s.substr(i+1,j-i-1);returnvarData(ss);}else{returnfalse;}}boolvar(conststrings){if(s.length()==0)returnfalse;if(s.length()==1&&s[0]='A'&&s[0]='Z')returnfalse;if(s.length()1){inti=0;while(is.length()&&s.at(i)!='(')//ÂÔ¹ý²»ÊÇ'('µÄ×Ö·ûi++;intj=i;while(js.length()&&s.at(j)!=')')//ÂÔ¹ý')'Ç°µÄ×Ö·ûj++;stringss=s.substr(i+1,j-i-1);//È¡³ö'('ºÍ')'Ö®¼äµÄ´®returnvar(ss);//µÝ¹éµ÷ÓÃvar}else{returntrue;}}stringchange(stringf,transformq)//¸Ãº¯Êý²éÕÒt_f2ÔÚfÖеÄλÖò¢ÓÃt_f1Ìæ´úfÖÐÏàÓ¦µÄt_f2{inti=f.find(q.t_f2);while(if.length()){i=f.find(q.t_f2);if(if.length())f=f.replace(i,q.t_f2.length(),q.t_f1);}returnf;}