Advertisement
Guest User

Untitled

a guest
Nov 27th, 2014
140
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.43 KB | None | 0 0
  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. int elements[5]; // 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 i,aux=raiz;
  66.     for(i=0; i<5; i++) elements[i]=-1;
  67.     while(raiz!=-1){
  68.         for(int i=5; --i;){
  69.             elements[i]=elements[i-1];
  70.         }
  71.         elements[0]=raiz;
  72.         raiz = heap[raiz].l;
  73.     }
  74.     //printf("%c\n",heap[elements[0]].tipo);
  75.     //for(i=0; i<5; i++) printf("%d ",elements[i]);
  76.     //puts("");
  77.    
  78.     switch(heap[elements[0]].tipo){
  79.         case 'K':
  80.                 if(elements[1]==-1 || elements[2]==-1) return;
  81.                 reduziu=1;
  82.                 if(elements[3]==-1){
  83.                     // utilizando 4 aqui para ser default pq tanto S quando K nao vai usar essa posicao.
  84.                     elements[4]= heap[elements[1]].r;
  85.                     atualizarRaiz=1;
  86.                 }
  87.                 else{
  88.                     heap[elements[3]].l=heap[elements[1]].r;
  89.                 }
  90.                 break;
  91.         case 'S':
  92.                 if(elements[1]==-1 || elements[2]==-1 || elements[3]==-1) return;
  93.                 reduziu=1;
  94.                 // precisa checar essa condicao, nao tenho certeza se eh realmente 2 mais faz mais sentido >.<
  95.                 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.
  96.                     printf("Memoria insuficiente!");
  97.                     exit(1);
  98.                 }
  99.                 int pos1 = hp++;
  100.                 int pos2 = hp++;
  101.                 int pos3 = hp++;
  102.                
  103.                 heap[pos1].tipo='@';
  104.                 heap[pos2].tipo='@';
  105.                 heap[pos3].tipo='@';
  106.                
  107.                 heap[pos1].l = heap[elements[1]].r;
  108.                 heap[pos1].r = heap[elements[3]].r;
  109.                
  110.                 heap[pos2].l = heap[elements[2]].r;
  111.                 heap[pos2].r = heap[elements[3]].r;
  112.                
  113.                 heap[pos3].l = pos1;
  114.                 heap[pos3].r = pos2;
  115.                 //for(i=0; i<5; i++) printf("%d ",elements[i]);
  116.                 //puts("");
  117.                 if(elements[4]==-1){
  118.                     //puts("Entrou aqui");
  119.                     elements[4]=pos3;
  120.                     atualizarRaiz=1;
  121.                 }
  122.                 else{
  123.                     heap[elements[4]].l=pos3;
  124.                 }  
  125.                 break;         
  126.     }
  127.  
  128. }
  129.  
  130. void imprimePre(int raiz){
  131.     if(raiz!=-1){
  132.         imprimePre(heap[raiz].l);
  133.         imprimePre(heap[raiz].r);
  134.         printf("%c",heap[raiz].tipo);
  135.     }
  136.    
  137. }
  138.  
  139.  
  140.  
  141. int main(){
  142.     //freopen("in.txt","r",stdin);
  143.     gets(str);
  144.     int raiz= montaGrafo(-1,str,0,strlen(str)-1);
  145.     //imprimePre(raiz);
  146.     reduziu=1;
  147.     while(reduziu){
  148.         reduziu=0;
  149.         atualizarRaiz=0;
  150.         fazReducao(raiz);
  151.         //printf("Raiz: %d\n",raiz);
  152.         if(atualizarRaiz){
  153.             raiz = elements[4];
  154.             //puts("atualizou");
  155.         }
  156.         //printf("Raiz: %d\n",raiz);
  157.     }
  158.     imprimePre(raiz);
  159.    
  160.     puts("");
  161.    
  162.     return 0;
  163. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement