Почему нельзя пройти через этот стек? oop?

Question

Я пытаюсь сделать проверку скобок с помощью реализации стека. Программа выведет действительный код, если для ввода указан правильный шаблон скобок

input: {[()]}
output: valid

input: {()[()]}
output: valid

input: (()))
output: unvalid

continuously

Но что произойдет после того, как я введу данные:

()
the program prints this unlimited loop
valid
valid
valid
valid
valid
. . . and so on

same with
(()))

Работает нормально, если поставить break; здесь, но это не будет непрерывным и мгновенно завершит программу, и больше не будет запрашивать ввод.

if(isempty(stack)){
    printf("Valid parenthesis expression\n");
    break;
} else{
     printf("Invalid parenthesis expression\n");
     break;
}

Кажется, я не могу найти причину, почему это произошло, может кто-нибудь помочь или дать мне совет о том, что происходит? Чтобы я мог * oop запросить ввод и распечатать действительный / недействительный только один раз?

#include<stdio.h>
#include<malloc.h>
#include<string.h>

typedef struct data{

    char parent;
    struct data *next;

}DATA;

void push(DATA **stack, char parentheses);
int isempty(DATA *stack);
void pop(DATA **stack);
int top(DATA *stack);

int main(int argc, char const *argv[]){

    DATA *stack;
    char parentheses[100];
    int i, flag = 1;
    do{
        //PUSH
        stack = NULL;

        printf("Enter parentheses: ");
        scanf("%[^\n]", &parentheses);


        if(strcmp(parentheses, "-1") == 0){
            break;
        }

        for(i = 0; i < strlen(parentheses); i++){
            if(parentheses[i] == '{' || parentheses[i] == '[' || parentheses[i] == '('){
                push(&stack, parentheses[i]);
            } else if (stack == NULL){
                printf("Invalid parenthesis expression\n");
                break;
            } else if(parentheses[i] == '}' && top(stack) == '{'){
                pop(&stack);
            } else if (parentheses[i] == ']' && top(stack) == '['){
                pop(&stack);
            } else if (parentheses[i] == ')' && top(stack) == '('){
                pop(&stack);
            } else if(parentheses[i] != '{' || parentheses[i] != '[' || parentheses[i] != '(' || parentheses[i] != '}' || parentheses[i] != ']' || parentheses[i] != ']') {
                printf("Invalid parenthesis expression\n");
                break;
            }
        }

        //POP
        if(isempty(stack)){
            printf("Valid parenthesis expression\n");
        } else{
            printf("Invalid parenthesis expression\n");
        }

    }while(1);

    return 0;

}

void push(DATA **stack, char parentheses){

    DATA *node = (DATA*) malloc(sizeof(DATA));
    node -> parent = parentheses;
    node -> next = NULL;

    if(!isempty(*stack)) node->next = *stack;
    *stack = node;
}

int isempty(DATA *stack){

    if(stack == NULL) return 1;
    else return 0;

}

void pop(DATA **stack){

    DATA *temp = *stack;
    *stack = (*stack)->next;
    free(temp);

}



int top(DATA *stack){

    return stack -> parent; //STACK !ISEMPTY
}

Answer 1

scanf("%[^\n]", &parentheses);

должно быть

scanf(" %[^\n]", parentheses);

обратите внимание на пробел перед символом '%', чтобы пропустить символ новой строки, поступающий с предыдущего ввода, без второго поворота scanf ничего не делает. Чтобы обнаружить этот случай, а также любой неверный ввод, я рекомендую вам всегда проверить значение scanf , возвращаемое.

В случае, если ввод содержит не менее 100 символов, которые вы записываете из круглых скобок , do

if (scanf(" %99[^\n]", parentheses) != 1) {
  /* EOF */
  return -1;
}

круглых скобок - это массив, если вы хотите использовать «&», он указывает индекс 0, поэтому & круглые скобки [0]

Примечание флаг не используется

При обнаружении неверного регистра вы можете указать «Действительное выражение в скобках»:

pi@raspberrypi:/tmp $ ./a.out
Enter parentheses: (
Invalid parenthesis expression
Enter parentheses: )
Invalid parenthesis expression
Valid parenthesis expression

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

Поскольку вы просто сохраняете символы в стеке, это намного больше просто и дешевле в памяти просто использовать массив char. Поскольку ввод ограничен 99 (без последнего нулевого символа), стеку необходимо также сохранить 99 символов, и фактически круглые скобки могут использоваться для стека

Предложение, все еще использующее ваш стек, исправление проблем, а также сокращение числа тестов и упрощение функций стека:

#include<stdio.h>
#include<malloc.h>
#include<string.h>

typedef struct data{
  char parent;
  struct data *next;
} DATA;

void push(DATA **stack, char parentheses);
int isempty(DATA *stack);
void pop(DATA **stack);
int top(DATA *stack);

int main(int argc, char const *argv[]){
  DATA *stack = NULL;
  char parentheses[100];
  char * p;

  while (fputs("Enter parentheses: ", stdout),
         (scanf(" %99[^\n]", parentheses) == 1) && strcmp(parentheses, "-1")) {
    for (p = parentheses; *p; ++p) {
      if  ((*p == '{') || (*p == '[') || (*p == '('))
        push(&stack, *p);
      else {
        char o;

        if (*p == '}')
          o = '{';
        else if (*p == ')')
          o = '(';
        else if (*p == ']')
          o = '[';
        else
          o = 0;

        if (isempty(stack) || (top(stack) != o))
          break;

        pop(&stack);
      }
    }

    if (!isempty(stack) || *p) {
      puts("Invalid parenthesis expression");

      while (! isempty(stack))
        pop(&stack);
    }
    else if (!*p)
      puts("Valid parenthesis expression");
  }

  return 0;
}

void push(DATA **stack, char parentheses) {
    DATA *node = malloc(sizeof(DATA));

    node->parent = parentheses;
    node->next = *stack;
    *stack = node;
}

int isempty(DATA *stack) {
  return (stack == NULL);
}

void pop(DATA **stack) {
  DATA *temp = *stack;

  *stack = (*stack)->next;
  free(temp);
}

int top(DATA *stack) {
  return stack->parent;
}

Компиляция и выполнение:

pi@raspberrypi:/tmp $ gcc -g -Wall s.c
pi@raspberrypi:/tmp $ ./a.out
Enter parentheses: ({[]}())
Valid parenthesis expression
Enter parentheses: (
Invalid parenthesis expression
Enter parentheses: )
Invalid parenthesis expression
Enter parentheses: (]
Invalid parenthesis expression
Enter parentheses: -1
pi@raspberrypi:/tmp $