Material didático para princípios de desenvolvimento de Algoritmos

LinhaCodigo
001// Prof. Leo^nidas - http://www.matematica.br http://line.ime.usp.br
002// MAC0122 - 2017/10/08
003// Primeira versao de: 2003
004
005// Exemplo de: arvore binaria (AB); expressao aritmetica (EA) em notacao in-fixa; expressao em notacao pos-fixa; listas ligadas
006// Descricao: Constroi uma AB representando uma Ea, depois a avalia de 2 modos (iterativo e recursivo)
007
008// gcc -fsanitize=address -g -o arvore_bin_expressao_aleatoria arvore_bin_expressao_aleatoria.c
009
010#include <stdio.h>
011#include <stdlib.h>
012
013#define MAX      2 // maxima profundidade da arvore
014#define Infimo   1 // so' aceita "operando" apos nivel 1
015#define MAXREC  30 // tamanho maximo para a pilha
016#define RESTO    5 // fator para diminuir valor dos numeros gerados
017#define SEMENTE 11 // para geracao de numeros aleatorios
018
019typedef struct Filho {
020  struct Filho *esq;
021  char tipo;
022  union { char c; int i; } info; // se tipo='d' => <operador => usar 'char c'>; se tipo='n' => <operando => usar 'int i'>
023  struct Filho *dir;
024  } No;
025
026int topo_ap, topo_v; // para simplificar usarei como globais (CUIDADO: evite, pois gera dificuldades de manutencao)
027
028// Prototipos de funcoes
029void imprime_arvore(No *r, int col);
030No *adiciona_filho(int cont);
031void monta_exp(No **)
032//V2 No *monta_exp(void);
033
034// Imprime arvore usando deslocanmento horizontal para indicar maior profundidade
035void imprime_arvore (No *r, int col) { // col indica profundidade do no'
036  int aux;
037  if ( r!= NULL ) {
038    if ( (*r).dir!=NULL ) imprime_arvore( (*r).dir, col+1 );
039    for (aux=0; aux<col; aux++)
040      printf("   ");
041    if ((*r).tipo=='d') printf("%c\n",(*r).info.c);
042    else                printf("%d\n",(*r).info.i);
043    if ( (*r).esq!=NULL ) imprime_arvore( (*r).esq, col+1);
044    }
045  }
046
047// Constroi arvore usando apenas operadores '*' e '+'
048No *adiciona_filho (int cont) {
049  No *aux;
050  int aux1, aux2, n; char c;
051  aux = malloc(sizeof(No));
052  if (cont<MAX) { // dentro do limite de profundidade 
053    // Para GCC:  aux1 = rand()%2; // 0 => operador, 1 => operando
054    aux1 = (int)(rand()%2); // 0 => operador, 1 => operando
055    if (aux1 && cont>Infimo) {
056      // e' operando
057      n = (rand() % RESTO);
058      if (n==0) n = 1; // evita 0 (0*n=0)
059      (*aux).info.i = n;
060      (*aux).tipo   = 'n';
061      (*aux).esq    = NULL;
062      (*aux).dir    = NULL;
063      }
064    else { // else de if (aux1 && cont>Infimo)
065      // e' operador
066      aux2 = rand()%2; // 0 => '+', 1 => '*'
067      if (aux2)
068        c='*';
069      else
070        c='+';
071      (*aux).info.c = c;
072      (*aux).tipo   = 'd';
073      // e' operador => tem dois filhos
074      (*aux).esq    = adiciona_filho( cont+1 );
075      (*aux).dir    = adiciona_filho( cont+1 );
076      } // else
077    } // if (cont<MAX)
078  else { // ja' atingiu o limite de profundidade, forca ser operando
079    printf("ultimo cont=%d MAX=%d\n",cont,MAX);
080    n = (rand() % RESTO);
081    if (n==0) n = 1; // evita 0 (0*n=0)
082    (*aux).info.i = n;
083    (*aux).tipo   = 'n';
084    (*aux).esq    = NULL;
085    (*aux).dir    = NULL;
086    } // else if (cont<MAX)
087  return aux;
088  } // adiciona_filho
089
090//V2 No *monta_exp (void)
091void monta_exp (No **r) {
092  //V2 No *r;
093  int aux1; char c;
094  *r = malloc(sizeof(No)); // no' r aponta para novo no'
095  srand(SEMENTE);
096  aux1 = rand() % 2; // 0 => '+', 1 => '*'
097  if (aux1) // decide operador: '+' ou '*'
098    c='*';
099  else
100    c='+';
101  (**r).info.c = c;
102  (**r).tipo   = 'd';
103  (**r).esq    = adiciona_filho(0);
104  (**r).dir    = adiciona_filho(0);
105  printf("\n retornou \n");
106  //V2 return r;
107  }
108
109// Calcula valor da expressao de modo iterativo
110int Calc_exp_it (No *r) {
111  No *Ap[MAXREC], *pai, *aux;
112  int V[MAXREC], topo_ap, topo_v, aux_esq, aux_dir;
113
114  // auxiliar para termino do algoritmo
115  aux = malloc(sizeof(No));
116  (*aux).esq = (*aux).dir=NULL;
117  topo_ap = topo_v = -1;
118  Ap[++topo_ap] = aux;
119  while (r!=NULL) {
120    if ((*r).tipo=='d') { // e' operador => empilhe
121      Ap[++topo_ap] = r;
122      pai = r;
123      r = (*r).esq;
124      }
125   else // e' operando => desempilhe 2
126     if (r==(*pai).dir) { // e' filho direito => computa expressao 
127       V[++topo_v] = (*r).info.i;
128       while (r==(*pai).dir) { // pegue 3 do topo da pilha e opere: operador operando1 operando2 => operando1 operador operando2 = operando3
129         aux_dir = V[topo_v--];
130         aux_esq = V[topo_v];
131         if ((*pai).info.c=='+')
132           V[topo_v] = aux_dir + aux_esq; // empilhe 'operando3'
133         else
134           V[topo_v] = aux_dir * aux_esq; // empilhe 'operando3'
135         r = pai;
136         pai = Ap[--topo_ap];
137         }
138       r = (*pai).dir;
139       } // if (r==(*pai).dir)
140    else { // e' filho esquerdo
141       V[++topo_v] = (*r).info.i;
142       r = (*pai).dir;
143       }
144    } // while
145
146  return V[0];
147  }
148
149// Calcula expressao de modo recursivo
150int Calc_exp_rec (No *r) {
151  int aux_esq, aux_dir;
152  if (r!=NULL)
153    if ( (*r).tipo=='d' ) { // e' operador
154      aux_esq = Calc_exp_rec( (*r).esq );
155      aux_dir = Calc_exp_rec( (*r).dir );
156      if ( (*r).info.c=='+' )
157        return aux_esq + aux_dir;
158      else
159        return aux_esq * aux_dir;
160      }
161    else
162      return (*r).info.i;
163  else
164    return 0; // --> so' sera' necessario se a arv. for vazia!
165  }
166
167//
168void main (void) {
169  No *raiz;
170
171  printf("INICIO\n");
172
173  //V2 raiz=monta_exp();
174  monta_exp(&raiz);
175
176  imprime_arvore(raiz, 0);
177
178  printf("\nValor (iterativo) %d\n",Calc_exp_it(raiz));
179  printf("\nValor (recursivo) %d\n",Calc_exp_rec(raiz));
180  }