SHARE
TWEET

Untitled

a guest May 25th, 2019 65 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #include <fstream>
  3. using namespace std;
  4. ifstream f("minerale.in");
  5. ofstream g("minerale.out");
  6. string a,b,s;
  7. int n;
  8. map <string, set<string> > terminal;
  9. map <string, set<string> > non_terminal;
  10. set <string> d[105][105];
  11. map <string,tuple<int,int,string,int,int,string> >mp[105][105];
  12. queue < tuple<int,int,string,int> >coada;
  13. map <tuple<int, int, string>, vector<tuple<int, int, string> > > v;
  14.  
  15. void dfs(tuple<int, int, string> s, tuple<int,int,string,int,int,string> a, string OP) {
  16.     v[s].push_back(make_tuple(get<0>(a), get<1>(a), get<2>(a)));
  17.     v[s].push_back(make_tuple(get<3>(a), get<4>(a), get<5>(a)));
  18.     tuple<int, int, string> left = make_tuple(get<0>(a), get<1>(a), get<2>(a));
  19.     tuple<int, int, string> right = make_tuple(get<3>(a), get<4>(a), get<5>(a));
  20.     string name_left = get<2>(a);
  21.     string name_right = get<5>(a);
  22.     if (get<0>(a) == 1)
  23.         v[left].push_back(make_tuple(-1, -1, name_left));
  24.     else dfs(left, mp[get<0>(a)][get<1>(a)][name_left], OP);
  25.     if (get<3>(a) == 1)
  26.         v[right].push_back(make_tuple(-1, -1, name_right));
  27.     else dfs(right, mp[get<3>(a)][get<4>(a)][name_right], OP);
  28. }
  29.  
  30. bool cyk(string s)
  31. {
  32.     int i,j,k;
  33.     for(i=1;i<=n;i++)
  34.     {
  35.         string aux="";
  36.         aux+=s[i-1];
  37.         if(!terminal[aux].empty())
  38.         {
  39.             d[1][i]=terminal[aux];
  40.         }
  41.     }
  42.     for(i=2;i<=n;i++)
  43.     {
  44.         for(j=1;j<=n-i+1;j++)
  45.         {
  46.             for(k=1;k<=i-1;k++)
  47.             {
  48.                 for(auto it1 : d[k][j])
  49.                 {
  50.                     for(auto it2 : d[i-k][j+k])
  51.                     {
  52.                         string aux="";
  53.                         aux+=it1;
  54.                         aux+=it2;
  55.                         for(auto it3: non_terminal[aux])
  56.                         {
  57.                             d[i][j].insert(it3);
  58.                             mp[i][j][it3]=make_tuple(k,j,it1,i-k,j+k,it2);
  59.                         }
  60.                     }
  61.                 }
  62.             }
  63.         }
  64.     }
  65.     /*for(i=1;i<=n;i++)
  66.     {
  67.         for(j=1;j<=n-i+1;j++)
  68.         {
  69.             cout<<"[";
  70.             for(auto it : d[i][j])
  71.             {
  72.                 cout<<it<<" ";
  73.             }
  74.             cout<<"] ";
  75.         }
  76.         cout<<"\n";
  77.     }
  78.     */
  79.     //string aux="";
  80.     //aux+='S';
  81.     //cout<<get<0>(mp[n][1][aux])<<" "<<get<1>(mp[n][1][aux])<<" "<<get<2>(mp[n][1][aux])<<" "<<get<3>(mp[n][1][aux])<<" "<<get<4>(mp[n][1][aux])<<" "<<get<5>(mp[n][1][aux]);
  82.     if(d[n][1].find("S")!=d[n][1].end())
  83.     {
  84.         dfs(make_tuple(n, 1, "S"), mp[n][1]["S"], s);
  85.           return 1;
  86.     }
  87.     else
  88.     {
  89.         return 0;
  90.     }
  91. }
  92. int main()
  93. {
  94.     int i;
  95.     f>>n;
  96.     for(i=1;i<=n;i++)
  97.     {
  98.         f>>a>>b;
  99.         if(b.size()==2)
  100.         {
  101.             non_terminal[b].insert(a);
  102.         }
  103.         else
  104.         {
  105.             terminal[b].insert(a);
  106.         }
  107.     }
  108.     f>>s;
  109.     n=s.size();
  110.     if(cyk(s)==0)
  111.     {
  112.         cout<<"Cuvantul nu poate fi generat de gramatica";
  113.     }
  114.     else
  115.     {
  116.        
  117.     }
  118.     return 0;
  119. }
RAW Paste Data
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
 
Top