将 lisp 字符串转换为 C 语言中的树 - 程序崩溃但在 Debug模式下运行

标签 c debugging memory

我正在用 C 编写一个程序,该程序假设将表示树的字符串解析为 C 中的实际树。

字符串格式是 Lisp 风格: 例如,以下字符串“(A(B)(C)(D))”将创建一棵树,其中 A 作为根,B C D 作为 3 个子节点,

这是我的树代码:

#include <stdlib.h>
#include <stdio.h>
#include "SP_Tree.h"

typedef struct SP_NODE {
    char* value;
    int numchilds;
    struct SP_NODE* parent;
    struct SP_NODE** childs;
} SP_NODE;

SP_NODE* SPTreeCreate(char* value){
    SP_NODE *tree = (SP_NODE*)malloc(sizeof(SP_NODE));
    SP_NODE **childs = (SP_NODE**)malloc(sizeof(SP_NODE)*10);

    // initialize node data
    tree->childs = childs;
    tree->value = value;
    tree->parent = NULL;
    tree->numchilds = 0;
    return tree;
}
SP_NODE* SPInsertChild(SP_NODE* parent, SP_NODE* child, int index){
    // add node to parent in index place
    if (parent != NULL){
        parent->childs[index] = child;
        parent->numchilds++;
        child->parent = parent;
    }
    return child;
}
void SPDestroyTree(SP_NODE* root){
    if (root) {
        for (int i = 0; i < root->numchilds; i++){
            if (root->childs[i]!= NULL){
                SPDestroyTree(root->childs[i]);
            }
        }
        free(root->value);
        free(root);
    }
}

这是我的解析器代码:

SP_NODE* SPCreateLispTree(char* lisp){
    // create tree from first node
    int root_index = SPFindRoot(lisp);
    char* root_str = (char*)malloc(sizeof(char)*(root_index));
    strncpy(root_str, lisp+1, root_index -1);
    root_str[root_index-1] = '\0';
    SP_NODE* root = SPTreeCreate(root_str);

    // stop condition - current root ending with )
    if (lisp[root_index] == ')' ){
        return root;
    }

    // loop over all subtrees, add child to tree from each subtree
    int i = 0;
    int start_index = root_index;
    int next_index = SPFindNextSubtree(lisp,start_index);
    while (next_index > 0){
        // create tree from next subtree in lisp
        char* new_lisp = (char*)malloc(next_index-start_index+1);
        strncpy(new_lisp, lisp+start_index, next_index-2);
        new_lisp[next_index-start_index] = '\0';

        SP_NODE* next_child = SPCreateLispTree(new_lisp);

        // insert this new child to root
        SPInsertChild(root,next_child,i);

        // look for next subtree
        start_index = next_index;
        next_index = SPFindNextSubtree(lisp,start_index);
        i++;
    }
    return root;
}
int SPFindNextSubtree(char* lisp,int start_index){
    // run over string until we get #left_Parentheses == #right_Parentheses
    int i = start_index + 1;
    int left = 1;
    int right = 0;
    while (lisp[i] != '\0' && left != right){
        if (lisp[i] == '('){
            left++;

        }else if (lisp[i] == ')'){
            right++;
        }
        i++;
    }
    // if we finished with uneven number of Parentheses, its the last subtree
    if (left != right){
        fflush(stdout);
        return -1;
    }
    return i;
}
int SPFindRoot(char* lisp){
    // root will be from ( until first between ( or )
    // get index of first )
    char* right = strchr(lisp,')');
    int right_index = right - lisp;

    // get index of second '(' (first char will always be '(')
    char* left = strchr(lisp+1,'(');
    int left_index = left - lisp;

    // chose smaller index
    int index = right_index;
    if (left != NULL && left_index < right_index){
        index = left_index;
    }
    return index;
}

代码在字符串上递归运行,找到当前根并从该根创建一个节点,然后找到该根之后的每个子树并从中创建一个子树。

我的问题是 - 程序对于小输入运行良好 - 但对于更大的输入,例如:

char* lisp = "(+(2)(*(5)(3(2)(3))(4(!)(2))(1))(2(3)(4)))";
SP_NODE* tree = SPCreateLispTree(lisp);

我的程序崩溃了。

但是 - 当我在 Debug模式下运行时它不会崩溃 - 并且它会产生所需的输出。

不确定我做错了什么以及如何调试它。

最佳答案

childs[index] 未初始化为 NULL。 – BLUEPIXY

strncpy(new_lisp, lisp+start_index, next_index-2); -->
strncpy(new_lisp, lisp+start_index, next_index-start_index); – BLUEPIXY

关于将 lisp 字符串转换为 C 语言中的树 - 程序崩溃但在 Debug模式下运行,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/34212176/

相关文章:

android - 使用Android NDK交叉编译

c - Visual Studio : Callback function problem (__cdecl *)

c - 如何生成 stm32 代码的二进制文件?

python - GDB pretty-print : printing an array when the size is known by the parent struct

使用 Sonarqube 和 Jenkins 的 Python 内存分析器

c - 如何使用 gettimeofday() 获取程序的运行时间

android - IntelliJ IDEA 在调试的同时编辑 android 代码

java - 为什么我的 java 代码没有继续执行 if 语句?

java - 为什么会出现 "Exception in thread "AWT-EventQueue- 0"java.lang.OutOfMemoryError: Java heap space"错误?

python - 切割杆问题集的递归树