括号、大括号、副括号匹配的 2 项测试失败

Failing 2 tests in bracket,braces, paranthesis matching

提问人：bluediager 提问时间：10/24/2023 最后编辑：Okabluediager 更新时间：10/24/2023 访问量：91

问：

试图让所有测试用例都通过，但根据测试用例的不同，我总是得到很少或很多测试用例错误。我有一种感觉，好像我错过了一些重要的东西，但无数个小时后，我仍然不知道我错过了什么。

测试用例： 12 是字符串数，后跟字符串数 空行是要测试的第一个字符串。

12

([])
(([()])))
([()[]()])()
(([()])
([])
(([()])))
([()[]()])()
(
(]
)(
][

预期输出：

Yes
Yes
No
Yes
No
Yes
No
Yes
No
No
No
No

我的输出：

Yes
Yes
No
Yes
Yes // should be no
Yes
No
Yes
Yes // should be no
No
No
No

失败案例：

([])
(

main.c

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


void ClearKeyboardBuffer(void) {
    char c;
    int noc;
    noc = scanf("%c", &c);
    
    while (noc == 1 && c != '\n') {
        scanf("%c", &c);
    }
}

Boolean isMatch(void) {
    STACK hStack;
    int noc;
    char c;
    Boolean m = TRUE;
    
    hStack = StackInitDefault();
    if (hStack == NULL) {
        printf("Failed to allocate space for stack object.\n");
        exit(2);
    }

    noc = scanf("%c", &c);
   
    
    while (noc == 1 && c != '\n') {
        if (StackIsEmpty(hStack)) {
            if (c == '(' || c == '[' || c == '{') {
                StackPush(hStack, c);
            } else if (c == ')' || c == ']' || c == '}') {
                m = FALSE;
            }
        } else if (!StackIsEmpty(hStack)) {
            if (c == '(' || c == '[' || c == '{') {
                StackPush(hStack, c);
            } else if (c == ')' || c == ']' || c == '}') {
                if (c == ')' && StackTop(hStack, NULL) == '(') {
                    StackPop(hStack);
                } else if (c == ']' && StackTop(hStack, NULL) == '[') {
                    StackPop(hStack);
                } else if (c == '}' && StackTop(hStack, NULL) == '{') {
                    StackPop(hStack);
                } else {
                    m = FALSE;
                }
            }
        }
        noc = scanf("%c", &c);
    }
    
    return  m;
}

int main(int argc, const char * argv[]) {
    STACK hStack;
    int n;
 
    hStack = StackInitDefault();  // initialize the object
    if (hStack == NULL) {
        printf("Failed to allocate space for stack object.\n");
        exit(1);
    }
    
    scanf("%d", &n);  // get number of strings that the user will be inputting
    ClearKeyboardBuffer();
    
    while (n--) {
        if (isMatch()) {
            printf("Yes\n");
        } else {
            printf("No\n");
        }
        while (!StackIsEmpty(hStack)) {
            StackPop(hStack);
        }
    }
    
    StackDestroy(&hStack);
    
    return 0;
}

堆栈.c

#include <stdio.h>
#include <stdlib.h>
#include "stack.h"
#include "status.h"


struct node;
typedef struct node Node;

struct node {
    char value;
    Node* next;
};

struct stack {
    Node* head;
};
typedef struct stack Stack;

STACK StackInitDefault(void) {
    Stack* pStack = (Stack*)malloc(sizeof(Stack));
    
    if (pStack != NULL) {  
        pStack->head = NULL;
    }
    
    return pStack;
}
    
Boolean StackIsEmpty(STACK hStack) {
    Stack* pStack = (Stack*)hStack;
    
    return (pStack->head == NULL)?TRUE:FALSE;
}

char StackTop(STACK hStack, Status* pStatus) {
    Stack* pStack = (Stack*)hStack;
    
    if (StackIsEmpty(hStack)) {
        if (pStatus != NULL) {
            *pStatus = FAILURE;
        }
        return 'e';
    }
    if (pStatus != NULL) {
        *pStatus = SUCCESS;
    }
    return pStack->head->value;
}


Status StackPush(STACK hStack, char c) {
    Stack* pStack = (Stack*)hStack;
    Node* temp = (Node*)malloc(sizeof(Node));
    
    if (temp == NULL) {
        return FAILURE;
    }
    
    temp->value = c;
    temp->next = pStack->head;
    pStack->head = temp;
    
    return SUCCESS;
}

Status StackPop(STACK hStack) {
    Stack* pStack = (Stack*)hStack;
    Node* temp;
    
    if (StackIsEmpty(hStack)) {
        return FAILURE;
    }
    
    temp = pStack->head;
    pStack->head = pStack->head->next;
    free(temp);
    
    return SUCCESS;
}

void StackDestroy(STACK* phStack) {
    Stack* pStack = (Stack*)*phStack;
    Node* temp = pStack->head;
    
    while (pStack->head != NULL) {
        temp = pStack->head;
        pStack->head = pStack->head->next;
        free(temp);
    }
    free(pStack);
    
    *phStack = NULL;
}

堆栈.h

#ifndef stack_h
#define stack_h
#include "status.h"


typedef void* STACK;

STACK StackInitDefault(void);

Status StackPush(STACK hStack, char c);

Status StackPop(STACK hStack);

char StackTop(STACK hStack, Status* pStatus);

void StackDestroy(STACK* phStack);

Boolean StackIsEmpty(STACK hStack);



#endif /* stack_h */

状态.h

#ifndef STATUS_H
#define STATUS_H

enum status { FAILURE, SUCCESS };
typedef enum status Status;

enum boolean { FALSE, TRUE };
typedef enum boolean Boolean;

#endif
C 解析 堆栈

评论

6赞 Fe2O3 10/24/2023
仔细看#5。请注意，处理到行的末尾将在堆栈上留下一个“打开”。代码需要测试此时输入中的堆栈是否为空。如果堆栈不为空，则该行上有一个不平衡的字符集合......
1赞 Vlad from Moscow 10/24/2023
@bluediager 你能解释一下为什么这句话“（（[（]）））”是正确的吗？
1赞 bluediager 10/24/2023
@Fe203哦，天哪，你是对的，我错过了那个简单的案例。刚刚修复了它，一切都完美无缺。谢谢！
1赞 Vlad from Moscow 10/24/2023
@bluediager 这些定义的目的是什么 enum boolean { FALSE， TRUE };typedef enum boolean 布尔值;而标头 <stdbool.h> 已经定义了 true 和 false？
1赞 bluediager 10/24/2023
@Fe2O3 你是对的，我只是想让它工作，假装它是一个空函数而不使用返回。我将编辑代码以利用返回：）

答：

1赞 Oka 10/24/2023 #1

这些评论基本上涵盖了这里的所有问题，但我将尝试进行总结。

主要问题是，为了平衡表达式，应在表达式完成解析后检查堆栈是否为空。这不会在您的代码中完成。

第二个问题是，您对某些测试用例的期望似乎是错误的（例如，期望 ）。Yes(([()])))

其他问题包括：

in 和 in 不是同一个对象。里面的对象永远不会传递给 ，而里面的对象是没有意义的。STACK hStack;mainSTACK hStack;isMatchisMatchStackDestroymain

最普遍的问题之一是此代码中有相当多的重复。结构，例如

if (StackIsEmpty(hStack)) {
    /* ... */
} else if (!StackIsEmpty(hStack)) {
   /* ... */

过于冗长。分支条件可以仅由语句暗示。else

整个 push & pop 部分花费大量时间检查不必要或冗余的条件。实际上，对于表达式中的每个角色，只需执行几件事isMatch

  • 给定一个开始字符 （， ， ），将其推送到堆栈中。([{
  • 给定结束字符 （， ， ），如果堆栈为空，或者堆栈顶部不是关联的开始字符，则返回无效结果。)]}

您实际上是在输入行方面工作，但通过一次从标准输入中读取一个字符来做到这一点。至少，有人可能会建议不要使用 ，但更不用说用 读取整行，然后将其处理为字符串的可能性，这将是失职的。只要你的线条不是很长，这很简单。getcharscanf("%c", ...)fgets

考虑到以下评论，一些明显的班级/课程/讲师/教授特定的批评：

老实说，我不确定。我确实同意很多事情看起来有点毫无意义，但教授真的很老派，他希望我们练习将堆栈对象视为不透明对象。这不是我个人制作这个项目的方式，但这是他希望我们这样做的方式。

这两者基本上都是噪音：

enum status { FAILURE, SUCCESS };
typedef enum status Status;

enum boolean { FALSE, TRUE };
typedef enum boolean Boolean;

这两个枚举都可以很容易地用 type： 表示，并且自 C99 以来一直通过 <stdbool.h> 提供（C23 将使它们成为关键字）。booltruefalse

这typedef

typedef void* STACK;

不是很好。 不需要便于使用不透明类型。不透明类型本质上只是指向不完整类型（一种没有定义的可识别类型，即有关其大小的信息）的指针。对于不透明类型，标头可以仅包含void *

typedef struct stack Stack;
Stack *StackInitDefault(void);

替换为源文件中的定义。struct stack

此外，-ing 指针有些争议，但最常见的建议是避免这样做。最重要的是，不需要将 a 显式转换为另一种指针类型，因为 a 可以隐式转换为任何其他指针类型。typedefvoid *void *

(如果你的编译器在抱怨，你可能使用的是 C++ 编译器，而不是 C 编译器。)

同样，做任何你需要做的事情来通过课程，但其中一些要求不是好的做法。

下面是一个遵循上述大部分建议的实现。它避免了 -ing 一起。 不存在，因为它不需要。它只是检查所有输入行（而不是从第一行派生的固定数量的行），或者运行当前的测试用例。typedefStackTop

一些典型的边缘情况：将空指针传递给任何库函数，或弹出一个空堆栈都是未定义的行为，并将其参数保留为调用者处理的悬空指针（模仿）。StackDestroyfree

用法示例：

$ ./a.out tests
"" -> PASS
"([])" -> PASS
"(([()])))" -> PASS
"([()[]()])()" -> PASS
"(([()])" -> PASS
"(([()])" -> PASS
"(([()])))" -> PASS
"([()[]()])()" -> PASS
"(" -> PASS
"(]" -> PASS
")(" -> PASS
"][" -> PASS

$ ./a.out 
[]
"[]" true
({[]})
"({[]})" true
int main(int argc, char *argv[]) { puts("Hello world!"); }
"int main(int argc, char *argv[]) { puts("Hello world!"); }" true
)()(((){}{})()
")()(((){}{})()" false

代码：

stack.h:

#ifndef STACK_H
#define STACK_H

#include <stdbool.h>

struct stack;

struct stack *StackInitDefault(void);
bool          StackIsEmpty(struct stack *);
bool          StackPush(struct stack *, char);
char          StackPop(struct stack *);
void          StackDestroy(struct stack *);

#endif

stack.c:

#include <stdlib.h>
#include "stack.h"

struct node {
    char value;
    struct node *prev;
};

struct stack {
    struct node *top;
};

struct stack *StackInitDefault(void)
{
    return calloc(1, sizeof (struct stack));
}

bool StackIsEmpty(struct stack *s)
{
    return !s->top;
}

bool StackPush(struct stack *s, char c)
{
    struct node *n = malloc(sizeof *n);

    if (!n)
        return false;

    n->value = c;
    n->prev = s->top;
    s->top = n;

    return true;
}

char StackPop(struct stack *s)
{
    struct node *n = s->top;
    char value = n->value;

    s->top = n->prev;
    free(n);

    return value;
}

/* slightly inefficient being written in terms of `StackPop`,
 * but keeps things simple */
void StackDestroy(struct stack *s)
{
    while (!StackIsEmpty(s))
        (void) StackPop(s);

    free(s);
}

main.c:

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

#include "stack.h"

#define stringify(b) ((b) ? "true" : "false")

/* running out of memory renders this program useless
 * bail out, let the OS clean up */
static void fatal_memory(void)
{
    fputs("CRITICAL: Out of memory.\n", stderr);
    exit(EXIT_FAILURE);
}

static char invert(char c)
{
    switch (c) {
        case '(': return ')';
        case '[': return ']';
        case '{': return '}';
    }

    return '\0';
}

static bool is_balanced(const char *data)
{
    struct stack *st = StackInitDefault();

    if (!st)
        fatal_memory();

    for (char c; (c = *data); data++) {
        switch (c) {
            case '(':
            case '[':
            case '{':
                if (!StackPush(st, c))
                    fatal_memory();
                break;
            case ')':
            case ']':
            case '}':
                if (StackIsEmpty(st) || invert(StackPop(st)) != c) {
                    StackDestroy(st);
                    return false;
                }
                break;
        }
    }

    bool result = StackIsEmpty(st);

    StackDestroy(st);

    return result;
}

static void do_basic_testcases(void)
{
    const struct {
        const char *string;
        const bool expect;
    } tests[] = {
        { "",             true  },
        { "([])",         true  },
        { "(([()])))",    false },
        { "([()[]()])()", true  },
        { "(([()])",      false },
        { "(([()])",      false },
        { "(([()])))",    false },
        { "([()[]()])()", true  },
        { "(",            false },
        { "(]",           false },
        { ")(",           false },
        { "][",           false }
    };

    for (size_t i = 0; i < sizeof tests / sizeof *tests; i++) {
        bool expect = tests[i].expect;
        bool actual = is_balanced(tests[i].string);

        printf("\"%s\" -> ", tests[i].string);

        if (expect == actual)
            puts("PASS");
        else
            printf("FAIL: `%s` expected, got `%s`\n", stringify(expect), stringify(actual));
    }
}

int main(int argc, char **argv)
{
    if (argc > 1 && 0 == strcmp("tests", argv[1]))
        do_basic_testcases();
    else {
        char line[4096];

        while (fgets(line, sizeof line, stdin)) {
            line[strcspn(line, "\n")] = '\0';
            printf("\"%s\" %s\n", line, stringify(is_balanced(line)));
        }
    }
}

评论

0赞 Oka 10/24/2023
@Fe2O3并不表示有效性，而是表示测试用例的行为符合预期。PASS
0赞 Fe2O3 10/24/2023
哎呀。被误解的“PASS”......我的错... ：-）

上一个：在不知道位置的情况下将子字符串添加到字符串

下一个：使用 CFF 资源管理器和 msdn doc 分析 PE 文件以查找导出表地址