前缀数学表达式数组来解析树-递归用数组移动
前缀数学表达式数组来解析树-递归用数组移动
提问于 2015-05-16 19:13:41
我想从一个数组中创建一个数学表达式解析树，该数组是以前缀表示法排序的。(顺便说一句，后缀会更容易吗？)
例如：
Infix：(3+4)*5)/2)+8) 前缀：+8/2*5+43(函数将给出此)
下面是我的代码，简而言之，它应该线性地遍历前缀数组，每个递归调用都会在数组中向前移动。
如果current是一个操作符，则向左和右进行递归调用，如果是一个数字，只需进行它并返回。
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中。所以问题是，如何使数组的地址与递归一起移动？(最好不使用静态或全局变量)
回答 1
Stack Overflow用户
回答已采纳
发布于 2015-05-17 04:55:42
问题是，您需要递归调用来返回新创建的节点和更新的输入指针。
执行此操作的方法有多种，但在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的输入指针，然后依靠它将输入指针提前到操作符或值标记。另一种更经典的方法是编写一个令牌程序，它返回一个令牌类型和一个语义值，同时维护输入指针。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/30279736
复制相关文章
相似问题
腾讯云开发者
