2

To tentando construir uma arvore que recebe uma expressão matemática completamente parentesada [ex: ((a+b)+c)] , porém acho que minha função de inserção ta errada! Será que alguém pode me dar uma luz?

typedef struct arvore {
char info;
struct arvore*esq;
struct arvore*dir;
}no;


no *cria(no*raiz, char el[], int i){
int j = i;
char s= el[j];
//printf("%s", el);

if(raiz == NULL){
    raiz = (no*)malloc(sizeof(no));
    (raiz)->dir = NULL;
    (raiz)->esq = NULL;
}

if(s == '('){
    j++;
    s=el[j];
    raiz->esq = cria(raiz->esq, el, j);
    if(s == '+'){
        (raiz)->info = s;
        j++;
        s=el[j];
        raiz->dir = cria((raiz)->dir, el, j);
        if(s==')'){
            j++;
            s=el[j];
            //return raiz;
        }
    }
}else{
    (raiz)->info=s;
    j++;
    s=el[j];

    return raiz;
}

}

a intenção é fazer a arvore ter apenas letras e operadores, sendo que cada nó q possuir um operador no campo info terá 2 filhos com letras nos campos infos, respectivos!

1 Resposta 1

4

Seu problema é que você parece estar assumindo que uma variável dentro de uma função conserva seu valor quando essa mesma função é chamada recursivamente (i.e. todas as chamadas a cria compartilham as mesmas variáveis j e s). Mas não é assim que a linguagem C (e praticamente toda linguagem que eu conheço) funciona - a cada chamada da função cria, uma nova cópia de suas variáveis locais é criada na pilha de chamada:

inserir a descrição da imagem aqui

Sendo assim, quando você faz, no final do último else:

(raiz)->info=s;
j++;
s=el[j];

return raiz;

Você espera que na função chamadora j seja 1 a mais, e s seja o próximo elemento, mas na realidade só a cópia de j e s daquela chamada específica tiveram seu valor atualizado; o j e o s da função que chamou o cria continuam com seu valor antigo.

j++;
s=el[j];                            // Abre um elemento (digamos, "a")
raiz->esq = cria(raiz->esq, el, j); // Lê esse elemento
if(s == '+'){                       // Ainda está no elemento "a"!

Como melhor resolver isso, não sei dizer, mas uma solução provisória que funcionaria (o restante do seu código me parece todo correto) seria transformar j e s em variáveis globais. Assim elas de fato seriam compartilhadas por todas as chamadas de cria, como você pretende. Entretanto, essa não é uma prática muito recomendável, sobretudo em sistemas grandes, de modo que alguma refatoração do seu código seria desejável eventualmente.

Como soluções definitivas, eu exploraria a possibilidade de guardar o estado da execução (j, s e o novo nó criado) em uma struct à parte, ou talvez a possibilidade de passar ponteiros para j e s às funções chamadas recursivamente, de modo que estas pudessem atualizar seu valor. Sinceramente, não sei o que seria melhor. Numa implementação de mais alto nível, eu usaria um iterador sobre a sequência de caracteres em vez da sequência em si (i.e. um iterador muda seu estado interno cada vez que um elemento seu é consumido), mas não conheço a complexidade de se fazer isso em C.

1
  • Obrigado cara, ajudou bastante! Esse programa é pra um trabalho da faculdade, entao acho q a melhor saida mesmo pode ser usar variaveis globais! Gratidão total! 16/10/2015 às 17:17

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .