семантическая ошибка с балансировкой скобок здесь - PullRequest
Новая
       14

семантическая ошибка с балансировкой скобок здесь

0 голосов
/ 25 декабря 2018

Я написал код 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] = '\0';
    n = (char*)malloc(sizeof(char) * 3);
    n[0] = 'N';
    n[1] = 'O';
    n[2] = '\0';

    while (s[i] != '\0') {
        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);
}

обновленный код: 

#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] != '\0') {
        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);
}

Ответы [ 4 ]

0 голосов
/ 27 декабря 2018

Вот некоторые основные проблемы в вашем коде:

  • вы неправильно инициализируете стек с create(sptr) перед использованием, предпочтительно в main(), где он определен.Ваш код имеет неопределенное поведение.Он печатает NO случайно, вероятно потому, что sptr->top имеет начальное значение 0, что делает стек непустым.

  • вы должны выскочить из стека, только когда вы встретите закрывающий разделитель ), ] или }.

  • васследует предотвратить потенциальное переполнение буфера, указав scanf() максимальное количество символов для чтения в c: scanf("%20s", c).Кроме того, вы должны проверить возвращаемое значение, чтобы избежать неопределенного поведения в конце файла.

  • Обратите также внимание на то, что 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] != '\0'; 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;
}
0 голосов
/ 25 декабря 2018

Я бы добавил флаги, чтобы увидеть, какой из них не соответствует 

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

0 голосов
/ 25 декабря 2018

Я предполагаю, что идея такова: всегда разрешается открывающая область (в анализируемом тексте), но конечная часть должна соответствовать последней открытой.Вот почему требуется стек.Кроме того, в конце концов, если стек не пустой, это означает, что некоторые парены не были закрыты.

Итак, вам следует использовать стек, но только когда вы встречаете парены - либо открывающиеся, либо закрывающиеся.

В функции isBalanced () основной цикл может быть таким: 

while (s[i] != '\0') {
    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, потому что он должен проверять, совпадает ли аргумент с вершиной стека.Если это так, вытолкните стек и верните 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;
}

Обратите внимание, что код довольно хорошо отражает «анализ»;когда анализ короткий и четкий, а код следует за анализом, результат часто также короткий и четкий.

0 голосов
/ 25 декабря 2018

В вашей функции pop вы не уменьшаете top, поэтому ваша функция isEmpty всегда возвращает false.

Следовательно, вы возвращаете 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 '$';
}
...