0 / 0 / 0
Регистрация: 14.07.2023
Сообщений: 5
1

Правильная скобочная последовательность

14.07.2023, 07:05. Показов 675. Ответов 10

Author24 — интернет-сервис помощи студентам
Здравствуйте, не могу понять в чем проблема, тесты либо проходятся либо возникает ошибка во время выполнения работы
Собственно сама задача: Задачу обязательно решать через список

Рассмотрим последовательность, состоящую из круглых, квадратных и фигурных скобок. Программа дожна определить, является ли данная скобочная последовательность правильной.

Пустая последовательность явлется правильной. Если A – правильная, то последовательности (A), [A], {A} – правильные. Если A и B – правильные последовательности, то последовательность AB – правильная.

Входные данные
В единственной строке записана скобочная последовательность, содержащая не более 100000 скобок.

Выходные данные
Если данная последовательность правильная, то программа должна вывести строку yes, иначе строку no.

Мой код:


C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#include<stdio.h>
#include<malloc.h>
#include<string.h>
 
struct Elem {
    char Data[1];
    struct Elem* Next;
};
 
struct MyList {
    struct Elem* Head;
    struct Elem* Tail;
    int Size;
};
 
void init(struct MyList* L) {
    L->Head = NULL;
    L->Tail = NULL;
    L->Size = 0;
}
 
int size(struct MyList* L){
    return (L->Size);
}
 
char* back(struct MyList* L) {
    if (L->Size == 0) {
        return NULL;
    }
 
    return L->Tail->Data;
}
 
void push_back(char* s, struct MyList* L) {
    struct Elem* N = (struct Elem*)malloc(sizeof(struct Elem));
    strcpy(N->Data, s);
    N->Next = NULL;
    if (L->Size == 0) {
        L->Head = N;
        L->Tail = N;
    }
    else {
        L->Tail->Next = N;
        L->Tail = N;
    }
    L->Size++;
}
 
void pop_front(struct MyList* L) {
    if (L->Size == 0) {
        return;
    }
    struct Elem* T = L->Head->Next;
    free(L->Head);
    L->Head = T;
    L->Size--;
    if (L->Size == 0)
        L->Tail = NULL;
 
    return;
}
 
void pop_back(struct MyList* L) {
    if (L->Size == 0) {
        return;
    }
    if (L->Size == 1){
        pop_front(L);
        return;
    }
    struct Elem* T = L->Head;
    while(T->Next != L->Tail)
        T = T->Next;
    free(L->Tail);
    L->Tail = T;
    T->Next = NULL;
    L->Size--;
 
    return;
}
 
int main(void) {
    char s[100000];
    char a[1];
    char* b;
    int n;
    struct MyList List;
    init(&List);
    scanf("%s",s);
    int len = strlen(s);
    for (int i = 0 ; i < len; i++){
        n = (size(&List));
        if (s[i]=='('){
            strcpy(a, "(");
            push_back(a, &List);
        } else if (s[i]=='['){
            strcpy(a, "[");
            push_back(a, &List);
        } else if (s[i]=='{'){
            strcpy(a, "{");
            push_back(a, &List);
        } else if (s[i]==')'){
            if (n==0){
                printf("no");
                exit(0);
            } else {
                b = back(&List);
                if (strcmp(b, "(")==0){
                    pop_back(&List);
                } else{
                    printf("no");
                    exit(0);
                }
            }
        } else if (s[i]==']'){
            if (n==0){
                printf("no");
                exit(0);
            } else {
                b = back(&List);
                if (strcmp(b, "[")==0){
                    pop_back(&List);
                } else{
                    printf("no");
                    exit(0);
                }
            }
        } else if (s[i]=='}'){
            if (n==0){
                printf("no");
                exit(0);
            } else {
                b = back(&List);
                if (strcmp(b, "{")==0){
                    pop_back(&List);
                } else{
                    printf("no");
                    exit(0);
                }
            }
        } else{
            break;
        }
    }
    int ans = size(&List);
    if (ans == 0){
        printf("yes");
    } else{
        printf("no");
    }
    return 0;
}
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
14.07.2023, 07:05
Ответы с готовыми решениями:

Определить, является ли данная скобочная последовательность правильной
Рассмотрим последовательность, состоящую из круглых, квадратных и фигурных скобок. Программа должна...

Проверить, является ли введенная скобочная последовательность правильной (рекурсия)
Дано слово из круглых и фигурных скобок. Требуется определить является ли введенное выражение...

Добавление в последовательность цифр и знаков операций так чтобы получилось правильная скобочная последовательность
Баланс скобок Дана последовательность, состоящая из открывающихся и закрывающихся круглых,...

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

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

10
Заблокирован
14.07.2023, 08:53 2
Кто, блин, вас учит так исходники форматировать? Читать жэж невозможно! Как-будто макака жопой по клавиатуре попрыгала.
--------------
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// проверка правильной расстановки скобок в строке s
#define push(sp, value)  (*sp++ = (value))
#define pop(sp) (*--sp)
 
bool check_brackets(char* s)
{
  unsigned len = strlen(s);
  if (!len) return true;
  
  char *stack = (char*)malloc(len) /*new char[len]*/, *sp = stack; 
  bool error = false;
  
  for (; !error && *s; s++)  
    switch (*s)
    {
      case '(': push(sp, ')'); break;
      case '[': push(sp, ']'); break;
      case '{': push(sp, '}'); break;
      case ')':
      case ']': 
      case '}': error = (sp == stack) || (pop(sp) != *s);
    } 
  
  error |= sp != stack;
  free(stack); // delete []stack; 
  return !error; 
}
1
2523 / 1243 / 459
Регистрация: 08.11.2016
Сообщений: 3,415
14.07.2023, 11:27 3
Лучший ответ Сообщение было отмечено DaZer228 как решение

Решение

Цитата Сообщение от DaZer228 Посмотреть сообщение
C
1
char Data[1];
зачем здесь массив на один элемент?

Код ужасен

Цитата Сообщение от Verevkin Посмотреть сообщение
Кто, блин, вас учит так исходники форматировать?
Поддерживаю. Однако
Цитата Сообщение от DaZer228 Посмотреть сообщение
Задачу обязательно решать через список
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <stdio.h>
#include <stdlib.h>
 
typedef struct TypeNode {
    char data;
    struct TypeNode *next;
} List;
 
List * createList(void)
{
    List *ret = (List *)malloc(sizeof (List));
    ret->data = 0;
    ret->next = NULL;
    return ret;
}
 
void deleteList(List *head)
{
    while (head) {
        List *tmp = head;
        head = head->next;
        free(tmp);
    }
}
 
List * push(char c, List *head)
{
    List *ret = createList();
    ret->data = c;
    ret->next = head;
    return ret;
}
 
List * pop(List *head)
{
    List *ret = head ? head->next : head;
    free(head);
    return ret;
}
 
int isOpening(char c)
{
    return c == '(' || c == '{' || c == '[';
}
 
int isClosingFor(char cOp, char cCl)
{
    return cOp == '(' ? cCl == ')' : (cOp == '{' ? cCl == '}' : (cOp == '[' ? cCl == ']' : 0));
}
 
int main(void)
{
    List *stack = NULL;
 
    char ch = 0;
    while (ch != '\n') {
        ch = getchar();
        if (isOpening(ch)) {
            stack = push(ch, stack);
        } else if (stack && isClosingFor(stack->data, ch)) {
            stack = pop(stack);
        } else {
            break;
        }
    }
 
    int res = 0;
    if (ch != '\n') {
        res = -1;
        while (ch != '\n') {
            ch = getchar();
        }
    }
 
    printf("%s\n", !res && !stack ? "Yes" : "No");
    deleteList(stack);
 
    return 0;
}
Verevkin, Ваш кот мне нравится, предложу небольшую оптимизацию
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#define push(sp, value)  (*sp++ = (value))
#define pop(sp) (*--sp)
 
bool check_brackets(char* s)
{
    unsigned len = strlen(s);
    if (!len) return true;
    else if (len % 2) return false;
    len /= 2;
 
    char *stack = (char*)malloc(len) /*new char[len]*/, *sp = stack;
    bool error = false;
    for (; !error && *s; s++)
        switch (*s)
        {
        case '(': push(sp, ')'); break;
        case '[': push(sp, ']'); break;
        case '{': push(sp, '}'); break;
        case ')':
        case ']':
        case '}': error = (sp == stack) || (pop(sp) != *s) || stack - sp >= len;
        }
 
    error |= sp != stack;
    free(stack); // delete []stack;
    return !error;
}
0
Заблокирован
14.07.2023, 15:47 4
Цитата Сообщение от Annemesski Посмотреть сообщение
предложу небольшую оптимизацию
Нахрена проверять длину на чётность? Функция проверяет скобки с учётом присутствия других символов в строке, которых может быть от 0 до over9000 штук.
0
2523 / 1243 / 459
Регистрация: 08.11.2016
Сообщений: 3,415
14.07.2023, 15:53 5
Цитата Сообщение от Verevkin Посмотреть сообщение
с учётом присутствия
по заданию на вход подается скобочная последовательность, то есть гарантируется что будут только скобки.
0
Заблокирован
14.07.2023, 20:37 6
Цитата Сообщение от Annemesski Посмотреть сообщение
по заданию
Да пох на задание, я эту функцию давно написал.
0
0 / 0 / 0
Регистрация: 14.07.2023
Сообщений: 5
14.07.2023, 21:16  [ТС] 7
Annemesski, Я немного исправил код теперь на двух тестах превышено максимальное время работы, можете пожалуйста подсказать как можно оптимизировать мой код?
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include<stdio.h>
#include<malloc.h>
#include<string.h>
 
struct Elem {
    char Data;
    struct Elem* Next;
};
 
struct MyList {
    struct Elem* Head;
    struct Elem* Tail;
    int Size;
};
 
void init(struct MyList* L) {
    L->Head = NULL;
    L->Tail = NULL;
    L->Size = 0;
}
 
int size(struct MyList* L){
    return (L->Size);
}
 
char back(struct MyList* L) {
    return L->Tail->Data;
}
 
void push_back(char s, struct MyList* L) {
    struct Elem* N = (struct Elem*)malloc(sizeof(struct Elem));
    N->Data = s;
    N->Next = NULL;
    if (L->Size == 0) {
        L->Head = N;
        L->Tail = N;
    }
    else {
        L->Tail->Next = N;
        L->Tail = N;
    }
    L->Size++;
}
 
void pop_front(struct MyList* L) {
    struct Elem* T = L->Head->Next;
    free(L->Head);
    L->Head = T;
    L->Size--;
    if (L->Size == 0)
        L->Tail = NULL;
 
    return;
}
 
void pop_back(struct MyList* L) {
    if (L->Size == 1){
        pop_front(L);
        return;
    }
    struct Elem* T = L->Head;
    while(T->Next != L->Tail)
        T = T->Next;
    free(L->Tail);
    L->Tail = T;
    T->Next = NULL;
    L->Size--;
 
    return;
}
 
int main(void) {
    char s[100000];
    char b;
    int n;
    struct MyList List;
    init(&List);
    scanf("%s",s);
    int len = strlen(s);
    for (int i = 0 ; i < len; i++){
        n = (size(&List));
        if (s[i]=='(' || s[i] == '{' || s[i] == '['){
            push_back(s[i], &List);
        } else if (s[i]==')'){
            if (n==0){
                printf("no");
                exit(0);
            } else {
                b = back(&List);
                if (b=='('){
                    pop_back(&List);
                } else{
                    printf("no");
                    exit(0);
                }
            }
        } else if (s[i]==']'){
            if (n==0){
                printf("no");
                exit(0);
            } else {
                b = back(&List);
                if (b=='['){
                    pop_back(&List);
                } else{
                    printf("no");
                    exit(0);
                }
            }
        } else if (s[i]=='}'){
            if (n==0){
                printf("no");
                exit(0);
            } else {
                b = back(&List);
                if (b=='{'){
                    pop_back(&List);
                } else{
                    printf("no");
                    exit(0);
                }
            }
        } else{
            break;
        }
    }
    int ans = size(&List);
    if (ans == 0){
        printf("yes");
    } else{
        printf("no");
    }
    return 0;
}
Добавлено через 6 минут
Annemesski, скорее всего что-то не так с самим списком, вроде как с логикой в мейне все хорошо
0
Вездепух
Эксперт CЭксперт С++
11691 / 6370 / 1723
Регистрация: 18.10.2014
Сообщений: 16,052
14.07.2023, 21:19 8
Цитата Сообщение от DaZer228 Посмотреть сообщение
#include<malloc.h>
Что это?

Цитата Сообщение от DaZer228 Посмотреть сообщение
C
1
2
  return;
}
Почему в некоторых void-функциях в конце болтается явный return? (А в некоторых - нет)

Цитата Сообщение от DaZer228 Посмотреть сообщение
теперь на двух тестах превышено максимальное время работы
Потому что у вас в коде используется функция pop_back, которая дико тормозит.

Функции push_back и pop_back из кода выкинуть и забыть о них навсегда. Все должно быть написано на функциях push_front и pop_front.
0
0 / 0 / 0
Регистрация: 14.07.2023
Сообщений: 5
14.07.2023, 21:25  [ТС] 9
TheCalligrapher,
функция malloc нужна для выделения доп памяти;
а насчет pop_back, и push_back, я же хочу решить задачу через дек, а в деке мы добавляем в конец и удаляем с конца
0
Вездепух
Эксперт CЭксперт С++
11691 / 6370 / 1723
Регистрация: 18.10.2014
Сообщений: 16,052
14.07.2023, 21:45 10
Цитата Сообщение от DaZer228 Посмотреть сообщение
функция malloc нужна для выделения доп памяти;
Я не спрашивал ничего про "функцию malloc". Я спрашивал про странный #include <malloc.h>. В стандартной библиотеке нет никакого <malloc.h>. Поэтому и возникает вопрос: что это и зачем вы это вписали в свой код?

Цитата Сообщение от DaZer228 Посмотреть сообщение
а насчет pop_back, и push_back, я же хочу решить задачу через дек, а в деке мы добавляем в конец и удаляем с конца
Во-первых, что это за странный "дек" такой ? В обычном деке можно и добавлять, и удалять с обоих концов.

Во-вторых, эта задача решается через стек. Без вариантов. Если вам приспичило использовать дек в качестве стека - флаг вам в руки. Но почему вы решили, что использовать дек в качестве стека можно только "с конца" - мне в упор не ясно.

Во-третьих, где у дека "начало", а где - "конец", решаете вы. Назовите "начало" "концом" - и проблема решена.

В любом случае, какой бы вариант решения вы ни выбрали, пока у вас в процессе решения вызывается вот эта тормозня

C
1
2
     while(T->Next != L->Tail)
        T = T->Next;
будет вылетать нарушение по времени.
1
0 / 0 / 0
Регистрация: 14.07.2023
Сообщений: 5
14.07.2023, 21:50  [ТС] 11
TheCalligrapher,
Да, спасибо, переписал на начало а не на конец и все зашло, спасибо
0
14.07.2023, 21:50
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
14.07.2023, 21:50
Помогаю со студенческими работами здесь

Правильная скобочная последовательность
Напомним, что называется правильной скобочной последовательностью: пустая строка является...

Правильная скобочная последовательность
Рассмотрим последовательность, состоящую из круглых, квадратных и фигурных скобок. Программа дожна...

Правильная скобочная последовательность
Правильная скобочная последовательность Напишите программу, которая определяет, является ли...

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

Правильная скобочная последовательность
Напишите функцию is_correct_bracket(text), которая принимает в качестве аргумента непустую строку...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
11
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru