Guest User

Untitled

a guest
May 25th, 2019
69
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