此处括号平衡的语义错误

Question

我写了一个 C 代码来检查简单的括号平衡，如果平衡，则分别打印 NO 和 YES。

问题是我得到的所有输入都是 NO。因此我认为这是一个语义错误但找不到它（我已经尝试了 2 天 :p）

有人可以帮我吗？谢谢！

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

typedef struct stack {
    char s[1000];
    int top;
} STACK;

void create(STACK *sptr) {
    sptr->top = -1;
}

int isEmpty(STACK *sptr) {
    if (sptr->top == -1)
        return 1;
    else
        return 0;
}

void push(STACK *sptr, char data) {
    sptr->s[++sptr->top] = data;
}

char pop(STACK *sptr) {
    if (isEmpty(sptr) == 0)
        return sptr->s[sptr -> top];
    else
        return '$';
}

char *isBalanced(char *s, STACK *sptr) {
    char *y, *n;
    int i = 0;
    y = (char*)malloc(sizeof(char) * 4);
    y[0] = 'Y';
    y[1] = 'E';
    y[2] = 'S';
    y[3] = '[=10=]';
    n = (char*)malloc(sizeof(char) * 3);
    n[0] = 'N';
    n[1] = 'O';
    n[2] = '[=10=]';

    while (s[i] != '[=10=]') {
        if (s[i] == '(' || s[i] == '{' || s[i] == '[') {
            push(sptr, s[i]);
        } else {
            char x = pop(sptr);
            switch (s[i]) {
              case ')':
                if (x != '(') 
                    return n;
                break;

              case '}':
                if (x != '{') 
                    return n;
                break;

              case ']':
                if (x != '[') 
                    return n;
                break;
            }
        }
        ++i;
    }

    if (isEmpty(sptr))
        return y;
    else
        return n;
}

int main() {
    STACK *sptr = (STACK *)malloc(sizeof(STACK));
    char c[21];
    int ch;
    do {
        printf("enter sequence:");
        scanf("%s", c);
        char *msg = isBalanced(c, sptr);
        printf("%s", msg);
        printf("choice?:");
        scanf("%d", &ch);
    } while(ch);
}

updated code:

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

typedef struct stack {
    char s[1000];
    int top;
} STACK;

void create(STACK *sptr) {
    sptr->top = -1;
}

int isEmpty(STACK *sptr) {
    if (sptr->top == -1)
        return 1;
    else 
        return 0;
}

void push(STACK *sptr, char data) {
    sptr->s[++sptr->top] = data;
}

char pop(STACK *sptr) {
    if (isEmpty(sptr) == 0)
        return sptr->s[sptr->top--];
    else
        return '$';
}

int isBalanced(char *s, STACK *sptr) {
    int i = 0;

    while (s[i] != '[=11=]') {
        if (s[i] == '(' || s[i] == '{' || s[i] == '[') {
            push(sptr, s[i]);
        } else {
            char x = pop(sptr);
            switch (s[i]) {
              case ')':
                if (x != '(')
                    return 0; 
                break;
              case '}':
                if (x != '{') 
                    return 0;
                break;
              case ']':
                if (x != '[') 
                    return 0;
                break;
            }
        }
        ++i;
    }

    if (isEmpty(sptr))
        return 1;
    else 
        return 0;
}

int main() {
    STACK *sptr = malloc(sizeof(STACK));
    char c[21];
    int ch;
    do {
        printf("enter sequence:");
        scanf("%s", c);
        printf("%s", (isBalanced(c, sptr) ? "YES" : "NO"));
        printf("choice?:");
        scanf("%d", &ch);

    } while(ch);
}

Answer 1

在你的 pop 函数中你没有递减 top 因此你的 isEmpty 函数总是 returns false.

因此你 return no 总是。

char* isBalanced(char* s, STACK* sptr)
{
    ....

   if(isEmpty(sptr)) return y;
   else return n;
}

以下是正确的实现方式：

char pop(STACK* sptr)
{
    if(isEmpty(sptr) == 0)
        return sptr->s[sptr->top--];
    else
        return '$';
}

Answer 2

我会添加标志以查看哪个不匹配

unsigned match(const char *f)
{
    int p = 0,s = 0,b = 0;
    while(*f)
    {
        switch(*f++)
        {
            case '(':
                p++;
                break;
            case ')':
                p -= !!p;
                break;

            case '[':
                s++;
                break;
            case ']':
                s -= !!s;
                break;

            case '{':
                b++;
                break;
            case '}':
                b -= !!b;
                break;
            default:
                break;
        }
    }
    return (!p) | ((!s) << 1) | ((!b) << 2);
}

不是堆栈版本，只是为了这个想法。添加 push 和 pop

相当容易

Answer 3

我假设这个想法是这样的：始终允许左括号（在分析的文本中），但右括号必须与最后打开的匹配。这就是为什么需要堆栈的原因。此外，最后，如果堆栈不为空，则意味着某些括号未关闭。

所以，你应该使用堆栈，但只有当你遇到括号时 - 打开或关闭。

在函数isBalanced()中，主循环可能是这样的：

while (s[i] != '[=10=]') {
    if ( s[i] == '(' || s[i] == '{' || s[i] == '[' ) {
        // opening - remember it
        push(sptr, s[i]);
    } else if ( s[i] == ')' || s[i] == '}' || s[i] == ']' ) {
        // closing - it should match
        if ( ! popmatch(sptr, s[i]) )
          return n;
    }
    ++i;
}

其余功能正常。现在，我修改了 pop() 函数：重命名为 popmatch，因为它应该检查参数是否与栈顶匹配。如果是，弹出堆栈并 return OK。所以函数将是：

char popmatch(STACK* sptr, char c) {
    // an empty stack can not match
    if (isEmpty(sptr))
      return 0;

    // not empty, can check for equality
    if ( c =! sptr->s[sptr->top] )
      return 0;
      // does not match!

    // ok, it matches so pop it and return ok
    sptr->top--;
    return 1;
}

请注意，代码很好地反映了 "analysis"；当分析简短明了，代码跟在分析之后，结果往往也简短明了。

Answer 4

以下是您的代码中的一些主要问题：

你在使用前没有正确地用 create(sptr) 初始化堆栈，最好是在定义它的 main() 中。您的代码具有未定义的行为。它偶然打印出 NO，可能是因为 sptr->top 的初始值为 0，这使得堆栈非空。
您应该只在遇到结束分隔符 )、] 或 }.
[=39= 时从堆栈弹出]
您应该通过告诉 scanf() 要读入 c 的最大字符数来防止潜在的缓冲区溢出：scanf("%20s", c)。此外，您应该测试 return 值以避免文件末尾出现未定义的行为。
另请注意，可以将 STACK 设置为局部变量以避免堆分配和潜在的分配失败，这会导致未定义的行为，因为它未经过测试。

这是更正后的版本：

#include <stdio.h>

typedef struct stack {
    char s[1000];
    int top;
} STACK;

void create(STACK *sptr) {
    sptr->top = -1;
}

int isEmpty(STACK *sptr) {
    if (sptr->top == -1)
        return 1;
    else 
        return 0;
}

void push(STACK *sptr, char data) {
    sptr->s[++sptr->top] = data;
}

char pop(STACK *sptr) {
    if (isEmpty(sptr) == 0)
        return sptr->s[sptr->top--];
    else
        return '$';
}

int isBalanced(char *s, STACK *sptr) {
    int i;

    for (i = 0; s[i] != '[=10=]'; i++) {
        switch (s[i]) {
          case '(':
          case '{':
          case '[':
            push(sptr, s[i]);
            break;
          case ')':
            if (pop(sptr) != '(')
                return 0; 
            break;
          case '}':
            if (pop(sptr) != '{') 
                return 0;
            break;
          case ']':
            if (pop(sptr) != '[') 
                return 0;
            break;
        }
    }
    return isEmpty(sptr);
}

int main() {
    STACK s, *sptr = &s;
    char c[100];
    int ch;

    do {
        printf("Enter sequence: ");
        if (scanf(" %99[^\n]", c) != 1)
            break;
        create(sptr);
        printf("%s\n", isBalanced(c, sptr) ? "YES" : "NO");
        printf("Choice? ");
        if (scanf("%d", &ch) != 1)
            break;
    } while (ch);

    return 0;
}

此处括号平衡的语义错误

semantical error with parenthesis balancing here

c

function

parentheses