Вывести все правильные скобочные выражения

@Artem969 · Регистрация: 17.11.2020

Author24 — интернет-сервис помощи студентам

Задача 3:

Вывести все правильные скобочные выражения длиной N (2 ≤ N ≤ 16, N чётное), состоящие из круглых и квадратных скобок.

Пример
Исходные данные Результат
4
(()) [[]] [()] ()[] []() ()() ([]) [][]

Nishen · 25.03.2022, 13:46

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
#include <iostream>
#include <stack>
#include <string>
 
 
 
int main() {
 
    std::string example = "(()) [[]] [()] ()[] []() ()() ([]) [][]";
    std::stack<char> chars;
    bool valid = true;
 
    for (std::size_t i = 0; valid && i < example.size(); ++i) {
        switch (example[i]) {
        case '(': case '[':
            chars.push(example[i]);
            break;
 
        case ')':
            if (chars.empty() || chars.top() != '(') {
                valid = false;
            }
            else {
                chars.pop();
            }
            break;
 
        case ']':
            if (chars.empty() || chars.top() != '[') {
                valid = false;
            }
            else {
                chars.pop();
            }
            break;
 
        default:
            break;
        }
    }
 
    if (!chars.empty()) {
        valid = false;
    }
 
    std::cout << "Valid: " << std::boolalpha << valid << '\n';
    return 0;
 
}

@_Ivana · 26.03.2022, 00:06

Lisp    
        
            
                
                
                
                
            
        
    Скопировано
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
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
(defn f [n]
  (if (<= n 0)
    #{""}
    (set (concat
          (map #(str "(" % ")") (f (- n 2)))
          (map #(str "[" % "]") (f (- n 2)))
          (->> (range 2 n 2)
               (mapcat #(for [l (f %)
                              r (f (- n %))]
                          (str l r))))))))
 
(f 8)
 
user=> 
#{"[(())][]"
  "[()[][]]"
  "[([])()]"
  "([[][]])"
  "([][]())"
  "(()()())"
  "[[[]][]]"
  "[]([[]])"
  "[()([])]"
  "([][()])"
  "()()([])"
  "[][[]]()"
  "()(([]))"
  "[][[]()]"
  "()[]([])"
  "()[()()]"
  "[()]()()"
  "[]()[[]]"
  "()[[]][]"
  "(([()]))"
  "[[](())]"
  "(()()[])"
  "[()(())]"
  "()[(())]"
  "(()[])[]"
  "[](())()"
  "()[()[]]"
  "[[]][]()"
  "(()(()))"
  "[()()][]"
  "[[[]]()]"
  "(([]))[]"
  "[]([])()"
  "[](()())"
  "(()[[]])"
  "[][()][]"
  "()[([])]"
  "[][()()]"
  "([(())])"
  "[][[[]]]"
  "(()())[]"
  "[()][][]"
  "[[][[]]]"
  "(())([])"
  "[][]()()"
  "[]()()()"
  "[()()]()"
  "((()))[]"
  "([](()))"
  "[]()[][]"
  "(()())()"
  "()()()[]"
  "()[]()()"
  "[[]()][]"
  "([[()]])"
  "[][][()]"
  "[][[][]]"
  "[()()()]"
  "()[]()[]"
  "[([])][]"
  "[][][][]"
  "[][](())"
  "([])[][]"
  "(((())))"
  "()()[][]"
  "[[[][]]]"
  "([[]])[]"
  "((())())"
  "()[()][]"
  "[][]()[]"
  "[[][]][]"
  "([][])()"
  "[([][])]"
  "([]())()"
  "[[]()()]"
  "()([]())"
  "[[]]()()"
  "[[][()]]"
  "[([[]])]"
  "([[]])()"
  "[]((()))"
  "[[]][][]"
  "[[]]()[]"
  "[][()[]]"
  "[[]()[]]"
  "()[[]]()"
  "[[[[]]]]"
  "[[()]()]"
  "(())[][]"
  "[([()])]"
  "[]([][])"
  "([[]][])"
  "()(())()"
  "[[]([])]"
  "[[]][()]"
  "(())[]()"
  "[][([])]"
  "[[(())]]"
  "(())()()"
  "(()([]))"
  "([])([])"
  "[]()()[]"
  "(([])[])"
  "()[][][]"
  "[[[]()]]"
  "([])()[]"
  "[(())()]"
  "()[][]()"
  "[[[]]][]"
  "(())[[]]"
  "[(()[])]"
  "[()()[]]"
  "[[][]]()"
  "([()][])"
  "()()[()]"
  "([])[[]]"
  "([()[]])"
  "[(())[]]"
  "(()[()])"
  "[[][]()]"
  "((([])))"
  "([]()[])"
  "[](([]))"
  "[(()())]"
  "[[()]][]"
  "[]()(())"
  "[[[]]]()"
  "([][[]])"
  "([][])[]"
  "[[()]]()"
  "(([]))()"
  "()[](())"
  "()[][[]]"
  "[()][()]"
  "[[[()]]]"
  "[()[]][]"
  "()(()[])"
  "(()[])()"
  "((()()))"
  "[]()([])"
  "([()()])"
  "()[[[]]]"
  "[][][]()"
  "([]())[]"
  "((()[]))"
  "[((()))]"
  "()()[[]]"
  "()([])[]"
  "()()()()"
  "([([])])"
  "(([])())"
  "(()[][])"
  "(())[()]"
  "[[([])]]"
  "([()]())"
  "[][(())]"
  "[[][][]]"
  "[](())[]"
  "()([])()"
  "[]([])[]"
  "[][][[]]"
  "([()])[]"
  "[([])]()"
  "([][][])"
  "[()[[]]]"
  "[()[]()]"
  "[][[]][]"
  "()[[()]]"
  "([])[]()"
  "([]()())"
  "[(())]()"
  "()[[][]]"
  "[]([()])"
  "[[]()]()"
  "([[[]]])"
  "[](()[])"
  "(([[]]))"
  "()([[]])"
  "[([]())]"
  "((()))()"
  "()()[]()"
  "[][()]()"
  "[[]]([])"
  "[()]([])"
  "()(()())"
  "[]([]())"
  "(())(())"
  "()([()])"
  "[[()[]]]"
  "([()])()"
  "([[]]())"
  "[()[()]]"
  "[()[]]()"
  "()([][])"
  "([])(())"
  "[[]][[]]"
  "[[()()]]"
  "[()](())"
  "([[]()])"
  "[]()[()]"
  "([])[()]"
  "(([][]))"
  "([]([]))"
  "[(([]))]"
  "[()][[]]"
  "([])()()"
  "()((()))"
  "[[]](())"
  "()(())[]"
  "()[()]()"
  "()[[]()]"
  "[][[()]]"
  "[([])[]]"
  "[]()[]()"
  "[[()][]]"
  "((())[])"
  "(([]()))"
  "[][]([])"
  "(()[]())"
  "(())()[]"
  "[()]()[]"
  "()()(())"
  "()[][()]"
  "[()][]()"}

Алгоритм, если вдруг не ясно из нескольких строчек кота - все правильные последовательности длины n состоят из:
- всех последовательностей длины n-2, окруженных круглыми скобками
- всех последовательностей длины n-2, окруженных квадратными скобками
- всех последовательностей длины 2 декартово сконкатенированных со всеми последовательностями длины n-2
- .... 4 с n-4
- .....
- n-2 с 2
ну и с удалением дублей на каждой итерации рекурсии, ессно

@igorrr37 · 26.03.2022, 08:05

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
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <ctime>
 
int main()
{
    int const n = 4; // 12 - 2.4c
    std::vector<std::string> vs(1);
    for (int i = 0; i < n / 2; ++i)
    {
        vs[0].append("()");
    }
    
    for (int i = 0; i < n / 2; ++i)
    {
        vs.push_back(vs.back());
        vs.back()[i * 2] = '[';
        vs.back()[i * 2 + 1] = ']';
    }
    std::vector<char> vct;
    vct.reserve(n);
    int cnt{};
    auto t1 = clock();
    for (int j = 0; j < vs.size(); ++j)
    {
        std::sort(vs[j].begin(), vs[j].end());
        do
        {
            int i{};
            for (i = 0; i < n; ++i)
            {
                if (vs[j][i] == '(' || vs[j][i] == '[')
                {
                    vct.push_back(vs[j][i]);
                }
                else if (!vct.empty() && ((vs[j][i] == ')' && vct.back() == '(') || (vs[j][i] == ']' && vct.back() == '[')))
                {
                    vct.pop_back();
                }
                else
                {
                    break;
                }
            }
            if ((i == n) && vct.empty())
            {
                std::cout << vs[j] << " ";
                ++cnt;
            }
            vct.clear();
        } while (std::next_permutation(vs[j].begin(), vs[j].end()));
    }
    std::cout << "\n" << cnt << "\n";
    auto t2 = clock();
    std::cout << (t2 - t1) / 1000. << "\n";
}

Новые блоги и статьи Все статьи Все блоги /
Создание и использование компонентов в Vue 3 Reangularity 14.03.2025 Компонент в Vue - это автономный блок интерфейса, который содержит собственную разметку, логику и стили. Представьте себе кнопку, форму ввода или даже целую панель навигации - всё это можно оформить. . .	Vue 3: Создаем современное веб-приложение с Composition API Reangularity 14.03.2025 В фронтенд-разработке Vue 3 выделяется своим прагматичным подходом. В отличие от React с его минималистичной философией "всё — JavaScript" или Angular с его всеобъемлющим корпоративным подходом, Vue. . .	Разработка контекстных меню в iOS mobDevWorks 14.03.2025 С приходом iOS 13 Apple представила новый API для контекстных меню, который полностью заменил предыдущую технологию 3D Touch peek & pop. Хотя многие разработчики и пользователи испытывают ностальгию. . .	Лучшие практики оптимизации Docker Image Mr. Docker 13.03.2025 Размер Docker-образа влияет на множество аспектов работы с контейнерами. Чем больше образ, тем дольше его загрузка в реестр и выгрузка из него. Для команд разработки, работающих с CI/ CD пайплайнами,. . .	Вопросы на собеседовании по Docker Mr. Docker 13.03.2025 Ты сидишь напротив технического специалиста, и вдруг звучит вопрос про Docker Swarm или многоэтапные сборки. Пот на лбу? Не переживай, после этой статьи ты будешь готов ко всему! Эта статья будет. . .
Поиск текста в сносках : замена дефиса на тире или тире на дефис... РоΜа 13.03.2025 Нужно было найти текст в сносках и заменить. Почему-то метод селекшн не сработал. . . пришлось гуглить. найденный на форумвба код пришлось править. Смысл - заменяет в сносках дефисы и тире на нужные. . . .	Real PATH definitions in bash scripts jigi33 13.03.2025 Как поймать путь и путь к директории относительно запускаемого файла в BASH 1. поймать путь через вывод $(pwd) 2. более правильно - на основе realpath (см. скриншот)	Django или Flask: что выбрать для веб-разработки на Python py-thonny 13.03.2025 Django – это высокоуровневый фреймворк, который придерживается философии "всё включено". Он предоставляет разработчику готовые решения для большинства типичных задач веб-разработки: от аутентификации. . .	Непрерывное развертывание в Java с Kubernetes Javaican 13.03.2025 Чем так привлекателен Kubernetes для развертывания Java-приложений? Этот оркестратор контейнеров позволяет автоматизировать развертывание, масштабирование и управление контейнеризированными. . .	Предотвращение XSS, CSRF и SQL-инъекций в JavaScript run.dev 13.03.2025 JavaScript занимает первые позиции среди языков веб-разработки, но его распространенность делает его привлекательной целью для злоумышленников. Межсайтовый скриптинг (XSS), межсайтовая подделка. . .

@Artem969 0 / 0 / 0 Регистрация: 17.11.2020 Сообщений: 17
		1
	Вывести все правильные скобочные выражения 25.03.2022, 12:14. Показов 1139. Ответов 3 Метки нет (Все метки) Задача 3: Вывести все правильные скобочные выражения длиной N (2 ≤ N ≤ 16, N чётное), состоящие из круглых и квадратных скобок. Пример Исходные данные Результат 4 (()) [[]] [()] ()[] []() ()() ([]) [][] 0

Вывести все правильные скобочные выражения

Решение