CODEWITHSUNDEEP
cparsingrecursiontreebinary-tree
shinzou
shinzou

Reputation: 6222

Prefix math expressions array to parse tree - recursion to move with array

I want to create a math expression parse tree from an array that is sorted in prefix notation. (BTW, will it be easier with postfix?)

For example:

Infix: ((((3+4)*5)/2)+8)

Prefix: + 8 / 2 * 5 + 4 3 (the function will be given this)

Below is my code, in short, it's suppose to go through the prefix array linearly, with each recursive call to move forward in the array.

If current is an operator make a recursive call to left and right, if a digit, just make it and return.

TreeNode * parsetree(char  *arr){

    if (*arr == '\0'){
        return NULL;
    }
    TreeNode *curr=NULL;

    if (isop(*arr)){
        curr = treenodemaker(*arr, NULL, NULL); 
        arr++;
        curr->left = parsetree(arr);
        arr++;
        curr->right = parsetree(arr);
    }
    else if (isdig(*arr)){
        curr = treenodemaker(*arr, NULL, NULL);
    }
    return curr;

}

The problem is moving up the array doesn't work well in the recursion, for example, given: *-39+21 which is ((1+2)*(9-3))

It creates the left part correctly, but the right side is just 3 I understand that when it leaves the first call to the left, it's just in arr+2 instead arr+4. So the question is, how can I make the address of the array move with the recursion? (preferably without using static or global variables)

Upvotes: 0

Views: 354

Answers (1)

rici
rici

Reputation: 241911

The problem is that you need the recursive call to return both the newly created node and the updated input pointer.

There are various ways of doing this, but the easiest one in C is to pass the input pointer by reference; or, in other words, pass a pointer to the pointer:

TreeNode * parsetree(char **arr){
    TreeNode *curr=NULL; 
    if (isop(**arr)){
        curr = treenodemaker(**arr, NULL, NULL); 
        ++*arr;
        curr->left = parsetree(arr);
        // Deleted arr++, which certainly wasn't correct
        curr->right = parsetree(arr);
    } else if (isdig(**arr)){
        curr = treenodemaker(*arr, NULL, NULL);
        ++*arr; // Here we need to record that we've consumed a char
    } else if (**arr) {
        // Need to do something here; an error has occurred
    }
    return curr;
}

Note the pattern: whenever we consume a character, we increment the input pointer. An alternative would have been passing the pointer to the input pointer to treenodemaker, and then relying on it to advance the input pointer past the operator or value token. A more classic alternative would be to write a tokenizer, which returns a token type and a semantic value, while maintaining the input pointer.

Upvotes: 1

Related Questions