尝试从堆栈构建二叉表达式树时出现以下错误。我相信问题是我在递归函数中弹出的位置,我认为我正在弹出一个空堆栈,但我不知道解决方案。
* 检测到 glibc ./interp:双重释放或损坏(快速顶部):0x0934d018 **
这是我的代码:
//This is the main
int main(int argc, char *argv[]){
TreeNode *node;
StackNode *stack = NULL;
push(&stack, "a");
push(&stack, "b");
push(&stack, "+");
//while (emptyStack(stack)!= 1){ //this while loop works correctly, which verifies that my stack implementation is working.
// printf("Top is : %sn", top(stack));
// pop(&stack);
//}
node = buildTree(stack);
//buildTree function
TreeNode *buildTree(StackNode *stack){
int integer; //to check for an integer
char *data = top(stack);
char *pch = strchr(top(stack), '.'); //to check for a double, looks for the decimal point
if (emptyStack(stack) != 0){
//stack is empty
fprintf(stderr, "Invalid expression, not enough tokens");
return NULL;
}
else if (sscanf(top(stack), "%d", &integer) != 0){
printf("parser: integer noden");
//got an integer
pop(&stack);
return makeTreeNode(data, NULL, NULL);
}
else if (pch != NULL){
printf("parser: double noden");
//got a double
pop(&stack);
return makeTreeNode(data, NULL, NULL);
}
else if ( isalpha((int)data[0])){
//got a variable
printf("parser: variable noden");
pop(&stack);
return makeTreeNode(data, NULL, NULL);
}
else{
//got an operator, recurse
printf("parser: operator noden");
pop(&stack);
return makeTreeNode(data,buildTree(stack), buildTree(stack));
}
}
//makeTreeNode
TreeNode* makeTreeNode(char token[], TreeNode* left, TreeNode* right){
//this function works correctly
这是我的堆栈函数
StackNode* makeStackNode(char* data, StackNode* next){
StackNode *node;
node = malloc(sizeof(StackNode));
node->data = data;
node->next = next;
printf("Making stack node of : %sn", data);
return node;
}
char* top(StackNode* stack){
if (emptyStack(stack)!= 0){
exit(EXIT_FAILURE);
}
else{
return stack->data;
}
}
void push(StackNode** stack, char* data){
StackNode* ptr;
ptr = makeStackNode(data, *stack);
*stack = ptr;
printf("Pushed stack node n");
}
//pop from stack
void pop (StackNode** stack){
if (emptyStack(*stack)!=0){
exit(EXIT_FAILURE);
}
else{
printf("Popping node n");
StackNode* ptr = *stack;
printf("Right before the pop, stack = %sn", top(*stack));
*stack = ptr->next;
printf("Right before the free, stack = %sn", top(*stack));
free(ptr);
}
}
//returns 1 if stack is empty, 0 if it is not empty
int emptyStack(StackNode* stack){
if (stack == NULL){
return 1;
}
else{
return 0;
}
}
打印输出:
Making stack node of : a
Pushed stack node
Making stack node of : b
Pushed stack node
Making stack node of : +
Pushed stack node
parser: operator node
Popping node
Right before the pop, stack = +
Right before the free, stack = b
parser: variable node
Popping node
Right before the pop, stack = b
Right before the free, stack = a
parser: integer node //this should be a variable node
Popping node
Right before the pop, stack = //this should be stack = a
Right before the free, stack = a //this should be blank
你的问题是这样的:
return makeTreeNode(data, buildTree(stack), buildTree(stack));
您认为传递给每个函数调用的stack
值是什么?
答:相同的值。当一个(我们不知道,不在乎哪个,因为这是一个序列点问题)时,另一个调用在同一个(现已释放的)节点上获取相同的堆栈指针,并快乐地运行,认为生活是伟大的,而实际上,它即将驶上未定义行为的道路。
您的堆栈需要按地址传递给buildTree()
,就像它在堆栈管理函数中的其他地方一样(因为这正是buildTree()
正在做的事情:管理输入堆栈)。
最后,一旦你解决了这个问题,你就需要修复该函数调用的序列点问题,但我留给你。(不是真的,见下文)
//buildTree function
TreeNode *buildTree(StackNode **stack)
{
char *data=NULL;
int integer;
if (stack == NULL)
{
//stack is empty
fprintf(stderr, "Invalid expression, not enough tokens");
return NULL;
}
// reference top of stack data
data = top(*stack);
if (strchr(data,'.') != NULL)
{
printf("parser: double noden");
pop(stack);
return makeTreeNode(data, NULL, NULL);
}
if (sscanf(data, "%d", &integer) != 0)
{
printf("parser: integer noden");
pop(stack);
return makeTreeNode(data, NULL, NULL);
}
if ( isalpha((int)data[0]))
{
printf("parser: variable noden");
pop(stack);
return makeTreeNode(data, NULL, NULL);
}
//got an operator, recurse
printf("parser: operator noden");
pop(stack);
TreeNode *rhs = buildTree(stack);
TreeNode *lhs = buildTree(stack);
return makeTreeNode(data, lhs, rhs);
}
//This is the main
int main(int argc, char *argv[])
{
TreeNode *node;
StackNode *stack = NULL;
push(&stack, "a");
push(&stack, "b");
push(&stack, "+");
node = buildTree(&stack);
}
输出
parser: operator node
parser: variable node
parser: variable node
旁注:我对buildTree()
进行了一些清理,包括您首先检查的反转:十进制或整数。 123.456 运行sscanf(data, "%d", &integer)
会很高兴地吸123
出来,这不是你想要的。