前缀数学表达式数组以解析树 - 递归以随数组移动
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 是一个分词类型和一个语义值,同时维护输入指针。
我想从以前缀表示法排序的数组创建数学表达式解析树。 (顺便说一句,使用 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 是一个分词类型和一个语义值,同时维护输入指针。