c - 如何调试树求和和运行时错误？

Question

我正在看problem 112来自弗吉尼亚大学在线法官。

几周前，我从大学收到了一些作业，事情是，尽管 UVa 接受了其他问题，但我无法弄清楚这个问题出了什么问题。我已经运行了来自 Udebug website 的输入没有问题。我仔细检查了结果，现在我厌倦了解决这个问题。

以下是有关所发生事件的详细信息。首先，我将 BUFSIZE 增加到 2^20 以避免任何内存溢出。结果？失败的。其次，我缩小了堆栈中元素的大小。结果？失败的。最后，为了以防万一，我删除了结果的 eol 字符。结果？失败。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

#define BUFSIZE 16384

typedef struct node {
    int element[BUFSIZE];
    int size;
    int current;
}Stack;//This is a stack I made

static Stack *stack;
static int level;//This is a level of a node in the whole tree
static int integer;//This is an integer that should be came out from the sum() function

bool initialize(void) {
    if (stack == NULL)
        stack = (Stack *)malloc(sizeof(Stack));

    stack->size = BUFSIZE;
    stack->current = 0;
    return true;
}

bool push(int number) {
    if (stack == NULL)
        return false;
    if ((stack->current + 1) > stack->size)
        return false;

    stack->element[stack->current] = number;
    stack->current++;
    return true;
}

int pop() {
    if (stack->current <= 0)
        return 0xFFFFFFFF;
    stack->current--;
    return stack->element[stack->current];
}

int sum() {
    int result = 0;
    int i;
    if (stack == NULL)
        return 0xFFFFFFFF;
    if (stack->current == 0)
        return 0xFFFFFFFF;

    for (i = 0; i < stack->current; i++)
        result += stack->element[i];

    return result;
}//Sum all the values in the stack and return it.

void replace(char * o_string, char * s_string, char * r_string) {
    char *buffer = (char *)calloc(BUFSIZE, sizeof(char));
    char * ch;

    if (!(ch = strstr(o_string, s_string)))
        return;
    strncpy(buffer, o_string, ch - o_string);
    buffer[ch - o_string] = 0;
    sprintf(buffer + (ch - o_string), "%s%s", r_string, ch + strlen(s_string));
    o_string[0] = 0;
    strcpy(o_string, buffer);
    free(buffer);
    return replace(o_string, s_string, r_string);
}//This is a function I found on Google. Memory usage optimization is not guaranteed.


int main(void) {
    char *buffer;
    char *line;
    char *restOfTheString;
    char *token;
    bool checked = false, found = false;

    int i = 0, j = 0, scannedInteger, result = 0, array[4096];

    buffer = (char *)calloc(BUFSIZE, sizeof(char));
    restOfTheString = (char *)calloc(BUFSIZE, sizeof(char));
    line = (char *)calloc(BUFSIZE, sizeof(char));
    memset(buffer, 0, BUFSIZE);
    for (i = 0; i < 4096; i++) {
        array[i] = -1;
    }
    level = 0;
    integer = 0;

    while (fgets(line, sizeof(line), stdin) != NULL) {//Get input line by line
        if (line[0] != '\n') {
            token = strtok(line, "\n");
            if (strlen(line) >= 1) {
                strcat(buffer, token);
            }
        }   
    }

    replace(buffer, " ", "");
    replace(buffer, "()()", "K");

    strcpy(restOfTheString, buffer);
    i = 0;
    while (restOfTheString[i] != 0) {
        if (level == 0 && !checked) {//If the level of the node is 0, then it is clearly the summed value I need to find out on the whole tree.
            initialize();
            sscanf(&restOfTheString[i], "%d%s", &integer, &restOfTheString[0]);
            i = -1;
            checked = true;
        }

        if (restOfTheString[i] == '(') {
            checked = false;
            level++;
        }//If there is an openning bracket, then increase the level of the node.
        else if (restOfTheString[i] == ')') {
            if (restOfTheString[i - 1] != '(')
                if (pop() == 0xFFFFFFFF)
                    return 0;
            level--;
            if (!found && level == 0) {
                array[j] = 0;
                j++;
                free(stack);
                stack = NULL;
            }//If there is a closing bracket, then it's time to check whether the level of the node is 0. If the level of the node is 0, then we need to report the result to the 'array' which is an integer array and move on to the next input.
            else if (found && level == 0) {
                array[j] = 1;
                j++;
                free(stack);
                stack = NULL;
                found = false;
            }
        }
        else if (restOfTheString[i] == '-' && !checked) {
            if (sscanf(&restOfTheString[i], "%d%s", &scannedInteger, &restOfTheString[0]) == 2) {
                if (push(scannedInteger) == false)
                    return 0;
                i = -1;
            }
        }//If there is a minus character, then it's obvious that the next couple of characters are a negative integer and I need to scan it out of the whole input.
        else if (restOfTheString[i] >= 48 && restOfTheString[i] <= 57 && !checked) {
            if (sscanf(&restOfTheString[i], "%d%s", &scannedInteger, &restOfTheString[0]) == 2) {
                if (push(scannedInteger) == false)
                    return 0;
                i = -1;
            }
        }//If there is a numerous character, then it's obvious that the next couple of characters are a negative integer and I need to scan it out of the whole input.

        else if (restOfTheString[i] == 'K') {
            if ((result = sum()) == 0xFFFFFFFF)
                return 0;
            if (result == integer) {
                found = true;
            }
        }//The 'K' character means the integer scanned prior to this iteration is a value in a leaf. So I need to call the sum() function in order to figure it out the result.
        i++;
    }
    i = 0;
    while (array[i] != -1) {
        if (array[i] == 1)
            printf("yes\n");
        else if (array[i] == 0)
            printf("no\n");
        i++;
    }
    return 0;
}

虽然内存使用情况明显可疑，但我不知道如何跟踪系统上的堆栈。

Answer 1

您使用了许多有问题的做法。

• 您从头开始释放并重新分配堆栈。在您的情况下，堆栈的大小是固定的；在 main 的开头分配一个，最后释放一次。

• 您将索引i设置为-1作为指示符，但稍后继续访问restOfString[i]。 restOfString 是一个分配的字符串，在实际数据之前写入字节可能会破坏系统为分配的内存保留的内部信息。这可能会导致释放时出现错误。无论如何，这是未定义的行为。

• 您逐行读取输入并将所有内容连接成一个巨大的字符串。您可以使用 strcat 来实现此目的，随着字符串的增长，它会变慢。如果必须将所有内容加载到大缓冲区中，请考虑使用 fread。

• 您的递归replace方法还会对临时分配的缓冲区进行大量复制。

• 这个:

  sscanf(&rest[i], "%d%s", &integer, &rest[0]);
  

  看起来很可疑。您将结果存储在您正在读取的字符串中，尽管索引不同。结果和来源可能重叠，这可能是未定义的行为。无论如何，这都需要大量的复制。您可以使用 strtol 读取整数，而不是使用 sscanf，它会在解析数字后给出字符串的位置。继续在结果偏移处扫描旧字符串。

您的问题似乎不在于核心算法，而在于读取输入。我assignment没有提到最大线路长度。这可能表明您不应该在行上下文中读取输入。

您可以使用不知道换行符的scanf函数。您可以利用扫描不成功的情况进行数据转换，例如扫描一个整数，重置输入流。

这样的策略只需要当前 token 的存储。如果使用递归，甚至不需要堆栈。我怀疑在线判断中的测试用例是否会突破堆栈限制，即使它们包含深度较大的退化树。