首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >问答首页 >前缀数学表达式数组来解析树-递归用数组移动

前缀数学表达式数组来解析树-递归用数组移动
EN

Stack Overflow用户
提问于 2015-05-16 19:13:41
回答 1查看 330关注 0票数 0

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

例如:

Infix:(3+4)*5)/2)+8) 前缀:+8/2*5+43(函数将给出此)

下面是我的代码,简而言之,它应该线性地遍历前缀数组,每个递归调用都会在数组中向前移动。

如果current是一个操作符,则向左和右进行递归调用,如果是一个数字,只需进行它并返回。

代码语言:javascript
运行
复制
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;

}

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

它正确地创建了左边的部分,但是右边是3 --我理解当它将第一个调用留在左边时,它只是在arr+2中而不是arr+4中。所以问题是,如何使数组的地址与递归一起移动?(最好不使用静态或全局变量)

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2015-05-17 04:55:42

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

执行此操作的方法有多种,但在C中最简单的方法是通过引用传递输入指针;或者,换句话说,将指针传递给指针:

代码语言:javascript
运行
复制
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的输入指针,然后依靠它将输入指针提前到操作符或值标记。另一种更经典的方法是编写一个令牌程序,它返回一个令牌类型和一个语义值,同时维护输入指针。

票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/30279736

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档