Advertisement
Guest User

Calcular Expressão - Arvore Binária

a guest
May 27th, 2015
241
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 4.19 KB | None | 0 0
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include <string.h>
  4. #include <ctype.h>
  5.  
  6. typedef struct tarvore{
  7.     char *c;
  8.     struct tarvore *esquerda, *direita;
  9. }arvore;
  10.  
  11. typedef struct tpilha{
  12.     char letra;
  13.     struct tpilha *proximo;
  14. }pilha;
  15.  
  16. pilha *empilharcaracter(char caracter){
  17.     pilha *auxiliar=NULL;
  18.     auxiliar = (pilha*)malloc(sizeof(pilha));
  19.     auxiliar->letra = caracter;
  20.     return auxiliar;
  21. }
  22.  
  23. void empilha(pilha **topo, pilha *novo){
  24.     novo->proximo = *topo;
  25.     *topo = novo;
  26. }
  27.  
  28. char desempilhar(pilha **topo){
  29.     pilha *aux=NULL;
  30.     aux = *topo;
  31.     *topo = (*topo)->proximo;
  32.     return aux->letra;
  33. }
  34.  
  35. void insereArvore(arvore **raiz, char *str, int &i){
  36.     char letra;
  37.     if(i>=0){
  38.         letra = str[i--];
  39.         *raiz = (arvore*)malloc(sizeof(arvore));
  40.         if(letra=='.'){
  41.             (*raiz)->c = (char*)malloc(sizeof(char)*((int)str[i]-47));
  42.             (*raiz)->c[(int)str[i]-48] = '\0';
  43.             for(int j=(int)str[i]-49;j>=0;j--){
  44.                 i--;
  45.                 (*raiz)->c[j] = str[i];
  46.             }
  47.             i--;
  48.         }
  49.         else{
  50.             (*raiz)->c = (char*)malloc(sizeof(char));
  51.             (*raiz)->c[0] = letra;
  52.         }
  53.         if(letra=='+' || letra=='-' || letra=='*' || letra=='/'){
  54.             insereArvore(&(*raiz)->direita, str, i);
  55.             insereArvore(&(*raiz)->esquerda, str, i);
  56.         }
  57.         else{
  58.             (*raiz)->esquerda = NULL;
  59.             (*raiz)->direita = NULL;
  60.         }
  61.     }
  62. }
  63.  
  64. void anularTopo(pilha **topo){
  65.     pilha *aux=*topo;
  66.     (*topo) = (*topo)->proximo;
  67.     free(aux);
  68. }
  69.  
  70. void notacaoPolonesa(pilha **topo, char *str, int &tamanho){
  71.     int j, k=0, l=0;
  72.     char temp[tamanho];
  73.     for(j=0;str[j]!='\0';j++){
  74.         if(isdigit(str[j])){
  75.             temp[k++] = str[j];
  76.             l++;
  77.             if(l>1 && !isdigit(str[j+1])){
  78.                 tamanho+=2;
  79.                 realloc(temp, tamanho);
  80.                 temp[k++] = (char)(l+48);
  81.                 temp[k++] = '.';
  82.             }
  83.         }
  84.         else{
  85.             if(*topo==NULL){
  86.                 empilha(topo, empilharcaracter(str[j]));
  87.             }
  88.             else{
  89.                 if(str[j]=='('){
  90.                     empilha(topo, empilharcaracter(str[j]));
  91.                 }
  92.                 else if(((*topo)->letra=='*' || (*topo)->letra=='/') && (str[j]=='+' || str[j]=='-')){
  93.                     temp[k++] = desempilhar(topo);
  94.                     empilha(topo, empilharcaracter(str[j]));
  95.                 }
  96.                 else if(((*topo)->letra=='+' || (*topo)->letra=='-' || (*topo)->letra=='*' || (*topo)->letra=='/' || (*topo)->letra=='(') && (str[j]=='/' || str[j]=='*' || str[j]=='+' || str[j]=='-')){
  97.                     empilha(topo, empilharcaracter(str[j]));
  98.                 }
  99.                 else{
  100.                     while((*topo)->letra!='('){
  101.                         temp[k++] = desempilhar(topo);
  102.                     }
  103.                     anularTopo(topo);
  104.                 }
  105.             }
  106.             l=0;
  107.         }
  108.     }
  109.     while((*topo)!=NULL){
  110.         temp[k++] = desempilhar(topo);
  111.     }
  112.     temp[k++] = '\0';
  113.     strcpy(str, temp);
  114.     free(temp);
  115. }
  116.  
  117. int calcularArvore(arvore *raiz){
  118.     if(raiz->c[0]=='+')
  119.         return calcularArvore(raiz->esquerda) + calcularArvore(raiz->direita);
  120.     if(raiz->c[0]=='-')
  121.         return calcularArvore(raiz->esquerda) - calcularArvore(raiz->direita);
  122.     if(raiz->c[0]=='*')
  123.         return calcularArvore(raiz->esquerda) * calcularArvore(raiz->direita);
  124.     if(raiz->c[0]=='/')
  125.         return calcularArvore(raiz->esquerda) / calcularArvore(raiz->direita);
  126.     return atoi(raiz->c);
  127. }
  128.  
  129. int procurarParenteses(char *str){
  130.     int j, c=0, tam;
  131.     for(j=0;str[j]!='\0';j++){
  132.         if(str[j]=='(')
  133.            c+=2;
  134.     }
  135.     tam = strlen(str)-c-1;
  136.     return tam;
  137. }
  138.  
  139. void expressao(char *str){
  140.     printf("Exp: ");
  141.     scanf("%s", str);
  142. }
  143.  
  144. int main(void){
  145.     arvore *raiz=NULL;
  146.     pilha *topo=NULL;
  147.     int i;
  148.     char str[100];
  149.     expressao(str);
  150.     i = procurarParenteses(str);
  151.     notacaoPolonesa(&topo, str, i);
  152.     insereArvore(&raiz, str, i);
  153.     printf("\nResultado: %d", calcularArvore(raiz));
  154. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement