Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //grafo testar o caso SKKKK
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- #define tamanho_heap 1000000
- typedef struct No{
- char tipo,memoria;
- int l,r;
- }no;
- char str[82000];
- no heap[tamanho_heap];
- int hp;
- int montaGrafo(int raiz,char* str, int b, int e){
- if(b == e){
- if(hp >= tamanho_heap){
- printf("Memoria insuficiente!");
- exit(1);
- }
- int pos=hp++;
- heap[pos].tipo=str[b];
- heap[pos].l=heap[pos].r=-1;
- return pos;
- }
- int i,ret;
- for( i=b; i<=e; i++){
- if(str[i]!='('){
- ret = montaGrafo(-1,str,i,i);
- }
- else{
- int j=i+1,total=1;
- while(total){
- if(str[j]=='(') total++;
- else if(str[j]==')') total--;
- j++;
- }
- ret = montaGrafo(-1,str,i+1,j-2);
- i=j-1;
- }
- if(raiz == -1) raiz=ret;
- else{
- if(hp >= tamanho_heap){
- printf("Memoria insuficiente!");
- exit(1);
- }
- int pos=hp++;
- heap[pos].tipo='@';
- heap[pos].l = raiz;
- heap[pos].r = ret;
- raiz = pos;
- }
- }
- return raiz;
- }
- int reduziu,atualizarRaiz;
- 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;
- void fazReducao(int raiz){
- int i,aux=raiz;
- for(i=0; i<5; i++) elements[i]=-1;
- while(raiz!=-1){
- for(int i=5; --i;){
- elements[i]=elements[i-1];
- }
- elements[0]=raiz;
- raiz = heap[raiz].l;
- }
- //printf("%c\n",heap[elements[0]].tipo);
- //for(i=0; i<5; i++) printf("%d ",elements[i]);
- //puts("");
- switch(heap[elements[0]].tipo){
- case 'K':
- if(elements[1]==-1 || elements[2]==-1) return;
- reduziu=1;
- if(elements[3]==-1){
- // utilizando 4 aqui para ser default pq tanto S quando K nao vai usar essa posicao.
- elements[4]= heap[elements[1]].r;
- atualizarRaiz=1;
- }
- else{
- heap[elements[3]].l=heap[elements[1]].r;
- }
- break;
- case 'S':
- if(elements[1]==-1 || elements[2]==-1 || elements[3]==-1) return;
- reduziu=1;
- // precisa checar essa condicao, nao tenho certeza se eh realmente 2 mais faz mais sentido >.<
- 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.
- printf("Memoria insuficiente!");
- exit(1);
- }
- int pos1 = hp++;
- int pos2 = hp++;
- int pos3 = hp++;
- heap[pos1].tipo='@';
- heap[pos2].tipo='@';
- heap[pos3].tipo='@';
- heap[pos1].l = heap[elements[1]].r;
- heap[pos1].r = heap[elements[3]].r;
- heap[pos2].l = heap[elements[2]].r;
- heap[pos2].r = heap[elements[3]].r;
- heap[pos3].l = pos1;
- heap[pos3].r = pos2;
- //for(i=0; i<5; i++) printf("%d ",elements[i]);
- //puts("");
- if(elements[4]==-1){
- //puts("Entrou aqui");
- elements[4]=pos3;
- atualizarRaiz=1;
- }
- else{
- heap[elements[4]].l=pos3;
- }
- break;
- }
- }
- void imprimePre(int raiz){
- if(raiz!=-1){
- imprimePre(heap[raiz].l);
- imprimePre(heap[raiz].r);
- printf("%c",heap[raiz].tipo);
- }
- }
- int main(){
- //freopen("in.txt","r",stdin);
- gets(str);
- int raiz= montaGrafo(-1,str,0,strlen(str)-1);
- //imprimePre(raiz);
- reduziu=1;
- while(reduziu){
- reduziu=0;
- atualizarRaiz=0;
- fazReducao(raiz);
- //printf("Raiz: %d\n",raiz);
- if(atualizarRaiz){
- raiz = elements[4];
- //puts("atualizou");
- }
- //printf("Raiz: %d\n",raiz);
- }
- imprimePre(raiz);
- puts("");
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement