192 / 166 / 82
Регистрация: 01.07.2016
Сообщений: 933
1

Вывод всех возможных не повторяющихся вариантов расстановки скобок в выражении

05.06.2019, 23:10. Показов 1147. Ответов 2
Метки нет (Все метки)

Я написал код но такое чувство "а вдруг что то упустил" и я сам не уверен в своей идее.

А алгоритм прост, сначала берём одну пару скобок и пытаемся её расставить всеми возможными вариантами.
HTML5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
1 - пара скобок
(1) 2 3 4 5 6 -- не рассматриваем
(1 2) 3 4 5 6 -- первое выражение со скобками, помечу его так #1, решётка # будет означать глубину рекурсии а число 1 как первый вариант расстановки скобок в выражении.
(1 2 3) 4 5 6 -- #2
(1 2 3 4) 5 6 -- #3
(1 2 3 4 5) 6 -- #4
1 (2 3) 4 5 6 -- #5
1 (2 3 4) 5 6
1 (2 3 4 5) 6
1 (2 3 4 5 6)
1 2 (3 4) 5 6
1 2 (3 4 5) 6
1 2 (3 4 5 6)
1 2 3 (4 5) 6
1 2 3 (4 5 6)
1 2 3 4 (5 6)
1 2 3 4 5 (6) -- не рассматриваем
Для первой пары в каждом из возможных вариантов расстановки скобок вызываем рекурсивно процедуру чтобы увеличить количество пар расставляемых скобок в выражении.
HTML5
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
Здесь рассматриваются варианты расстановок скобок из выражения #1
((1 2) 3) 4 5 6
((1 2) 3 4) 5 6
-------------------------------------
((1 2) 3 4 5) 6
((1 2) 3 4 5 6) -- не рассматриваем
 
(1 2) (3 4) 5 6
(1 2) (3 4 5) 6
(1 2) (3 4 5 6)
 
 
(1 2) 3 (4 5) 6
(1 2) 3 (4 5 6)
 
(1 2) 3 4 (5 6)
 
(1 2) 3 4 5 (6) -- не рассматриваем
 
Здесь рассматриваются варианты расстановок скобок из выражения #2
 
((1 2 3) 4) 5 6
((1 2 3) 4 5) 6
((1 2 3) 4 5 6) -- не рассматриваем
(1 2 3) (4 5) 6 -- А вот здесь стоит объяснить как произошел переход, когда я вызываю выражение (1 2 3) 4 5 6 рекурсивно, в процедуре я сначал
а нахожу место для левой скобки, места для левой скобки где она могла бы расположиться это все места СНАРУЖИ ВСЕХ РАССТАВЛЕННЫХ СКОБОК 
в предыдущих вызовах процедур. То есть конкретно в этом примере я могу поставить открывающую скобку перед 1, 4, 5, 6. Когда постав
ил открывающую то начинаю искать место для закрывающей в местах от самого правого края и до первой скобки где она может б
ыть встречена. Конкретно в этом при
мере я могу поставить закрывающую скобку после 3, 4, 5, 6.
 
В общем виде это будет выглядеть так:
Неважно уже какую по счёту пару скобок я пытаюсь расставить в выражении, расставляем текущую скобочную последовательность СНАРУЖИ всех остальных уже расставленных в предыдущих вызовах скобочных последовательностей.
 
Например хотим расставить 4ую по счёту пару скобок в выражении с уже расставленными скобками.
1 2 3 {4 5 6} 7 7 {8 8 9 {8 7 6 5 5 4 3 2 1 2 6} 7 3 4} 5 6 7
 
Получаем:
(1 2 3 {4 5 6} 7 7 {8 8 9 {8 7 6 5 5 4 3 2 1 2 6} 7 3 4} 5) 6 7
(1 2 3 {4 5 6} 7 7 {8 8 9 {8 7 6 5 5 4 3 2 1 2 6} 7 3 4} 5 6) 7
(1 2 3 {4 5 6} 7 7 {8 8 9 {8 7 6 5 5 4 3 2 1 2 6} 7 3 4} 5 6 7) - не рассматриваем
1 (2 3 {4 5 6} 7 7 {8 8 9 {8 7 6 5 5 4 3 2 1 2 6} 7 3 4} 5) 6 7
1 (2 3 {4 5 6} 7 7 {8 8 9 {8 7 6 5 5 4 3 2 1 2 6} 7 3 4} 5 6) 7
1 (2 3 {4 5 6} 7 7 {8 8 9 {8 7 6 5 5 4 3 2 1 2 6} 7 3 4} 5 6 7)
1 2 (3 {4 5 6} 7 7 {8 8 9 {8 7 6 5 5 4 3 2 1 2 6} 7 3 4} 5) 6 7
1 2 (3 {4 5 6} 7 7 {8 8 9 {8 7 6 5 5 4 3 2 1 2 6} 7 3 4} 5 6) 7
1 2 (3 {4 5 6} 7 7 {8 8 9 {8 7 6 5 5 4 3 2 1 2 6} 7 3 4} 5 6 7)
 
=========================================================================================
 
И продолжим наш предыдущий пример
 
(1 2 3) (4 5 6)
 
(1 2 3) 4 (5 6)
 
(1 2 3) 4 5 (6) -- не рассматриваем
 
 
----
 
Для выражения #3
(1 2 3 4) 5 6
((1 2 3 4) 5) 6
(1 2 3 4) (5 6)
 
---
 
Для выражения #4
(1 2 3 4 5) 6 - так и остаётся
 
--
 
Для выражения #5
1 (2 3) 4 5 6
(1 (2 3)) 4 5 6
(1 (2 3) 4) 5 6
(1 (2 3) 4 5) 6
1 ((2 3) 4) 5 6
1 ((2 3) 4 5) 6
1 ((2 3) 4 5 6)
1 (2 3) (4 5) 6
1 (2 3) (4 5 6)
1 (2 3) 4 (5 6)
1 (2 3) 4 5 (6) -- не рассматриваем
Вот код генерирующий эти скобки
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
#include <iostream>
#include <fstream>
#include <vector>
 
typedef unsigned char uchar;
 
std::ofstream outFile("c:\\out.txt", std::ios::out);
 
class Brackets {
 
public:
 
    int left;
 
    int right;
 
    Brackets() {}
 
};
 
void show_exression(std::vector<int> &numbers, std::vector<Brackets> &bracket) {
    for(int i = 0; i < (int)numbers.size(); ++i) {
        for(int j = 0; j < (int)bracket[i].left; ++j) {
            outFile << '(';
        }
        outFile << numbers[i];
        for(int j = 0; j < (int)bracket[i].right; ++j) {
            outFile << ')';
        }
        outFile << std::ends;
    }
    outFile << std::endl;
}
 
void set_brackets(
    std::vector<Brackets> bracket,
    std::vector<int> &numbers
) {
    const int size = (int)numbers.size();
    uchar c = 0, indl, indr, k;
    for (uchar i = 0; i < size - 1; ++i) {
        if (!c) {
            indl = i;
            indr = size - 1;
            while (!bracket[indr].right && indr > indl) {
                --indr;
            }
            if (
                indr == indl
                                                            ||
                bracket[indr].right && bracket[indl].left
                                                            ||
                !bracket[indr].right && !bracket[indl].left
            ) {
                ++indr;
            }
            (i) ? k = 0 : k = 1;
            while (indr < size - k) {
                ++bracket[indl].left;
                ++bracket[indr].right;
                show_exression(numbers, bracket);
                set_brackets(bracket, numbers);
                --bracket[indl].left;
                --bracket[indr].right;
                ++indr;
            }
        }
        c += bracket[i].left;
        c -= bracket[i].right;
    }
}
 
int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};
    std::vector<Brackets> bracket(numbers.size());
    for(int i = 0; i < (int)bracket.size(); ++i) {
        bracket[i].left = bracket[i].right = 0;
    }
    set_brackets(bracket, numbers);
    outFile.close();
    return 0;
}
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
05.06.2019, 23:10
Ответы с готовыми решениями:

Вывод всех возможных вариантов перестановки элементов массива (рекурсия)
Никак не могу создать алгоритм для вывода всех возможных вариантов перестановки элементов массива...

Проверить правильность расстановки круглых скобок в выражении
Дана последовательность символов длины n (n&gt;=1) Написать метод, который проверяет круглых скобок в...

Проверить правильность расстановки скобок вида (), {}, [] в выражении.
Скобки считаются сбалансированными, если: а) при подсчете скобок слева направо количество...

Файл: Проверить корректность расстановки скобок в арифметическом выражении
Помогите написать задачу!!! Проверить корректность расстановки скобок в арифметическом выражении....

2
192 / 166 / 82
Регистрация: 01.07.2016
Сообщений: 933
06.06.2019, 10:39  [ТС] 2
Я искал в интернете что то подобное но не смог найти или плохо искал. Может существуют готовые алгоритмы?
0
192 / 166 / 82
Регистрация: 01.07.2016
Сообщений: 933
15.06.2019, 10:41  [ТС] 3
Всё ещё актуально
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
15.06.2019, 10:41
Помогаю со студенческими работами здесь

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

Файлы: проверить корректность расстановки скобок в арифметическом выражении
Проверить корректность расстановки скобок в арифметическом выражении. Выражение задается из файла...

Напишите программу, которая проверяет правильность расстановки скобок в выражении.
Напишите пожалуйста программу, которая проверяет правильность расстановки скобок в выражении....

Сколько есть возможных вариантов расстановки книг, в которых ни одна из них не стоит на своем месте?
Есть 12 различных книг, каждая из которых имеет свое определённое (помеченное) место на полке....


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

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

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