我想从一个数组中创建一个数学表达式解析树,该数组是以前缀表示法排序的。(顺便说一句,后缀会更容易吗?)
例如:
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
中。所以问题是,如何使数组的地址与递归一起移动?(最好不使用静态或全局变量)
发布于 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
的输入指针,然后依靠它将输入指针提前到操作符或值标记。另一种更经典的方法是编写一个令牌程序,它返回一个令牌类型和一个语义值,同时维护输入指针。
https://stackoverflow.com/questions/30279736
复制相似问题