API tools faq
paste
Advertisement
Guest User

Turner

a guest
Jun 26th, 2017
64
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 16.00 KB | None | 0 0
raw download clone embed print report
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <time.h>
  5. /*
  6.  *
  7.  */
  8. int quantidade=0;
  9. char fonte[100000000];
  10. char destino[100000000];
  11.  
  12. int contador(char vetor[], int i)
  13. {
  14.  
  15.     int conta_parenteses=0;
  16.     int posicao=i;
  17.  
  18.     if(vetor[posicao]=='(')
  19.     {
  20.         conta_parenteses++;
  21.  
  22.         while(conta_parenteses!=0)
  23.         {
  24.             posicao++;
  25.             if(vetor[posicao]=='(')
  26.             {
  27.                 conta_parenteses++;
  28.             }
  29.             if(vetor[posicao]==')')
  30.             {
  31.                 conta_parenteses--;
  32.             }
  33.         }
  34.  
  35.     }
  36.     return posicao;
  37. }
  38. // I a => a
  39. void RegraI(char *inicio, char *fim)
  40. {
  41.     int posicao=contador(inicio,1);
  42.     memmove(fim,inicio+1,posicao);
  43.     memmove(fim+posicao,inicio+(posicao+1),strlen(inicio));
  44.  
  45. }
  46. // C a b c => a c b
  47. void RegraC( char *inicio, char *fim)
  48. {
  49.     int quant= strlen(inicio);
  50.     int pos_f= contador(inicio,1);
  51.     int pos_x= contador(inicio,pos_f+1);
  52.     int pos_y= contador(inicio, pos_x+1);
  53.     int resto=0;
  54.     int quant_resto=0;
  55.     if(pos_y+1!=quant-1)
  56.     {
  57.         quant_resto= quant- (pos_y+1);
  58.         resto=pos_y+1;
  59.  
  60.     }
  61.  
  62.  
  63.  
  64.  
  65.     int quan_x=pos_x-pos_f;
  66.     int quan_y=pos_y-pos_x;
  67.     quant=quan_x+quan_y+pos_f+ quant_resto;
  68.  
  69.     memmove(fim,inicio+1,pos_f);
  70.     memmove(fim+pos_f,inicio+(pos_x+1),quan_y);
  71.     memmove(fim+(pos_f+quan_y),inicio+(pos_f+1),quan_x);
  72.     memmove(fim+(pos_f+quan_y+quan_x),inicio+resto,strlen(inicio));
  73.  
  74.  
  75. }
  76. // B a b c => a (bc)
  77. void RegraB(char *inicio, char*fim)
  78. {
  79.     int quant= strlen(inicio);
  80.     int pos_f= contador(inicio,1);
  81.     int pos_g= contador(inicio,pos_f+1);
  82.     int pos_x= contador(inicio, pos_g+1);
  83.     int quant_resto=0;
  84.     int resto=0;
  85.     if(pos_x+1!=quant-1)
  86.     {
  87.         quant_resto=quant -(pos_x+1);
  88.         resto=pos_x+1;
  89.     }
  90.  
  91.  
  92.  
  93.  
  94.  
  95.  
  96.     int quan_x=pos_x-pos_g;
  97.     int quan_g=pos_g-pos_f;
  98.     quant=quan_x+quan_g+pos_f+ quant_resto+2;
  99.  
  100.     memmove(fim,inicio+1,pos_f);
  101.     fim[pos_f]='(';
  102.     memmove(fim+(pos_f+1),inicio+(pos_f+1),quan_g);
  103.     memmove(fim+(pos_f+1+quan_g),inicio+(pos_g+1),quan_x);
  104.     fim[pos_f+1+quan_g+quan_x]=')';
  105.     memmove(fim+(pos_f+1+quan_x+quan_g+1),inicio+resto,strlen(inicio));
  106.  
  107.  
  108. }
  109. //regra S' renomeada  a b c d => a (bd)(cd)
  110. void RegraQ(char *inicio, char *fim)
  111. {
  112.     int quant= strlen(inicio);
  113.     int pos_a= contador(inicio,1);
  114.     int pos_b= contador(inicio,pos_a+1);
  115.     int pos_c= contador(inicio, pos_b+1);
  116.     int pos_d= contador(inicio, pos_c+1);
  117.     int resto=0;
  118.     int quan_resto=0;
  119.     if(pos_d+1!=quant-1)
  120.     {
  121.         quan_resto=(quant)- (pos_d+1);
  122.         resto=pos_d+1;
  123.     }
  124.  
  125.  
  126.  
  127.  
  128.  
  129.  
  130.     int quan_b=pos_b-pos_a;
  131.     int quan_c=pos_c-pos_b;
  132.     int quan_d=pos_d-pos_c;
  133. //a b c d => a (bd)(cd)
  134.     quant=quan_c+quan_b+pos_a+ quan_resto+quan_d+4+quan_c+quan_d;
  135.  
  136.     memmove(fim, inicio+1,pos_a);
  137.     fim[pos_a]='(';
  138.     memmove(fim+(pos_a+1),inicio+(pos_a+1),quan_b);
  139.     memmove(fim+(pos_a+1+quan_b),inicio+(pos_c+1),quan_d);
  140.     fim[pos_a+1+quan_b+quan_d]=')';
  141.     fim[pos_a+1+quan_b+quan_d+1]='(';
  142.     memmove(fim+(pos_a+1+quan_b+quan_d+2),inicio+(pos_b+1),quan_c);
  143.     memmove(fim+(pos_a+1+quan_b+quan_d+2+quan_c),inicio+(pos_c+1),quan_d);
  144.     fim[pos_a+1+quan_b+quan_d+2+quan_c+quan_d]=')';
  145.     memmove(fim+(pos_a+1+quan_b+quan_d+2+quan_c+quan_d+2),inicio+resto,strlen(inicio));
  146.     /*
  147.         for(i=0;i<=quant;i++){
  148.             if(i<pos_a){
  149.                 destino[i]=vetor[j];
  150.             }
  151.             else if (i==pos_a) destino[i]='(';
  152.             else if(i<pos_a+quan_b+1) {
  153.                     destino[i]=vetor[con_b];
  154.                     con_b++;
  155.                     }
  156.                 else if(i<pos_a+quan_b+quan_d+1) {
  157.                     destino[i]=vetor[con_d];
  158.                        con_d++;
  159.                             }
  160.                             else if(i==pos_a+quan_b+quan_d+1){
  161.                               destino[i]=')';
  162.                               con_c=pos_b+1;
  163.                               con_d=pos_c+1;
  164.                             }
  165.                             else if(i==pos_a+quan_b+quan_d+2){
  166.                               destino[i]='(';
  167.                             }
  168.                              else if(i<=pos_a+quan_b+quan_d+2+quan_c){
  169.                               destino[i]=vetor[con_c];
  170.                               con_c++;
  171.  
  172.                              }
  173.                               else if(i<=pos_a+quan_b+quan_d+2+quan_c+quan_d){
  174.                               destino[i]=vetor[con_d];
  175.                               con_d++;
  176.                             }
  177.                              else if(i==pos_a+quan_b+quan_d+2+quan_c+quan_d+1){
  178.                               destino[i]=')';
  179.                              }
  180.  
  181.                             else{
  182.                                     if(resto!=0){
  183.                                 destino[i]=vetor[resto];
  184.                                 resto++;
  185.                                     }
  186.  
  187.                             }
  188.  
  189.             j++;
  190.         }
  191.         destino[quant+1]='\0';
  192.     */
  193. }
  194. //regra B' renomeada a b c d => a b (c d)
  195. void RegraW (char *inicio, char *fim)
  196. {
  197.     int quant= strlen(inicio);
  198.     int pos_a= contador(inicio,1);
  199.     int pos_b= contador(inicio,pos_a+1);
  200.     int pos_c= contador(inicio, pos_b+1);
  201.     int pos_d= contador(inicio, pos_c+1);
  202.     int resto=0;
  203.     int quan_resto=0;
  204.     if(pos_d+1!=quant-1)
  205.     {
  206.         quan_resto=(quant)- (pos_d+1);
  207.         resto=pos_d+1;
  208.     }
  209.  
  210.  
  211.  
  212.  
  213.  
  214.     int quan_b=pos_b-pos_a;
  215.     int quan_c=pos_c-pos_b;
  216.     int quan_d=pos_d-pos_c;
  217.  
  218.     quant=quan_c+quan_b+pos_a+ quan_resto+quan_d+2;
  219. // a b c d => a b (c d)
  220.  
  221.  
  222.     memmove(fim, inicio+1,pos_a);
  223.     memmove(fim+pos_a,inicio+(pos_a+1),quan_b);
  224.     fim[pos_a+quan_b]='(';
  225.     memmove(fim+(pos_a+quan_b+1),inicio+(pos_b+1),quan_c);
  226.     memmove(fim+(pos_a+quan_b+1+quan_c),inicio+(pos_c+1),quan_d);
  227.     fim[pos_a+quan_b+1+quan_c+1]=')';
  228.     memmove(fim+(pos_a+quan_b+1+quan_c+2),inicio+resto,strlen(inicio));
  229.  
  230.     /*
  231.         for(i=0;i<=quant;i++){
  232.             if(i<pos_a){
  233.                 destino[i]=vetor[j];
  234.             }
  235.             else if(i<pos_a+quan_b) {
  236.                     destino[i]=vetor[con_b];
  237.                     con_b++;
  238.                     }
  239.                      else if(i==pos_a+quan_b){
  240.                            destino[i]='(';
  241.                      }
  242.                 else if(i<=pos_a+quan_b+quan_c) {
  243.                     destino[i]=vetor[con_c];
  244.                        con_c++;
  245.                             }
  246.  
  247.                               else if(i<=pos_a+quan_b+quan_c+quan_d){
  248.                               destino[i]=vetor[con_d];
  249.                               con_d++;
  250.                             }
  251.                              else if(i==pos_a+quan_b+quan_d+quan_c+1){
  252.                               destino[i]=')';
  253.                              }
  254.  
  255.                             else{
  256.                                     if(resto!=0){
  257.                                 destino[i]=vetor[resto];
  258.                                 resto++;
  259.                                     }
  260.  
  261.                             }
  262.  
  263.             j++;
  264.         }
  265.         destino[quant+1]='\0';
  266.     */
  267.  
  268. }
  269.  
  270. //C’ a b c d => a (b d) c
  271. void RegraE (char *inicio, char*fim)
  272. {
  273.     int quant= strlen(inicio);
  274.     int pos_a= contador(inicio,1);
  275.     int pos_b= contador(inicio,pos_a+1);
  276.     int pos_c= contador(inicio, pos_b+1);
  277.     int pos_d= contador(inicio, pos_c+1);
  278.     int resto=0;
  279.     int quan_resto=0;
  280.     if(pos_d+1!=quant-1)
  281.     {
  282.         quan_resto=(quant)- (pos_d+1);
  283.         resto=pos_d+1;
  284.     }
  285.  
  286.  
  287.     int i;
  288.     int j=1;
  289.     int con_b=pos_a+1;
  290.     int con_c=pos_b+1;
  291.     int con_d=pos_c+1;
  292.     int quan_b=pos_b-pos_a;
  293.     int quan_c=pos_c-pos_b;
  294.     int quan_d=pos_d-pos_c;
  295.  
  296.     quant=quan_c+quan_b+pos_a+ quan_resto+quan_d+2;
  297.  
  298. //C’ a b c d => a (b d) c
  299.     memmove(fim,inicio+1,pos_a);
  300.     fim[pos_a]='(';
  301.     memmove(fim+(pos_a+1),inicio+(pos_a+1),quan_b);
  302.     memmove(fim+(pos_a+1+quan_b),inicio+(pos_c+1),quan_d);
  303.     fim[pos_a+1+quan_b+quan_d]=')';
  304.     memmove(fim+(pos_a+1+quan_b+quan_d+1),inicio+(pos_b+1),quan_c);
  305.     memmove(fim+(pos_a+1+quan_b+quan_d+1+quan_c),inicio+resto,strlen(inicio));
  306.  
  307.     /*
  308.         for(i=0;i<=quant;i++){
  309.             if(i<pos_a){
  310.                 destino[i]=vetor[j];
  311.             }
  312.               else if(i==pos_a){
  313.                            destino[i]='(';
  314.                      }
  315.             else if(i<=pos_a+quan_b) {
  316.                     destino[i]=vetor[con_b];
  317.                     con_b++;
  318.                     }
  319.  
  320.                 else if(i<=pos_a+quan_b+quan_d) {
  321.                     destino[i]=vetor[con_d];
  322.                        con_d++;
  323.                             }
  324.                  else if(i==pos_a+quan_b+quan_d+1){
  325.                               destino[i]=')';
  326.                              }
  327.                               else if(i<=pos_a+quan_b+quan_c+quan_d+1){
  328.                               destino[i]=vetor[con_c];
  329.                               con_c++;
  330.                             }
  331.  
  332.  
  333.                             else{
  334.                                     if(resto!=0){
  335.                                 destino[i]=vetor[resto];
  336.                                 resto++;
  337.                                     }
  338.  
  339.                             }
  340.  
  341.             j++;
  342.         }
  343.         destino[quant+1]='\0';
  344.     */
  345. }
  346.  
  347. //K a b => a
  348. void RegraK(char *inicio, char *fim)
  349. {
  350.     int quant= strlen(inicio);
  351.     int pos_a= contador(inicio,1);
  352.     int pos_b= contador(inicio,pos_a+1);
  353.     int quant_resto=0;
  354.     int resto=0;
  355.     if(pos_b+1!=quant-1)
  356.     {
  357.         quant_resto=quant -(pos_b+1);
  358.         resto=pos_b+1;
  359.     }
  360.  
  361.  
  362.     int i;
  363.     int j=1;
  364.     int con_a=pos_a+1;
  365.     int con_b=pos_b+1;
  366.     int quan_b=pos_b-pos_a;
  367.     quant=quan_b+pos_a+ quant_resto;
  368.  
  369.     if(pos_a!=0 &&quan_b!=0)
  370.     {
  371.  
  372.         memmove(fim,inicio+1,pos_a);
  373.  
  374.         memmove(fim+pos_a,inicio+resto,strlen(inicio));
  375.  
  376.     }
  377.     else
  378.     {
  379.         quantidade=1;
  380.     }
  381. }
  382. //S a b c => ac(bc)
  383. void RegraS(char *inicio, char*fim)
  384. {
  385.     int quant= strlen(inicio);
  386.     int pos_a= contador(inicio,1);
  387.     int pos_b= contador(inicio,pos_a+1);
  388.     int pos_c= contador(inicio, pos_b+1);
  389.     int quant_resto=0;
  390.     int resto=0;
  391.     if(pos_c+1!=quant-1)
  392.     {
  393.         quant_resto=quant -(pos_c+1);
  394.         resto=pos_c+1;
  395.     }
  396.  
  397.  
  398.     int i;
  399.     int j=1;
  400.     int con_b=pos_a+1;
  401.     int con_c=pos_b+1;
  402.     int quan_b=pos_b-pos_a;
  403.     int quan_c=pos_c-pos_b;
  404.     quant=quan_b+quan_c+pos_a+ quant_resto+2+quan_c;
  405.  
  406.     if(pos_a!=0 &&quan_b!=0&&quan_c!=0)
  407.     {
  408.  
  409.         memmove(fim,inicio+1,pos_a);
  410.         memmove(fim+pos_a,inicio+(pos_b+1),quan_c);
  411.         fim[pos_a+quan_c]='(';
  412.         memmove(fim+(pos_a+quan_c+1),inicio+pos_a+1,quan_b);
  413.         memmove(fim+(pos_a+quan_b+quan_c+1) ,inicio+(pos_b+1),quan_c);
  414.         fim[pos_a+quan_b+quan_c+1+quan_c]=')';
  415.         memmove(fim+(pos_a+quan_b+quan_c+1+quan_c+1),inicio+resto,strlen(inicio));
  416.  
  417.     }
  418.     else
  419.     {
  420.         quantidade=1;
  421.     }
  422.  
  423. }
  424.  
  425. void eliminar_parenteses(char *vetor,char *fvetor)
  426. {
  427.  
  428.     int abreparenteses=0;
  429.     int i,t;
  430.     i=0;
  431.     t=1;
  432.     if(vetor[0]=='(')
  433.     {
  434.         abreparenteses++;
  435.         while(abreparenteses!=0)
  436.         {
  437.             if(vetor[t]==')')
  438.             {
  439.                 abreparenteses--;
  440.             }
  441.             if(vetor[t]=='(')
  442.             {
  443.                 abreparenteses++;
  444.             }
  445.             if(abreparenteses!=0)
  446.             {
  447.                 i++;
  448.                 t++;
  449.             }
  450.         }
  451.     }
  452.     t++;
  453.     memmove(fvetor,vetor+1,i);
  454.     memmove(fvetor+i,vetor+t,strlen(vetor));
  455.  
  456. }
  457.  
  458.  
  459.  
  460.  
  461. int main(int argc, char** argv)
  462. {
  463.  
  464.  char * build_pattern(int n, char *input)
  465.     {
  466.         char y[] ="Q(EBI(SII))I(B(EBI(SII))I)";
  467.         int y_len = 77;
  468.         int pattern_length = 0;
  469.         int pattern_size = 6;
  470.         if (n > 0)
  471.         {
  472.             pattern_size += 6 * (n - 1);
  473.         }
  474.         char *pattern = (char*)malloc(pattern_size * sizeof(char*)); /*  Aloca��o do padr�o (ATEN��O TAMANHO)
  475.         //int input_size = ((pattern_size - n) + (n*y_len) + 1) * n * n;
  476.         //char *input = (char*) malloc(input_size * sizeof(char)); // Aloca��o de entrada (ATEN��O TAMANHO)*/
  477.  
  478.  
  479.         int i,j;
  480.         for (i = 0; i < n; i++)
  481.         {
  482.             pattern[pattern_length++] = 'Y';
  483.             pattern[pattern_length++] = '(';
  484.             pattern[pattern_length++] = '(';
  485.         }
  486.         pattern[pattern_length++] = 'Y';
  487.         pattern[pattern_length++] = '(';
  488.         pattern[pattern_length++] = 'K';
  489.         pattern[pattern_length++] = 'K';
  490.         pattern[pattern_length++] = ')';
  491.  
  492.         for ( i = 0; i < n; i++)
  493.         {
  494.             pattern[pattern_length++] = ')';
  495.             pattern[pattern_length++] = 'K';
  496.             pattern[pattern_length++] = ')';
  497.         }
  498.  
  499.         pattern[pattern_length++] = '\0';
  500.  
  501.  
  502.         int i_length = 0;
  503.         for (i = 0; i < pattern_length; i++)
  504.         {
  505.             char cur_char = pattern[i];
  506.             if (cur_char == 'Y')
  507.             {
  508.                 for (j = 0; j < y_len; j++)
  509.                 {
  510.                     input[i_length++] = y[j];
  511.                 }
  512.             }
  513.             else
  514.             {
  515.                 input[i_length++] = cur_char;
  516.             }
  517.  
  518.         }
  519.         input[i_length++] = '\0';
  520.         free(pattern);
  521.         pattern = NULL;
  522.         return input;
  523.  
  524.     }
  525.  
  526.    int n=1;
  527.     build_pattern(n, fonte);
  528.     build_pattern(n, destino);
  529.  
  530.      char *F=fonte;
  531.     char*D=destino;
  532.     char *auxiliar;
  533.   clock_t inicio= clock();
  534.  while(quantidade!=1)
  535.     {
  536. printf("\n Fonte: %s", F);
  537. printf("\n Destino: %s",D);
  538.         switch(F[0])
  539.         {
  540.  
  541.         case '(':
  542.         {
  543.             eliminar_parenteses(F,D);
  544.              if(quantidade!=1)
  545.             {
  546.                 auxiliar=F;
  547.                 F=D;
  548.                 D=auxiliar;
  549.             }
  550.             break;
  551.         }
  552.  
  553.         case 'K':
  554.         {
  555.  
  556.             RegraK(F,D);
  557.              if(quantidade!=1)
  558.             {
  559.                 auxiliar=F;
  560.                 F=D;
  561.                 D=auxiliar;
  562.             }
  563.         break;
  564.  
  565.         }
  566.         case 'S':
  567.         {
  568.  
  569.             RegraS(F,D);
  570.              if(quantidade!=1)
  571.             {
  572.                 auxiliar=F;
  573.                 F=D;
  574.                 D=auxiliar;
  575.             }
  576.             break;
  577.         }
  578.         case 'I':
  579.             {
  580.                 RegraI(F,D);
  581.                  if(quantidade!=1)
  582.             {
  583.                 auxiliar=F;
  584.                 F=D;
  585.                 D=auxiliar;
  586.             }
  587.             break;
  588.             }
  589.         case 'B':
  590.             {
  591.                 RegraB(F,D);
  592.                  if(quantidade!=1)
  593.             {
  594.                 auxiliar=F;
  595.                 F=D;
  596.                 D=auxiliar;
  597.             }
  598.             break;
  599.             }
  600.         case 'C':
  601.             {
  602.                 RegraC(F,D);
  603.                  if(quantidade!=1)
  604.             {
  605.                 auxiliar=F;
  606.                 F=D;
  607.                 D=auxiliar;
  608.             }
  609.             break;
  610.             }
  611.             case 'E':
  612.             {
  613.                 RegraE(F,D);
  614.                  if(quantidade!=1)
  615.             {
  616.                 auxiliar=F;
  617.                 F=D;
  618.                 D=auxiliar;
  619.             }
  620.             break;
  621.             }
  622.             case 'Q':
  623.                 {
  624.                     RegraQ(F,D);
  625.                      if(quantidade!=1)
  626.             {
  627.                 auxiliar=F;
  628.                 F=D;
  629.                 D=auxiliar;
  630.             }
  631.             break;
  632.                 }
  633.             case 'W':
  634.                 {
  635.             RegraW(F,D);
  636.         if(quantidade!=1)
  637.             {
  638.                 auxiliar=F;
  639.                 F=D;
  640.                 D=auxiliar;
  641.             }
  642.             break;
  643.                 }
  644.         default:
  645.             quantidade=1;
  646.  
  647.         }
  648.  
  649.     }
  650.     clock_t fina= clock();
  651.     double fim=((fina-inicio)/CLOCKS_PER_SEC);
  652.  
  653.     printf(" destino: %s \n", D);
  654.      printf("\n Tempo %1f s\n", fim);
  655.     return (EXIT_SUCCESS);
  656. }
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!