API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Nov 28th, 2014
164
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 8.03 KB | None | 0 0
raw download clone embed print report
  1. //grafo testar o caso SKKKK
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <string.h>
  5.  
  6. #define tamanho_heap 1000000
  7.  
  8. typedef struct No{
  9.     char tipo,memoria;
  10.     int l,r;
  11. }no;
  12.  
  13. char str[82000];
  14. no heap[tamanho_heap];
  15. int hp;
  16.  
  17. int montaGrafo(int raiz,char* str, int b, int e){
  18.     if(b == e){
  19.         if(hp >= tamanho_heap){
  20.             printf("Memoria insuficiente!");
  21.             exit(1);
  22.         }
  23.         int pos=hp++;
  24.         heap[pos].tipo=str[b];
  25.         heap[pos].l=heap[pos].r=-1;
  26.         return pos;
  27.     }
  28.     int i,ret;
  29.     for( i=b; i<=e; i++){
  30.         if(str[i]!='('){
  31.             ret = montaGrafo(-1,str,i,i);
  32.         }
  33.         else{
  34.             int j=i+1,total=1;
  35.             while(total){
  36.                 if(str[j]=='(') total++;
  37.                 else if(str[j]==')') total--;
  38.                 j++;
  39.             }
  40.             ret = montaGrafo(-1,str,i+1,j-2);
  41.             i=j-1;
  42.         }
  43.         if(raiz == -1) raiz=ret;
  44.         else{
  45.             if(hp >= tamanho_heap){
  46.                 printf("Memoria insuficiente!");
  47.                 exit(1);
  48.             }
  49.             int pos=hp++;
  50.             heap[pos].tipo='@';
  51.             heap[pos].l = raiz;
  52.             heap[pos].r = ret;
  53.             raiz = pos;
  54.         }
  55.     }
  56.  
  57.     return raiz;
  58.  
  59. }
  60.  
  61.  
  62. int reduziu,atualizarRaiz;
  63.  // 5 por que no pior caso eu vou precisar de um para saber o tipo S ou K / 3 para os operadores a b c no caso do S/ e outro para saber o retorno;
  64. void fazReducao(int raiz){
  65.     int elements[6];
  66.     int i,aux=raiz;
  67.     int pos1, pos2, pos3,pos4;
  68.  
  69.     for(i=0; i<6; i++) elements[i]=-1;
  70.     while(raiz!=-1){
  71.         for(i=6; --i;){
  72.             elements[i]=elements[i-1];
  73.         }
  74.         elements[0]=raiz;
  75.         raiz = heap[raiz].l;
  76.     }
  77.     //printf("%c\n",heap[elements[0]].tipo);
  78.     //for(i=0; i<5; i++) printf("%d ",elements[i]);
  79.     //puts("");
  80.  
  81.     switch(heap[elements[0]].tipo){
  82.         case 'K':
  83.                 if(elements[1]==-1 || elements[2]==-1) return;
  84.                 reduziu=1;
  85.                 if(elements[3]==-1){
  86.                     atualizarRaiz=heap[elements[1]].r;
  87.                 }
  88.                 else{
  89.                     heap[elements[3]].l=heap[elements[1]].r;
  90.                 }
  91.                 break;
  92.         case 'S':
  93.                 if(elements[1]==-1 || elements[2]==-1 || elements[3]==-1) return;
  94.                 reduziu=1;
  95.                 // precisa checar essa condicao, nao tenho certeza se eh realmente 2 mais faz mais sentido >.<
  96.                 if(hp+2 >= tamanho_heap){ // +2 pq o ponteiro hp sempre ta uma posicao a frente entao eu ja tenho um @ mais vou precisar de + 2.
  97.                     printf("Memoria insuficiente!");
  98.                     exit(1);
  99.                 }
  100.                 pos1 = hp++;
  101.                 pos2 = hp++;
  102.                 pos3 = hp++;
  103.  
  104.                 heap[pos1].tipo='@';
  105.                 heap[pos2].tipo='@';
  106.                 heap[pos3].tipo='@';
  107.  
  108.                 heap[pos1].l = heap[elements[1]].r;
  109.                 heap[pos1].r = heap[elements[3]].r;
  110.  
  111.                 heap[pos2].l = heap[elements[2]].r;
  112.                 heap[pos2].r = heap[elements[3]].r;
  113.  
  114.                 heap[pos3].l = pos1;
  115.                 heap[pos3].r = pos2;
  116.                 //for(i=0; i<5; i++) printf("%d ",elements[i]);
  117.                 //puts("");
  118.                 if(elements[4]==-1){
  119.                     //puts("Entrou aqui");
  120.                     atualizarRaiz=pos3;
  121.                 }
  122.                 else{
  123.                     heap[elements[4]].l=pos3;
  124.                 }
  125.                 break;
  126.         case 'I':
  127.                 if(elements[1]==-1) return;
  128.                 reduziu=1;
  129.  
  130.                 if(elements[2]==-1){
  131.                     atualizarRaiz=heap[elements[1]].r;
  132.                 }
  133.                 else{
  134.                     heap[elements[2]].l=heap[elements[1]].r;
  135.                 }
  136.                 break;
  137.         case 'B':
  138.                 //B a b c => a(bc)
  139.                 if(elements[1]==-1 || elements[2]==-1 || elements[3]==-1) return;
  140.                 reduziu=1;
  141.  
  142.                 if(hp+3 >= tamanho_heap){ //
  143.                     printf("Memoria insuficiente!");
  144.                     exit(1);
  145.                 }
  146.  
  147.                 pos1 = hp++;
  148.                 pos2 = hp++;
  149.  
  150.                 heap[pos2].tipo='@';
  151.                 heap[pos2].l = heap[elements[2]].r; //left pra b
  152.                 heap[pos2].r = heap[elements[3]].r; // righ pra c
  153.  
  154.  
  155.                 heap[pos1].tipo='@';
  156.                 heap[pos1].l = heap[elements[1]].r;
  157.                 heap[pos1].r = pos2;
  158.  
  159.                 if(elements[4]==-1){
  160.                     //puts("Entrou aqui");
  161.                     atualizarRaiz=pos1;
  162.                 }
  163.                 else{
  164.                     heap[elements[4]].l=pos1;
  165.                 }
  166.  
  167.                 break;
  168.  
  169.         case 'C':
  170.                 //C a b c => acb
  171.                 if(elements[1]==-1 || elements[2]==-1 || elements[3]==-1) return;
  172.                 reduziu=1;
  173.  
  174.                 pos1 = hp++;
  175.                 pos2 = hp++;
  176.  
  177.                 heap[pos1].tipo='@';
  178.                 heap[pos1].l = heap[elements[1]].r; //left pra a
  179.                 heap[pos1].r = heap[elements[3]].r; // righ pra c
  180.  
  181.  
  182.                 heap[pos2].tipo='@';
  183.                 heap[pos2].l = pos1; //left pra pos1
  184.                 heap[pos2].r = heap[elements[2]].r; //righ pra b
  185.  
  186.                 if(elements[4]==-1){
  187.                     //puts("Entrou aqui");
  188.                     atualizarRaiz=pos2;
  189.                 }
  190.                 else{
  191.                     heap[elements[4]].l = pos2;
  192.                 }
  193.                 break;
  194.  
  195.         case 's':
  196.             //S' a b c d => a(bd)(cd)
  197.             if(elements[1]==-1 || elements[2]==-1 || elements[3]==-1 || elements[4]==-1) return;
  198.                 reduziu=1;
  199.  
  200.                 if(hp+4 >= tamanho_heap){
  201.                     printf("Memoria insuficiente!");
  202.                     exit(1);
  203.                 }
  204.  
  205.                 pos1 = hp++;
  206.                 pos2 = hp++;
  207.                 pos3 = hp++;
  208.                 pos4 = hp++;
  209.  
  210.                 heap[pos1].tipo='@';
  211.                 heap[pos2].tipo='@';
  212.                 heap[pos3].tipo='@';
  213.                 heap[pos4].tipo='@';
  214.  
  215.                 heap[pos1].l = heap[elements[1]].r; // left para a - @1
  216.  
  217.                 heap[pos2].l = heap[elements[2]].r; // left para b - @2
  218.                 heap[pos2].r = heap[elements[4]].r; // righ para d - @2
  219.  
  220.                 heap[pos3].l = heap[elements[3]].r; // left para c - @3
  221.                 heap[pos3].r = heap[elements[4]].r; // righ para d de novo
  222.  
  223.                 heap[pos1].r = pos2;
  224.  
  225.                 heap[pos4].l = pos1;
  226.                 heap[pos4].r = pos3;
  227.  
  228.  
  229.                 if(elements[5]==-1){
  230.                     puts("Entrou aqui");
  231.                     atualizarRaiz=pos4;
  232.  
  233.                 }
  234.                 else{
  235.                     puts("Entrou aqui2");
  236.                     heap[elements[5]].l=pos4;
  237.                 }
  238.  
  239.                 break;
  240.         case 'b':
  241.                 //B' a b c d => ab(cd)
  242.                 if(elements[1]==-1 || elements[2]==-1 || elements[3]==-1|| elements[4]==-1) return;
  243.                 reduziu=1;
  244.  
  245.                 if(hp+3 >= tamanho_heap){
  246.                     printf("Memoria insuficiente!");
  247.                     exit(1);
  248.                 }
  249.  
  250.                 pos1 = hp++;
  251.                 pos2 = hp++;
  252.                 pos3 = hp++;
  253.  
  254.                 heap[pos1].tipo='@';
  255.                 heap[pos1].l = heap[elements[1]].r; // left pra a
  256.                 heap[pos1].r = heap[elements[2]].r; //righ pra b
  257.  
  258.  
  259.                 heap[pos2].tipo='@';
  260.                 heap[pos2].l = heap[elements[3]].r; // left para c - @1
  261.                 heap[pos2].r = heap[elements[4]].r; // righ para d - @1
  262.  
  263.  
  264.                 heap[pos3].tipo='@';
  265.                 heap[pos3].l = pos1;
  266.                 heap[pos3].r = pos2;
  267.  
  268.                 if(elements[5]==-1){
  269.                     atualizarRaiz= pos3;
  270.                 }
  271.                 else{
  272.                     heap[elements[5]].l=pos3;
  273.                 }
  274.  
  275.  
  276.                 break;
  277.  
  278.         case 'c':
  279.                 //C' a b c d => a(bd)c
  280.                 if(elements[1]==-1 || elements[2]==-1 || elements[3]==-1|| elements[4]==-1) return;
  281.                 reduziu=1;
  282.  
  283.                 if(hp+4 >= tamanho_heap){
  284.                     printf("Memoria insuficiente!");
  285.                     exit(1);
  286.                 }
  287.  
  288.                 pos1 = hp++;
  289.                 pos2 = hp++;
  290.                 pos3 = hp++;
  291.  
  292.                 heap[pos1].tipo='@';
  293.                 heap[pos1].l = heap[elements[1]].r; // left pra a
  294.  
  295.  
  296.                 heap[pos2].tipo='@';
  297.                 heap[pos2].l = heap[elements[2]].r; // left para b - @1
  298.                 heap[pos2].r = heap[elements[4]].r; // righ para d - @1
  299.  
  300.                 heap[pos1].r = pos2;
  301.  
  302.                 heap[pos3].tipo='@';
  303.                 heap[pos3].l = pos1;                //left pra pos 1
  304.                 heap[pos3].r = heap[elements[3]].r; //righ pra c
  305.  
  306.                 if(elements[5]==-1){
  307.                     atualizarRaiz= pos3;
  308.                 }
  309.                 else{
  310.                     heap[elements[5]].l=pos3;
  311.                 }
  312.  
  313.                 break;
  314.  
  315.     }
  316.  
  317. }
  318.  
  319. void imprimePre(int raiz){
  320.     if(raiz!=-1){
  321.         imprimePre(heap[raiz].l);
  322.         imprimePre(heap[raiz].r);
  323.         printf("%c",heap[raiz].tipo);
  324.     }
  325.  
  326. }
  327.  
  328.  
  329.  
  330. int main(){
  331.     //freopen("in.txt","r",stdin);
  332.  
  333.     gets(str);
  334.     int raiz= montaGrafo(-1,str,0,strlen(str)-1);
  335.  
  336.     reduziu=1;
  337.     while(reduziu){
  338.         reduziu=0;
  339.         atualizarRaiz=-1;
  340.         imprimePre(raiz);
  341.         printf("\n");
  342.         fazReducao(raiz);
  343.         //printf("Raiz: %d\n",raiz);
  344.         if(atualizarRaiz!=-1){
  345.             raiz = atualizarRaiz;
  346.             //puts("atualizou");
  347.         }
  348.         //printf("Raiz: %d\n",raiz);
  349.     }
  350.  
  351.     printf("\n");
  352.  
  353.     imprimePre(raiz);
  354.  
  355.     puts("");
  356.  
  357.     return 0;
  358. }
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!