C program for solving mathematical expressions using binary tree

Question

I’m trying to build a tree that receives a completely parented mathematical expression [e.g.: ((a+b)+c)] but I think my insertion function is wrong! Will 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 q has an operator in the field info will have 2 children with letters in the fields Infos, respective!

Answer 1

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 (i.e. all calls to cria share the same variables j and s). But that’s not how the C language (and pretty much every language I know) works - every function call cria, a new copy of your local variables is created on the call stack:

So when you do, at the end of the last else:

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

return raiz;

You expect in the calling function j be it 1 the more, and s be the next element, but in reality only the copy of j and s that specific call had its value updated; the j and the s of the function that called the cria continue with their old value.

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"!

How best to solve this, I can’t say, but an interim solution that would work (the rest of your code seems all right) would be to transform j and s global variables. So they would in fact be shared by all the calls of cria, how do you intend. However, this is not a very recommended practice, especially in large systems, so some refactoring of your code would be desirable eventually.

As definitive solutions, I would explore the possibility of guarding the state of execution (j, s and the new node created) in a struct apart, or perhaps the possibility of passing pointers to j and s functions called recursively, so that they could update their value. I honestly don’t know what would be better. In a higher-level implementation, I would use a iterator over the string instead of the sequence itself (i.e. an iterator changes its internal state each time an element of itself is consumed), but I don’t know the complexity of doing this in C.