API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Aug 17th, 2017
60
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 14.83 KB | None | 0 0
raw download clone embed print report
  1.  
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <string>
  5. #include <queue>
  6. #include <set>
  7.  
  8. using namespace std;
  9.  
  10.  
  11. /*
  12. Funkcija koju poziva ispitni sustav SPPRUT.
  13.  
  14. Nemojte mijenjati:
  15.   - naziv datoteke
  16.   - naziv funkcije
  17.   - broj ulaznih parametara
  18.   - tipove ulaznih parametara
  19.   - tip povratne vrijednosti
  20.  
  21. Ulazni parametri:
  22.   definicijaPA: string s definicijom funkcije prijelaza PA
  23.                 oblikovan prema uputama na FERWebu
  24.   ulazniNiz: string s nizom znakova za koji PA provjerava da li se prihvaca
  25.  
  26. Povratna vrijednost:
  27.   int: 1 ako PA prihvaca niz
  28.        0 ako PA ne prihvaca niz
  29. */
  30.  
  31. int utrlab2(char* definicijaPA, char* ulazniNiz) {
  32.  
  33.     string stanja[50];
  34.     string dPa(definicijaPA);
  35.     string s(dPa.substr(1,dPa.find('%')-1));
  36.  
  37.     int brojac=0;
  38.     string s2;
  39.         for(int i=0;i<s.size();i++){
  40.             if(s[i]==','){
  41.                 stanja[brojac++]=s2;
  42.                 //cout<<"ovo je jedno od svih stanja:"<<s2<<endl;
  43.                 s2.clear();
  44.             }
  45.             else
  46.                 s2+=s[i];
  47.         }
  48.         stanja[brojac++]=s2;
  49.         //cout<<"ovo je jedno od svih stanja:"<<s2<<endl;
  50.     //èitanje drugog reda: dozvoljeni ulazni znakovi
  51.     s.clear();
  52.     s2.clear();
  53.     dPa.erase(0,dPa.find('%'));
  54.     s=dPa.substr(1,dPa.find('%')-1);
  55.  
  56.     int brojac2=0;
  57.     string znak[100];
  58.     for(int i=0;i<s.size();i++){
  59.             if(s[i]==','){
  60.                 znak[brojac2++]=s2;
  61.                 //cout<<"ovo je jedno od svih znakova:"<<s2<<endl;
  62.                 s2.clear();
  63.             }
  64.             else
  65.                 s2+=s[i];
  66.         }
  67.     znak[brojac2++]=s2;
  68.     znak[brojac2++]='$';
  69.     //cout<<"ovo je jedno od svih znakova:"<<s2<<endl;
  70.     // èitanje treæeg reda: sva prihvatljiva stanja
  71.     s.clear();
  72.     s2.clear();
  73.     dPa.erase(0,dPa.find('%'));
  74.     s=dPa.substr(1,dPa.find('%')-1);
  75.  
  76.  
  77.     int brojac3=0;
  78.     string znak_stog[100];
  79.     for(int i=0;i<s.size();i++){
  80.             if(s[i]==','){
  81.                 znak_stog[brojac3++]=s2;
  82.                // cout<<"ovo je jedno od svih Prih stanja:"<<s2<<endl;
  83.                 s2.clear();
  84.             }
  85.             else
  86.                 s2+=s[i];
  87.         }
  88.     znak_stog[brojac3++]=s2;
  89.  
  90.     s.clear();
  91.     s2.clear();
  92.     dPa.erase(0,dPa.find('%'));
  93.     string poc_stanje(dPa.substr(1,dPa.find('%')-1)); // POCETNO STANJE
  94.     dPa.erase(0,dPa.find('%'));
  95.     string DNO(dPa.substr(1,dPa.find('%')-1)); // DNO STOGA
  96.     dPa.erase(0,dPa.find('%'));
  97.     s=dPa.substr(1,dPa.find('%')-1);
  98.  
  99.     int brojac4=0;
  100.     string prih_stanja[100];
  101.     for(int i=0;i<s.size();i++){
  102.             if(s[i]==','){
  103.                 prih_stanja[brojac4++]=s2;
  104.                // cout<<"ovo je jedno od svih Prih stanja:"<<s2<<endl;
  105.                 s2.clear();
  106.             }
  107.             else
  108.                 s2+=s[i];
  109.         }
  110.     prih_stanja[brojac4++]=s2;
  111.  
  112.  
  113.     struct matrica{
  114.     int niz[100];
  115.     string stog[100];
  116.     int br;
  117.     };
  118.  
  119.  
  120.  
  121.     matrica mat[brojac+10][brojac2+10][brojac3+10]; // MATRICA PRIJELAZA stanje, znak, stog znak!
  122.  
  123.     for(int i=0;i<brojac+10;i++)
  124.         for(int j=0;j<brojac2+10;j++)
  125.             for(int k=0;k<brojac3+10;k++)
  126.                 mat[i][j][k].br=0;
  127.  
  128.     s.clear();
  129.     s2.clear();
  130.     //cout<<"TABLICA PRIJELAZA: "<<endl;
  131.     int velicina=dPa.size()-1-dPa.find('%');
  132.     while(velicina>0){
  133.         s.clear();
  134.         s2.clear();
  135.  
  136.         dPa.erase(0,dPa.find('%'));
  137.         velicina=dPa.size()-1;
  138.         s=dPa.substr(1,dPa.find('%')-1);
  139.         if(s.size()==0) continue;
  140.  
  141.         string zn,st;
  142.         int brojac5=0;
  143.         while(s[brojac5++]!=',') //stanje iz kojeg idemo
  144.             s2+=s[brojac5-1];
  145.         zn=s[brojac5];          //ulazni znak
  146.         st=s[brojac5+2];
  147.         brojac5+=5; //pomicemo na sljedece stanje;
  148.  
  149.  
  150.         int x,y,zz, z,z2;
  151.         for(int i=0;i<brojac;i++)
  152.             if(!s2.compare(stanja[i])){
  153.                 x=i;
  154.                 break;
  155.             }
  156.             else if(i==brojac-1 )
  157.                 return 0;
  158.                 //cout<<"1_Stanje ne postoji:"<< s2 <<endl;
  159.         for(int i=0;i<brojac2;i++)
  160.             if(!zn.compare(znak[i])){
  161.                 y=i;
  162.                 break;
  163.             }
  164.             else if(i==brojac2-1)
  165.                 return 0;
  166.                 //cout<<"1_Znak ne postoji"<< zn <<endl;
  167.         for(int i=0;i<brojac3;i++)
  168.             if(!st.compare(znak_stog[i])){
  169.                 zz=i;
  170.                 break;
  171.             }
  172.             else if(i==brojac3-1)
  173.                 return 0;
  174.                 //cout<<"1_Znak ne postoji"<< zn <<endl;
  175.  
  176.         string s3;
  177.         while(brojac5<s.size()){
  178.             if(s[brojac5++]==','){
  179.                 //cout<<"--> "<<s3<<endl;
  180.                 for(int i=0;i<brojac;i++)
  181.                     if(!s3.compare(stanja[i])){
  182.                         z=i;
  183.                         break;
  184.                     }
  185.                     else if(i==brojac-1)
  186.                         return 0;
  187.                             //cout<<"2_Stanje u koje želimo prijeći ne postoji:"<< s3 <<endl;
  188.                 //cout<<"Dosao"<<x <<" "<< y<<" "<< z<< "Brojac brojac2:"<<brojac<<" "<< brojac2<<endl;
  189.                 mat[x][y][zz].niz[mat[x][y][zz].br++]=z; // spremamo u tablicu indekse stanja u koja mozemo prijeci
  190.                 s3.clear();
  191.                 while(s[brojac5++]!='#')
  192.                     s3+=s[brojac5-1];
  193.                 mat[x][y][zz].stog[mat[x][y][zz].br-1]=s3;
  194.                 s3.clear();
  195.             }
  196.             else{
  197.                 s3+=s[brojac5-1]; //ucitavamo stanje u koje prelazimo
  198.  
  199.             }
  200.  
  201.             }
  202.  
  203.         //cout<<"--> "<<s3<<endl;
  204.     /*  SIGURNO CE SVE OBUHVATITI
  205.         for(int i=0;i<brojac;i++)
  206.                     if(!s3.compare(stanja[i])){
  207.                         z=i;
  208.                         break;
  209.                     }
  210.                     else if(i==brojac-1)
  211.                           //  cout<<"3_Stanje u koje želimo prijeći ne postoji:"<< s3 <<endl;
  212.         mat[x][y].niz[mat[x][y].br++]=z; // spremamo u tablicu indekse stanja u koja mozemo prijeci
  213.         s3.clear();*/
  214.  
  215.  
  216.     }
  217.  
  218.  // DO TUDA BI SVE TREBALO BITI OK, SADA UCITAVANJE
  219.  
  220.  
  221.  
  222.         s.clear();
  223.         s2.clear();
  224.         s.assign(ulazniNiz);
  225.  
  226.         struct podre {
  227.  
  228.             string stanje;
  229.             string slovo;
  230.         };
  231.         //friend bool operator==(const pod_red& q1, const pod_red& q2);
  232.         /*pod_red pod_red::operator==(pod_red &other){
  233.             return !stanje.compare(other.stanje) && !slovo.compare(other.slovo);
  234.         }*/
  235.  
  236.         /*bool pod_red::operator==(const pod_red &other) const {
  237.             return !stanje.compare(other.stanje) && !slovo.compare(other.slovo);
  238.         }*/
  239.  
  240.         /*bool operator==(const pod_red& q1, const pod_red& q2){
  241.             if( q1.stanje.compare(q2.stanje) + q1.slovo.compare(q2.slovo)==0)
  242.                 return true;
  243.             else
  244.                 return false;
  245. */
  246.  
  247.          podre pomocni;
  248.  
  249.         queue <podre> red;
  250.  
  251.        /* queue <podre> red_pom;
  252.         pomocni.stanje=poc_stanje;
  253.         pomocni.slovo= DNO;
  254.         red.push(pomocni); // inicijalizacija reda
  255.         red_pom.push(pomocni);
  256.  
  257.  
  258.         int n=1; // brojac kretanja u queue
  259.  
  260.         set <pod_red> kopije;
  261.         kopije.insert(pomocni);
  262.  
  263.         if(s.size()==0) continue; // ?????????????????????????????????????????????? Rijesiti ovo!
  264.  
  265.         //cout<<"\nULAZNI NIZ: "<<s<<endl;
  266.         //cout<<"Pocetno stanje >>> "<<poc_stanje<<" <<<"<<endl;
  267.  
  268.         string zn="$";
  269.         while(!red_pom. empty()){
  270.             string s3,s33;
  271.             pomocni=red_pom.front();
  272.             s3=pomocni.stanje;
  273.             s33=pomocni.slovo;
  274.             red_pom.pop();
  275.             int x,y,z;
  276.  
  277.             for(int i=0;i<brojac;i++) // trazenje stanja, zatim znaka
  278.                 if(!s3.compare(stanja[i])){
  279.                     x=i;
  280.                     break;
  281.                 }
  282.                 else if(i==brojac-1)
  283.                     return 0;
  284.                     cout<<"5_Stanje ne postoji:"<< s2 <<endl;
  285.  
  286.             for(int i=0;i<brojac3;i++) // trazenje stanja, zatim znaka
  287.                 if(!s33.compare(znak_stog[i])){
  288.                     z=i;
  289.                     break;
  290.                 }
  291.                 else if(i==brojac3-1)
  292.                     return 0;
  293.                     cout<<"5_Stanje ne postoji:"<< s2 <<endl;
  294.  
  295.  
  296.             int prov=0;
  297.             for(int i=0;i<brojac2;i++)
  298.                 if(!zn.compare(znak[i])){
  299.                     y=i;
  300.                     break;
  301.                 }
  302.                 else if(i==brojac2-1){
  303.                     cout<<"Nema epsilon prijelaza iz pocetnog stanja "<<endl;
  304.                     prov=1;
  305.                 }
  306.             if(prov) continue;
  307.  
  308.             for(int i=0;i<mat[x][y][z].br;i++){ // dodajemo stanja u red
  309.                 pomocni.stanje=stanja[mat[x][y][z].niz[i]];
  310.                 pomocni.slovo= mat[x][y][z].stog[i];
  311.  
  312.                 set <pod_red>::iterator it;
  313.                 int pp=0;
  314.                 for(it=kopije.begin();it!=kopije.end;it++){
  315.                     if(!pomocni.stanje.compare(it*.stanje) && !pomocni.slovo.compare(it*.slovo)){
  316.                         pp=1;
  317.                         break;
  318.                     }
  319.                 }
  320.  
  321.                 if(pp) // nasao ga je! To je duplic! Ne dodajemo
  322.                     continue;
  323.  
  324.                 kopije.insert(pomocni);
  325.                 red.push(pomocni);
  326.                 red_pom.push(pomocni);
  327.                 n++;
  328.                 cout<<"Epsilon prijelaz:  "<<stanja[mat[x][y].niz[i]]  << endl;
  329.  
  330.             }
  331.  
  332.         }
  333.  
  334.  
  335.         int x,y,pomocna,prihvaceno=0,greska=0;
  336.         for(int k=0;k<s.size();k++){
  337.             zn=s[k];
  338.             kopije.clear();
  339.             cout<<">>Citam novi znak: (  "<<zn<<"  )"<<endl;
  340.             pomocna=0;
  341.             for(int j=0;j<n;j++){
  342.                 s2=red.front();
  343.                 red.pop();
  344.                 //cout<< "IZ ovog stanja idemo "<<s2<<endl;
  345.  
  346.                 for(int i=0;i<brojac;i++) // trazenje stanja, zatim znaka
  347.                     if(!s2.compare(stanja[i])){
  348.                         x=i;
  349.                         break;
  350.                     }
  351.                     else if(i==brojac-1)
  352.                         cout<<"Stanje ne postoji:"<< s2 <<endl;
  353.  
  354.                 for(int i=0;i<brojac2;i++)
  355.                     if(!zn.compare(znak[i])){
  356.                         y=i;
  357.                         break;
  358.                     }
  359.                     else if(i==brojac2-1){
  360.                         if(zn.compare(" ")){
  361.                             cout<<"Znak ne postoji! >>> "<< zn <<endl;
  362.                             greska=1;
  363.                         }
  364.                         else{
  365.                             zn="$";
  366.                             for(int ii=0;ii<brojac2;ii++)
  367.                                 if(!zn.compare(znak[ii])){
  368.                                 y=ii;
  369.                                 break;
  370.                         }
  371.                         string s5;
  372.                         s5=stanja[mat[x][y].niz[i]];
  373.                         for(int m=0;m<brojac3;m++)
  374.                             if(!prih_stanja[m].compare(s5)){
  375.                                 prihvaceno=1;
  376.                                 break;
  377.                             }
  378.  
  379.                         }
  380.                     }
  381.                 if(greska) break;
  382.                 //cout<<"pomocna prije: "<<pomocna<<endl;
  383.                 pomocna+=mat[x][y].br;
  384.                 //cout<<"pomocna poslije: "<<pomocna<<endl;
  385.                 for(int i=0;i<mat[x][y].br;i++){ // dodajemo stanja u red
  386.                     if(kopije.find(stanja[mat[x][y].niz[i]])!=kopije.end()){ // nasao ga je! To je duplic! Ne dodajemo
  387.                         pomocna--;
  388.                         continue;
  389.                     }
  390.                     kopije.insert(stanja[mat[x][y].niz[i]]);
  391.                     red.push(stanja[mat[x][y].niz[i]]);
  392.                     red_pom.push(stanja[mat[x][y].niz[i]]);
  393.                     cout<<"Prelazim -->"<<stanja[mat[x][y].niz[i]]  << endl;
  394.                     if(k==s.size()-1){
  395.                         //cout<<"Usli smo u zadnje stanje"<<endl;
  396.                         string s5;
  397.                         s5=stanja[mat[x][y].niz[i]];
  398.                         for(int m=0;m<brojac3;m++)
  399.                             if(!prih_stanja[m].compare(s5)){
  400.                                 prihvaceno=1;
  401.                                 break;
  402.                             }
  403.  
  404.                     }
  405.                 }
  406.  
  407.             }
  408.             if(greska) break;
  409.             n=pomocna;
  410.  
  411.             zn='$';
  412.             while(!red_pom.empty()){
  413.                 string s3;
  414.                 s3=red_pom.front();
  415.                 red_pom.pop();
  416.                 int x,y;
  417.  
  418.                 for(int i=0;i<brojac;i++) // trazenje stanja, zatim znaka
  419.                     if(!s3.compare(stanja[i])){
  420.                         x=i;
  421.                         break;
  422.                     }
  423.                     else if(i==brojac-1)
  424.                         cout<<"Stanje ne postoji:"<< s2 <<endl;
  425.                 int prov=0;
  426.                 for(int i=0;i<brojac2;i++)
  427.                     if(!zn.compare(znak[i])){
  428.                         y=i;
  429.                         break;
  430.                     }
  431.                     else if(i==brojac2-1){
  432.                         //cout<<"Nema epsilon prijelaza "<< zn <<endl;
  433.                         prov=1;
  434.                     }
  435.                 if(prov) continue;
  436.  
  437.                 for(int i=0;i<mat[x][y].br;i++){ // dodajemo stanja u red
  438.                     if(kopije.find(stanja[mat[x][y].niz[i]])!=kopije.end()) // nasao ga je! To je duplic! Ne dodajemo
  439.                         continue;
  440.  
  441.                     kopije.insert(stanja[mat[x][y].niz[i]]);
  442.                     red.push(stanja[mat[x][y].niz[i]]);
  443.                     red_pom.push(stanja[mat[x][y].niz[i]]);
  444.                     n++;
  445.                     cout<<"Epsilon prijelaz:  "<<stanja[mat[x][y].niz[i]]  << endl;
  446.  
  447.                     if(k==s.size()-1){
  448.                         //cout<<"Usli smo EPSILON prijelazom u jedno od zadnjih stanja"<<endl;
  449.                         string s5;
  450.                         s5=stanja[mat[x][y].niz[i]];
  451.                         for(int m=0;m<brojac3;m++)
  452.                             if(!prih_stanja[m].compare(s5)){
  453.                                 prihvaceno=1;
  454.                                 break;
  455.                             }
  456.  
  457.                     }
  458.                 }
  459.  
  460.             }
  461.         }
  462.         if(prihvaceno) cout<<"PRIHVACA se ulazni niz"<<endl;
  463.             else cout<<"NE PRIHVACA se ulazni niz"<<endl;
  464.  
  465.  
  466.  
  467.  
  468.  
  469.  
  470.  
  471.  
  472. */
  473.  
  474.  
  475.  
  476.  
  477.  
  478.  
  479.  
  480.  
  481.  
  482.   return 1;
  483. }
  484.  
  485.  
  486.  
  487. int main(){
  488.     char def[100], ulaz[100];
  489.     scanf("%s %s", def,ulaz);
  490.  
  491.     printf("Rjesenje: %d",utrlab2( def,  ulaz));
  492.  
  493. return 0;
  494. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!