前缀数学表达式数组以解析树 - 递归以随数组移动

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

我想从以前缀表示法排序的数组创建数学表达式解析树。 (顺便说一句,使用 postfix 会更容易吗?)

例如:

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

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

下面是我的代码,简而言之,假设是线性遍历前缀数组,每次递归调用都在数组中向前移动。

如果current是一个运算符,则递归调用left和right,如果是一个数字,就调用它然后return。

TreeNode * parsetree(char  *arr){

    if (*arr == '[=10=]'){
        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;

}

问题是向上移动数组在递归中不能很好地工作,例如,给定: *-39+21((1+2)*(9-3))

它正确地创建了左侧部分,但右侧只是 3 我知道当它离开左侧的第一个调用时,它只是在 arr+2 而不是 arr+4 .那么问题来了,如何让数组的地址随着递归移动呢? (最好不使用静态或全局变量)

问题是您需要递归调用 return 新创建的节点和更新的输入指针。

有多种方法可以做到这一点,但在 C 中最简单的方法是通过引用传递输入指针;或者,换句话说,将指针传递给指针:

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

注意模式:每当我们使用一个字符时,我们都会增加输入指针。另一种方法是将指向输入指针的指针传递给 treenodemaker,然后依靠它将输入指针推进到运算符或值标记之后。一个更经典的替代方案是编写一个分词器,它 return 是一个分词类型和一个语义值,同时维护输入指针。