C program to solve mathematical expressions using binary tree

Question

C program to solve mathematical expressions using binary tree

Navigation

#1 by (4 votes)

2

I'm trying to build a tree that gets a fully mathematic math expression [ex: ((a + b) + c)], but I think my insert function is wrong! Can someone give me a light?

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;
}

}

The intention is to make the tree have only letters and operators, and each node that has an operator in the info field will have 2 children with letters in the respective information fields!

c inserir

asked by anonymous 16.10.2015 / 04:47

1 answer

Autoload class PSR4 How to create project installation done in the android studio

score 4 · Accepted Answer

Your problem is that you seem to be assuming that a variable within a function retains its value when that same function is called recursively (ie all calls to cria share the same variables j and% with%). But this is not how C (and pretty much every language I know) works - at every call of the s function, a new copy of its local variables is created in the call stack:

So,whenyoudo,attheendofthelastcria:

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

Youexpectthecallingfunctionelsetobejmore,and1isthenextelement,butinrealityonlythecopyofsandjspecificcallhaditsvalueupdated;thesandthejofthefunctionthatcalledthescontinuewiththeiroldvalue.

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

How do I best solve this, I can not say, but a temporary solution that would work (the rest of your code seems to me to be correct) would be to transform cria and j into global variables. So they would in fact be shared by all s calls, as you intended. However, this is not a very recommendable practice, especially in large systems, so some refactoring of your code would eventually be desirable.

As a final solution, I would exploit the possibility of saving execution status ( cria , j and new created node) in a s aside, or perhaps the possibility to pass pointers to struct and j to the functions called recursively, so that they could update their value. Honestly, I do not know what would be best. In a higher level implementation, I would use an iterator on the string instead of the string itself (ie an iterator changes its internal state each time an element of it is consumed), but I do not know the complexity of doing this in C.