C语言括号、大括号、括号匹配中2项测试不合格

我试图让所有的测试用例都通过，但是我总是得到很少或很多的测试用例，这取决于测试用例。我有一种感觉，就像我错过了一些重要的东西，但是经过无数个小时，我仍然不知道我错过了什么。
测试用例：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;
}

型
stack.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;
}

型
stack.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 */

型
status.h

#ifndef STATUS_H
#define STATUS_H
enum status { FAILURE, SUCCESS };
typedef enum status Status;
enum boolean { FALSE, TRUE };
typedef enum boolean Boolean;
#endif

型

这些评论基本上涵盖了这里的所有问题，但我将尝试进行总结。
主要的问题是，为了使表达式平衡，在表达式完成解析后，堆栈应该被检查为 * 空 *。这在代码中没有完成。
第二个问题是，您对某些测试用例的期望似乎是错误的（例如，将(([()])))期望为Yes）。
其他问题包括：
main中的STACK hStack;和isMatch中的STACK hStack;不是同一个对象。isMatch中的对象永远不会传递给StackDestroy，而main中的对象是无意义的。
最普遍的问题之一是，在这段代码中有相当多的重复。

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

字符串
分支条件可以通过一个else语句来暗示。
isMatch的整个push & pop部分花费大量时间检查不必要或冗余的条件。

给定一个开始字符（(，[，{），将其压入堆栈。
给定一个结束字符（)，]，}），如果堆栈为空，或者堆栈顶部不是相关的 * 开始字符 *，则返回 invalid 结果。

您可以有效地使用 * 行 * 的输入，但是通过从标准输入中一次阅读一个字符来实现。至少，人们可能会建议使用getchar而不是使用scanf("%c", ...)，但是如果不提到使用fgets阅读整行的可能性，那将是疏忽，然后将其处理为 string。只要你的行不是 * 非常 * 长，这是非常简单的。
一些明确的 * 类/课程/教师/教授 * 具体的批评，考虑到这一评论：
老实说，我不确定。我同意很多东西看起来有点无意义，但教授真的很老派，他希望我们练习将堆栈对象视为不透明对象。这不是我个人编写这个程序的方式，但这是他希望我们这样做的方式。
这两个基本上都是噪音：

enum status { FAILURE, SUCCESS };
typedef enum status Status;
enum boolean { FALSE, TRUE };
typedef enum boolean Boolean;

型
这两种枚举都可以很容易地用bool类型表示：true和false从C99到<stdbool.h>（C23将使它们成为keywords）。
此typedef

typedef void* STACK;

型
不太好。void *不需要促进不透明类型。不透明类型本质上只是指向 * 不完整类型 *（没有定义的可识别类型，即关于其大小的信息）的指针。对于不透明类型，您的标头可以简单地包含

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

型
使用源文件中的struct stack定义。
此外，typedef-ing指针有点争议，但最常见的建议是避免这样做。最重要的是，不需要显式转换void *到另一个指针类型，因为void *可以 * 隐式 * 转换为任何其他指针类型。
（* 如果你的编译器在抱怨，你可能使用的是C++编译器，而不是C编译器。
同样，尽你所能通过这门课，但其中一些要求不是好的做法。
下面是一个遵循上面大部分建议的实现。它避免了typedef-ing。StackTop不存在，因为它不需要。它只是检查所有输入行（而不是从第一行派生的一组行数），或者运行当前的测试用例。
一些典型的边缘案例：传递空指针到任何库函数，或弹出空堆栈都是undefined behaviour，StackDestroy将其参数作为dangling-pointer留给调用者处理（模仿free）。
示例用法：

$ ./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)));
        }
    }
}

型

展开查看全部

C语言括号、大括号、括号匹配中2项测试不合格

1条答案

相关问题

热门标签

最新问答

C语言 括号、大括号、括号匹配中2项测试不合格

1条答案

相关问题

热门标签

最新问答

C语言括号、大括号、括号匹配中2项测试不合格