Как расставить скобки в выражении всеми возможными способами?

@no swear · Регистрация: 01.07.2016

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

В общем решаю одну непростую задачку, а условие такое:

Кликните здесь для просмотра всего текста

Дана строка чисел (например 123456=5) и сразу за ней знак равно и ещё одно число. Нужно скомбинировать такие варианты чисел, скобок и знаков операций (+, -, *, div, ^ - это степень) так чтобы получить заданно число.
Под комбинацией чисел понимается что если нам дана строка из цифр 123456 то нужно получить следующие комбинации:
1 2 3 4 5 6 - 6 чисел
12 3 4 5 6 - 5 чисел
12 3 45 6 - 4 числа
12 456 - 3 числа
... и так далее, смысл в том что к конкретной цифре могут присоединится
только 2 соседние с ней цифры (1 2 3 => 12 3 => 1 23).

Под комбинацией скобок понимается что из каждого полученного числа (которые сверху) нужно получить числа со всеми возможными комбинациями скобок '(' - открывающей и ')' - закрывающей:
(1 2) 3 (4 5 6), (1 2) (3 4) 5 6, (1 2 3 4 5) 6
((12 3 4) 5) 6, (12 3 4 5) 6
(12 456) - ну из двух чисел получать скобки бессмысленно

Под комбинацией знаков операций (+, -, *, div, ^) понимается что из каждого полученного числа со скобками(которые сверху) нужно получить следующие выражения:
(1 + 2) - 3 * (4 * 5 + 6)
(1 - 2 ^ 3 + 4 * 5) / 6

А потом посчитать это и проверить что оно равно нашему заданному числу или нет(в нашем случае это число 5), если равно то вывести выражение при котором выполняется заданное уравнение

Не обязательно выполнять всё так как я тут описал, главное получить результат.

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

Буду рад любой помощи!

@no swear · 11.05.2018, 19:41 **[ТС]**

Что то получилось написать, кому интересно посмотрите если заметите ошибки скажите мне буду очень благодарен

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
#include "stdafx.h"
#include <fstream>
#include <vector>
#include <string>
using namespace std;
typedef unsigned char u_char;
typedef short int s_int;
struct brackets;
ifstream fin;
ofstream fout;
vector<int> array_of_numbers;
s_int size;
 
struct brackets
{
    s_int left;
    s_int right;
};
 
void set_brackets(vector<brackets> br)
{
    u_char c = 0, indl, indr, k;
    for (u_char i = 0; i < size - 1; ++i) {
        if (!c) {
            indl = i;
            //(!i) ? indr = size - 2 : indr = size - 1;
            //indr = size - 1;
            indr = size - 1;
            while (!br[indr].right && indr > indl) {
                --indr;
            }
            //++indr;
            if (indr == indl || br[indr].right && br[indl].left ||
                                !br[indr].right && !br[indl].left)
            {
                ++indr;
            }
            (i) ? k = 0 : k = 1;
            while (indr < size - k) {
            //while (!br[indr].right && indr > indl) {
                ++br[indl].left;
                ++br[indr].right;
                for (u_char p = 0; p < size; ++p) {
                    for (u_char l = 1; l <= br[p].left; ++l) {
                        fout << '(';
                    }
                    fout << ends << array_of_numbers[p] << ends;
                    for (u_char l = 1; l <= br[p].right; ++l) {
                        fout << ')';
                    }
                }
                fout << endl;
                set_brackets(br);
                --br[indl].left;
                --br[indr].right;
                ++indr;
            }
        }
        c += br[i].left;
        c -= br[i].right;
    }
}
 
void concatenate_numbers(string &numbers)
{
    int i, j;
    int s, r;
    string tmp;
    vector<brackets> br(numbers.size());
    for (r = 0; r <= numbers.size(); ++r) {
        size = 0;
        for (i = 0; i < r; ++i) {
            array_of_numbers[i] = +numbers[i] - 48;
            ++size;
        }
        if (r == numbers.size()) {
            for (j = 0; j < size; ++j) {
                fout << array_of_numbers[j] << ends;
            }
            fout << endl;
            for (j = 0; j < br.size(); ++j) {
                br[j].left = 0;
                br[j].right = 0;
            }
            set_brackets(br);
        }
        s = size;
        for (i = 2; i < numbers.size() && r + i <= numbers.size(); ++i) {
            tmp = numbers.substr(r, i);
            array_of_numbers[size++] = atoi(tmp.c_str());
            for (j = r + i; j < numbers.size(); ++j) {
                array_of_numbers[size++] = +numbers[j] - 48;
            }
            for (j = 0; j < size; ++j) {
                fout << array_of_numbers[j] << ends;
            }
            fout << endl;
            for (j = 0; j < br.size(); ++j) {
                br[j].left = 0;
                br[j].right = 0;
            }
            set_brackets(br);
            size = s;
        }
    }
}
 
int main()
{
    const char *in = "c:\\input.txt";
    const char *out = "c:\\output.txt";
    fin.open(in, ios::in);
    fout.open(out, ios::out | ios::trunc);
    string numbers;
    fin >> numbers;
    array_of_numbers.resize(numbers.size());
    concatenate_numbers(numbers);
    fin.close();
    fout.close();
}

Пока что создаёт только комбинации из чисел и скобок. Сейчас пишу перебор арифметических знаков операций

@no swear · 12.05.2018, 20:10 **[ТС]**

В input.txt задавайте последовательность чисел без знака равно, например так: 12345
В output.txt будет выводится выражение и то чему это выражение равно
Правда ещё есть то над чем надо поработать

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
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
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
#include "stdafx.h"
#include <fstream>
#include <vector>
#include <stack>
#include <string>
#include <iomanip>
using namespace std;
typedef unsigned char u_char;
typedef short int s_int;
struct brackets;
class Tree;
ifstream fin;
ofstream fout;
vector<int> num;
string value;
s_int size;
 
struct brackets
{
    s_int left;
    s_int right;
};
 
class Tree
{
    struct Node
    {
        string data;
        Node *Left;
        Node *Right;
    };
 
private:
    string str_OPZ;
    vector<string> mas_of_symbol;
    stack<double> stack_of_number;
    Node *Start;
 
    void DetourLRK(Node *N)
    {
        if (N == NULL) return;
        DetourLRK(N->Left);
        DetourLRK(N->Right);
        if (!Isdigit(N->data[0])) {
            Calc(N->data[0]);
        }
        else {
            stack_of_number.push(atof(N->data.c_str()));
        }
    }
 
    void DetourLRK(Node *N, string &s)
    {
        if (N == NULL) return;
        DetourLRK(N->Left, s);
        DetourLRK(N->Right, s);
        s += N->data + " | ";
    }
 
    void AddNode(Node *&N, int n)
    {
        N = new Node;
        N->Left = NULL;
        N->Right = NULL;
        N->data = mas_of_symbol[n];
    }
 
    int Priority(char s)
    {
        if (s == '+' || s == '-') 
            return 1;
        return 2;
    }
 
    bool Isdigit(char s)
    {
        if (s >= '0' && s <= '9') 
            return true;
        return false;
    }
 
    void Calc(char s)
    {
        double a, b;
        a = stack_of_number.top();
        stack_of_number.pop();
        b = stack_of_number.top();
        stack_of_number.pop();
        switch (s)
        {
            case '+':
                stack_of_number.push(a + b);
                return;
 
            case '-':
                stack_of_number.push(b - a);
                return;
 
            case '*':
                stack_of_number.push(a * b);
                return;
 
            case '/':
                stack_of_number.push(b / a);
                return;
        }
    }
 
    void ConstructTree(Node *&N, int l, int r)
    {
        int nest = 0, k = 3, ind;
        int i = l;
        if (l == r) {
            AddNode(N, l);
            return;
        }
        while (i <= r) {
            if (mas_of_symbol[i] == "(") {
                nest++;
                i++;
                continue;
            }
            if (mas_of_symbol[i] == ")") {
                nest--;
                i++;
                continue;
            }
            if (nest == 0 && !Isdigit(mas_of_symbol[i][0])) {
                if (k >= Priority(mas_of_symbol[i][0])) {
                    k = Priority(mas_of_symbol[i][0]);
                    ind = i;
                }
            }
            i++;
        }
        if (k == 3) {
            return ConstructTree(N, l + 1, r - 1);
        }
        AddNode(N, ind);
        ConstructTree(N->Left, l, ind - 1);
        ConstructTree(N->Right, ind + 1, r);
    }
 
    void DeleteNode(Node *&N)
    {
        if (N == NULL) return;
        DeleteNode(N->Left);
        DeleteNode(N->Right);
        delete N;
    }
 
public:
    Tree()
    {
        Start = NULL;
    }
 
    string OPZ();
    double Answer();
    void GetDataFrom(const string&);
    void DeleteTree();
};
 
void Tree::DeleteTree()
{
    mas_of_symbol.clear();
    DeleteNode(Start);
}
 
void Tree::GetDataFrom(const string &s)
{
    string sn = "";
    bool f = false;
    mas_of_symbol.clear();
    str_OPZ = "";
    for (int i = 0; i < s.length(); ++i) {
        if (Isdigit(s[i]) || s[i] == ',') {
            sn += s[i];
            f = true;
        }
        else {
            if (f) {
                mas_of_symbol.push_back(sn);
                f = false;
            }
            sn = s[i];
            mas_of_symbol.push_back(sn);
            sn = "";
        }
    }
    if (sn.length() > 0) 
        mas_of_symbol.push_back(sn);
    ConstructTree(Start, 0, mas_of_symbol.size() - 1);
}
 
double Tree::Answer()
{
    DetourLRK(Start);
    double tmp = stack_of_number.top();
    stack_of_number.pop();
    return tmp;
}
 
string Tree::OPZ()
{
    DetourLRK(Start, str_OPZ);
    string Astr = str_OPZ;
    str_OPZ = "";
    return Astr;
}
 
string inttostr(int n)
{
    string s;
    while (n) {
        s = char((n % 10) + '0') + s;
        n /= 10;
    }
    return s;
}
 
void set_op(vector<u_char> op, vector<brackets> br, s_int r)
{
    if (r >= size) {
        /*for (u_char p = 0; p < size; ++p) {
            for (u_char l = 1; l <= br[p].left; ++l) {
                fout << '(';
            }
            fout << num[p];
            for (u_char l = 1; l <= br[p].right; ++l) {
                fout << ')';
            }
            if (p < size - 1)
                fout << op[p + 1];
        }*/
        /*for (u_char i = 1; i < op.size(); ++i) {
            fout << op[i] << ends;
        }*/
 
        Tree tr;
        value = "";
        for (u_char p = 0; p < size; ++p) {
            for (u_char l = 1; l <= br[p].left; ++l) {
                value += '(';
            }
            value += inttostr(num[p]);
            for (u_char l = 1; l <= br[p].right; ++l) {
                value += ')';
            }
            if (p < size - 1)
                value += op[p + 1];
        }
        tr.GetDataFrom(value);
        fout << value << " = " << setprecision(6) << tr.Answer() << endl;
        tr.DeleteTree();
        //fout << value << endl;
        return;
        //exit(1);
    }
    op[r] = '+';
    set_op(op, br, r + 1);
    op[r] = '-';
    set_op(op, br, r + 1);
    op[r] = '*';
    set_op(op, br, r + 1);
    op[r] = '/';
    set_op(op, br, r + 1);
}
 
void set_brackets(vector<brackets> br)
{
    u_char c = 0, indl, indr, k;
    vector<u_char> op(br.size());
    for (u_char i = 0; i < size - 1; ++i) {
        if (!c) {
            indl = i;
            indr = size - 1;
            while (!br[indr].right && indr > indl) {
                --indr;
            }
            if (indr == indl || br[indr].right && br[indl].left ||
                                !br[indr].right && !br[indl].left)
            {
                ++indr;
            }
            (i) ? k = 0 : k = 1;
            while (indr < size - k) {
                ++br[indl].left;
                ++br[indr].right;
                /*for (u_char p = 0; p < size; ++p) {
                    for (u_char l = 1; l <= br[p].left; ++l) {
                        fout << '(';
                    }
                    fout << ends << num[p] << ends;
                    for (u_char l = 1; l <= br[p].right; ++l) {
                        fout << ')';
                    }
                }*/
                fout << endl;
                set_op(op, br, 1);
                set_brackets(br);
                --br[indl].left;
                --br[indr].right;
                ++indr;
            }
        }
        c += br[i].left;
        c -= br[i].right;
    }
}
 
void concatenate_numbers(string &numbers)
{
    int i, j;
    int s, r;
    string tmp;
    vector<brackets> br(numbers.size());
    for (r = 0; r <= numbers.size(); ++r) {
        size = 0;
        for (i = 0; i < r; ++i) {
            num[i] = +numbers[i] - 48;
            ++size;
        }
        if (r == numbers.size()) {
            /*for (j = 0; j < size; ++j) {
                fout << num[j] << ends;
            }
            fout << endl;*/
            for (j = 0; j < br.size(); ++j) {
                br[j].left = 0;
                br[j].right = 0;
            }
            set_brackets(br);
        }
        s = size;
        for (i = 2; i < numbers.size() && r + i <= numbers.size(); ++i) {
            tmp = numbers.substr(r, i);
            num[size++] = atoi(tmp.c_str());
            for (j = r + i; j < numbers.size(); ++j) {
                num[size++] = +numbers[j] - 48;
            }
            /*for (j = 0; j < size; ++j) {
                fout << num[j] << ends;
            }
            fout << endl;*/
            for (j = 0; j < br.size(); ++j) {
                br[j].left = 0;
                br[j].right = 0;
            }
            set_brackets(br);
            size = s;
        }
    }
}
 
int main()
{
    const char *in = "c:\\input.txt";
    const char *out = "c:\\output.txt";
    fin.open(in, ios::in);
    fout.open(out, ios::out | ios::trunc);
    string numbers;
    fin >> numbers;
    num.resize(numbers.size());
    concatenate_numbers(numbers);
    fin.close();
    fout.close();
}

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@no swear 192 / 166 / 82 Регистрация: 01.07.2016 Сообщений: 943

	Как расставить скобки в выражении всеми возможными способами? 07.05.2018, 20:25. Показов 4080. Ответов 2 Метки нет (Все метки) В общем решаю одну непростую задачку, а условие такое: Кликните здесь для просмотра всего текста Дана строка чисел (например 123456=5) и сразу за ней знак равно и ещё одно число. Нужно скомбинировать такие варианты чисел, скобок и знаков операций (+, -, , div, ^ - это степень) так чтобы получить заданно число. Под комбинацией чисел понимается что если нам дана строка из цифр 123456 то нужно получить следующие комбинации: 1 2 3 4 5 6 - 6 чисел 12 3 4 5 6 - 5 чисел 12 3 45 6 - 4 числа 12 456 - 3 числа ... и так далее, смысл в том что к конкретной цифре могут присоединится только 2 соседние с ней цифры (1 2 3 => 12 3 => 1 23). Под комбинацией скобок понимается что из каждого полученного числа (которые сверху) нужно получить числа со всеми возможными комбинациями скобок '(' - открывающей и ')' - закрывающей: (1 2) 3 (4 5 6), (1 2) (3 4) 5 6, (1 2 3 4 5) 6 ((12 3 4) 5) 6, (12 3 4 5) 6 (12 456) - ну из двух чисел получать скобки бессмысленно Под комбинацией знаков операций (+, -, , div, ^) понимается что из каждого полученного числа со скобками(которые сверху) нужно получить следующие выражения: (1 + 2) - 3 * (4 * 5 + 6) (1 - 2 ^ 3 + 4 * 5) / 6 А потом посчитать это и проверить что оно равно нашему заданному числу или нет(в нашем случае это число 5), если равно то вывести выражение при котором выполняется заданное уравнение Не обязательно выполнять всё так как я тут описал, главное получить результат. Из всего этого я сделал только комбинацию чисел и продумал как сделать перебор арифметических операций а также решил что буду считать полученное выражение с помощью Обратной польской записи. А вот скобки меня в тупик загнали, несколько дней думаю как правильно и оптимально перебрать все скобки. Пришел к некоторому рекурсивному алгоритму но очень сомневаюсь на счёт его правильности. Буду рад любой помощи! 0

Как расставить скобки в выражении всеми возможными способами?

Решение