Расстановка скобочек в выражении (все комбинации)

@lifestyle · Регистрация: 10.05.2009

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

собственно сабж: расстановка всех комибинаций скобочек в мат. выражении от 4 до 8 цифр в выражении.
пример:
есть выражение 1+2+3+4
все комб.:
(1+2)+(3+4)
(1+2)+3+4
1+(2+3)+4
1+2+(3+4)
(1+2+3)+4
1+(2+3+4)
(1+2+3+4)
П.С.
+ любой оператор может быть (+,-,*,/)

Что можете посоветовать. ума не приложу как сие проделать можно еще и в обобщеном варианте до 8 цифр.

@Mr.X · 31.10.2010, 08:01

В вашем примере противоречие. Вообще-то допустимых расстановок скобок вот столько:

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
#1:     ((((1)+(2))+(3))+(4))         #2:       ((((1)+(2))+(3))+4)
#3:     ((((1)+(2))+3)+(4))           #4:       ((((1)+(2))+3)+4)
#5:     ((((1)+2)+(3))+(4))           #6:       ((((1)+2)+(3))+4)
#7:     ((((1)+2)+3)+(4))             #8:       ((((1)+2)+3)+4)
#9:     (((1)+((2)+(3)))+(4))         #10:      (((1)+((2)+(3)))+4)
#11:    (((1)+((2)+3))+(4))           #12:      (((1)+((2)+3))+4)
#13:    (((1)+(2))+((3)+(4)))         #14:      (((1)+(2))+((3)+4))
#15:    (((1)+(2))+(3))+(4)           #16:      (((1)+(2))+(3))+4
#17:    (((1)+(2))+(3)+(4))           #18:      (((1)+(2))+(3)+4)
#19:    (((1)+(2))+(3+(4)))           #20:      (((1)+(2))+(3+4))
#21:    (((1)+(2))+3)+(4)             #22:      (((1)+(2))+3)+4
#23:    (((1)+(2))+3+(4))             #24:      (((1)+(2))+3+4)
#25:    (((1)+(2)+(3))+(4))           #26:      (((1)+(2)+(3))+4)
#27:    (((1)+(2)+3)+(4))             #28:      (((1)+(2)+3)+4)
#29:    (((1)+(2+(3)))+(4))           #30:      (((1)+(2+(3)))+4)
#31:    (((1)+(2+3))+(4))             #32:      (((1)+(2+3))+4)
#33:    (((1)+2)+((3)+(4)))           #34:      (((1)+2)+((3)+4))
#35:    (((1)+2)+(3))+(4)             #36:      (((1)+2)+(3))+4
#37:    (((1)+2)+(3)+(4))             #38:      (((1)+2)+(3)+4)
#39:    (((1)+2)+(3+(4)))             #40:      (((1)+2)+(3+4))
#41:    (((1)+2)+3)+(4)               #42:      (((1)+2)+3)+4
#43:    (((1)+2)+3+(4))               #44:      (((1)+2)+3+4)
#45:    (((1)+2+(3))+(4))             #46:      (((1)+2+(3))+4)
#47:    (((1)+2+3)+(4))               #48:      (((1)+2+3)+4)
#49:    (((1+(2))+(3))+(4))           #50:      (((1+(2))+(3))+4)
#51:    (((1+(2))+3)+(4))             #52:      (((1+(2))+3)+4)
#53:    (((1+2)+(3))+(4))             #54:      (((1+2)+(3))+4)
#55:    (((1+2)+3)+(4))               #56:      (((1+2)+3)+4)
#57:    ((1)+(((2)+(3))+(4)))         #58:      ((1)+(((2)+(3))+4))
#59:    ((1)+(((2)+3)+(4)))           #60:      ((1)+(((2)+3)+4))
#61:    ((1)+((2)+((3)+(4))))         #62:      ((1)+((2)+((3)+4)))
#63:    ((1)+((2)+(3)))+(4)           #64:      ((1)+((2)+(3)))+4
#65:    ((1)+((2)+(3))+(4))           #66:      ((1)+((2)+(3))+4)
#67:    ((1)+((2)+(3)+(4)))           #68:      ((1)+((2)+(3)+4))
#69:    ((1)+((2)+(3+(4))))           #70:      ((1)+((2)+(3+4)))
#71:    ((1)+((2)+3))+(4)             #72:      ((1)+((2)+3))+4
#73:    ((1)+((2)+3)+(4))             #74:      ((1)+((2)+3)+4)
#75:    ((1)+((2)+3+(4)))             #76:      ((1)+((2)+3+4))
#77:    ((1)+((2+(3))+(4)))           #78:      ((1)+((2+(3))+4))
#79:    ((1)+((2+3)+(4)))             #80:      ((1)+((2+3)+4))
#81:    ((1)+(2))+((3)+(4))           #82:      ((1)+(2))+((3)+4)
#83:    ((1)+(2))+(3)+(4)             #84:      ((1)+(2))+(3)+4
#85:    ((1)+(2))+(3+(4))             #86:      ((1)+(2))+(3+4)
#87:    ((1)+(2))+3+(4)               #88:      ((1)+(2))+3+4
#89:    ((1)+(2)+((3)+(4)))           #90:      ((1)+(2)+((3)+4))
#91:    ((1)+(2)+(3))+(4)             #92:      ((1)+(2)+(3))+4
#93:    ((1)+(2)+(3)+(4))             #94:      ((1)+(2)+(3)+4)
#95:    ((1)+(2)+(3+(4)))             #96:      ((1)+(2)+(3+4))
#97:    ((1)+(2)+3)+(4)               #98:      ((1)+(2)+3)+4
#99:    ((1)+(2)+3+(4))               #100:     ((1)+(2)+3+4)
#101:   ((1)+(2+((3)+(4))))           #102:     ((1)+(2+((3)+4)))
#103:   ((1)+(2+(3)))+(4)             #104:     ((1)+(2+(3)))+4
#105:   ((1)+(2+(3))+(4))             #106:     ((1)+(2+(3))+4)
#107:   ((1)+(2+(3)+(4)))             #108:     ((1)+(2+(3)+4))
#109:   ((1)+(2+(3+(4))))             #110:     ((1)+(2+(3+4)))
#111:   ((1)+(2+3))+(4)               #112:     ((1)+(2+3))+4
#113:   ((1)+(2+3)+(4))               #114:     ((1)+(2+3)+4)
#115:   ((1)+(2+3+(4)))               #116:     ((1)+(2+3+4))
#117:   ((1)+2)+((3)+(4))             #118:     ((1)+2)+((3)+4)
#119:   ((1)+2)+(3)+(4)               #120:     ((1)+2)+(3)+4
#121:   ((1)+2)+(3+(4))               #122:     ((1)+2)+(3+4)
#123:   ((1)+2)+3+(4)                 #124:     ((1)+2)+3+4
#125:   ((1)+2+((3)+(4)))             #126:     ((1)+2+((3)+4))
#127:   ((1)+2+(3))+(4)               #128:     ((1)+2+(3))+4
#129:   ((1)+2+(3)+(4))               #130:     ((1)+2+(3)+4)
#131:   ((1)+2+(3+(4)))               #132:     ((1)+2+(3+4))
#133:   ((1)+2+3)+(4)                 #134:     ((1)+2+3)+4
#135:   ((1)+2+3+(4))                 #136:     ((1)+2+3+4)
#137:   ((1+((2)+(3)))+(4))           #138:     ((1+((2)+(3)))+4)
#139:   ((1+((2)+3))+(4))             #140:     ((1+((2)+3))+4)
#141:   ((1+(2))+((3)+(4)))           #142:     ((1+(2))+((3)+4))
#143:   ((1+(2))+(3))+(4)             #144:     ((1+(2))+(3))+4
#145:   ((1+(2))+(3)+(4))             #146:     ((1+(2))+(3)+4)
#147:   ((1+(2))+(3+(4)))             #148:     ((1+(2))+(3+4))
#149:   ((1+(2))+3)+(4)               #150:     ((1+(2))+3)+4
#151:   ((1+(2))+3+(4))               #152:     ((1+(2))+3+4)
#153:   ((1+(2)+(3))+(4))             #154:     ((1+(2)+(3))+4)
#155:   ((1+(2)+3)+(4))               #156:     ((1+(2)+3)+4)
#157:   ((1+(2+(3)))+(4))             #158:     ((1+(2+(3)))+4)
#159:   ((1+(2+3))+(4))               #160:     ((1+(2+3))+4)
#161:   ((1+2)+((3)+(4)))             #162:     ((1+2)+((3)+4))
#163:   ((1+2)+(3))+(4)               #164:     ((1+2)+(3))+4
#165:   ((1+2)+(3)+(4))               #166:     ((1+2)+(3)+4)
#167:   ((1+2)+(3+(4)))               #168:     ((1+2)+(3+4))
#169:   ((1+2)+3)+(4)                 #170:     ((1+2)+3)+4
#171:   ((1+2)+3+(4))                 #172:     ((1+2)+3+4)
#173:   ((1+2+(3))+(4))               #174:     ((1+2+(3))+4)
#175:   ((1+2+3)+(4))                 #176:     ((1+2+3)+4)
#177:   (1)+(((2)+(3))+(4))           #178:     (1)+(((2)+(3))+4)
#179:   (1)+(((2)+3)+(4))             #180:     (1)+(((2)+3)+4)
#181:   (1)+((2)+((3)+(4)))           #182:     (1)+((2)+((3)+4))
#183:   (1)+((2)+(3))+(4)             #184:     (1)+((2)+(3))+4
#185:   (1)+((2)+(3)+(4))             #186:     (1)+((2)+(3)+4)
#187:   (1)+((2)+(3+(4)))             #188:     (1)+((2)+(3+4))
#189:   (1)+((2)+3)+(4)               #190:     (1)+((2)+3)+4
#191:   (1)+((2)+3+(4))               #192:     (1)+((2)+3+4)
#193:   (1)+((2+(3))+(4))             #194:     (1)+((2+(3))+4)
#195:   (1)+((2+3)+(4))               #196:     (1)+((2+3)+4)
#197:   (1)+(2)+((3)+(4))             #198:     (1)+(2)+((3)+4)
#199:   (1)+(2)+(3)+(4)               #200:     (1)+(2)+(3)+4
#201:   (1)+(2)+(3+(4))               #202:     (1)+(2)+(3+4)
#203:   (1)+(2)+3+(4)                 #204:     (1)+(2)+3+4
#205:   (1)+(2+((3)+(4)))             #206:     (1)+(2+((3)+4))
#207:   (1)+(2+(3))+(4)               #208:     (1)+(2+(3))+4
#209:   (1)+(2+(3)+(4))               #210:     (1)+(2+(3)+4)
#211:   (1)+(2+(3+(4)))               #212:     (1)+(2+(3+4))
#213:   (1)+(2+3)+(4)                 #214:     (1)+(2+3)+4
#215:   (1)+(2+3+(4))                 #216:     (1)+(2+3+4)
#217:   (1)+2+((3)+(4))               #218:     (1)+2+((3)+4)
#219:   (1)+2+(3)+(4)                 #220:     (1)+2+(3)+4
#221:   (1)+2+(3+(4))                 #222:     (1)+2+(3+4)
#223:   (1)+2+3+(4)                   #224:     (1)+2+3+4
#225:   (1+(((2)+(3))+(4)))           #226:     (1+(((2)+(3))+4))
#227:   (1+(((2)+3)+(4)))             #228:     (1+(((2)+3)+4))
#229:   (1+((2)+((3)+(4))))           #230:     (1+((2)+((3)+4)))
#231:   (1+((2)+(3)))+(4)             #232:     (1+((2)+(3)))+4
#233:   (1+((2)+(3))+(4))             #234:     (1+((2)+(3))+4)
#235:   (1+((2)+(3)+(4)))             #236:     (1+((2)+(3)+4))
#237:   (1+((2)+(3+(4))))             #238:     (1+((2)+(3+4)))
#239:   (1+((2)+3))+(4)               #240:     (1+((2)+3))+4
#241:   (1+((2)+3)+(4))               #242:     (1+((2)+3)+4)
#243:   (1+((2)+3+(4)))               #244:     (1+((2)+3+4))
#245:   (1+((2+(3))+(4)))             #246:     (1+((2+(3))+4))
#247:   (1+((2+3)+(4)))               #248:     (1+((2+3)+4))
#249:   (1+(2))+((3)+(4))             #250:     (1+(2))+((3)+4)
#251:   (1+(2))+(3)+(4)               #252:     (1+(2))+(3)+4
#253:   (1+(2))+(3+(4))               #254:     (1+(2))+(3+4)
#255:   (1+(2))+3+(4)                 #256:     (1+(2))+3+4
#257:   (1+(2)+((3)+(4)))             #258:     (1+(2)+((3)+4))
#259:   (1+(2)+(3))+(4)               #260:     (1+(2)+(3))+4
#261:   (1+(2)+(3)+(4))               #262:     (1+(2)+(3)+4)
#263:   (1+(2)+(3+(4)))               #264:     (1+(2)+(3+4))
#265:   (1+(2)+3)+(4)                 #266:     (1+(2)+3)+4
#267:   (1+(2)+3+(4))                 #268:     (1+(2)+3+4)
#269:   (1+(2+((3)+(4))))             #270:     (1+(2+((3)+4)))
#271:   (1+(2+(3)))+(4)               #272:     (1+(2+(3)))+4
#273:   (1+(2+(3))+(4))               #274:     (1+(2+(3))+4)
#275:   (1+(2+(3)+(4)))               #276:     (1+(2+(3)+4))
#277:   (1+(2+(3+(4))))               #278:     (1+(2+(3+4)))
#279:   (1+(2+3))+(4)                 #280:     (1+(2+3))+4
#281:   (1+(2+3)+(4))                 #282:     (1+(2+3)+4)
#283:   (1+(2+3+(4)))                 #284:     (1+(2+3+4))
#285:   (1+2)+((3)+(4))               #286:     (1+2)+((3)+4)
#287:   (1+2)+(3)+(4)                 #288:     (1+2)+(3)+4
#289:   (1+2)+(3+(4))                 #290:     (1+2)+(3+4)
#291:   (1+2)+3+(4)                   #292:     (1+2)+3+4
#293:   (1+2+((3)+(4)))               #294:     (1+2+((3)+4))
#295:   (1+2+(3))+(4)                 #296:     (1+2+(3))+4
#297:   (1+2+(3)+(4))                 #298:     (1+2+(3)+4)
#299:   (1+2+(3+(4)))                 #300:     (1+2+(3+4))
#301:   (1+2+3)+(4)                   #302:     (1+2+3)+4
#303:   (1+2+3+(4))                   #304:     (1+2+3+4)
#305:   1+(((2)+(3))+(4))             #306:     1+(((2)+(3))+4)
#307:   1+(((2)+3)+(4))               #308:     1+(((2)+3)+4)
#309:   1+((2)+((3)+(4)))             #310:     1+((2)+((3)+4))
#311:   1+((2)+(3))+(4)               #312:     1+((2)+(3))+4
#313:   1+((2)+(3)+(4))               #314:     1+((2)+(3)+4)
#315:   1+((2)+(3+(4)))               #316:     1+((2)+(3+4))
#317:   1+((2)+3)+(4)                 #318:     1+((2)+3)+4
#319:   1+((2)+3+(4))                 #320:     1+((2)+3+4)
#321:   1+((2+(3))+(4))               #322:     1+((2+(3))+4)
#323:   1+((2+3)+(4))                 #324:     1+((2+3)+4)
#325:   1+(2)+((3)+(4))               #326:     1+(2)+((3)+4)
#327:   1+(2)+(3)+(4)                 #328:     1+(2)+(3)+4
#329:   1+(2)+(3+(4))                 #330:     1+(2)+(3+4)
#331:   1+(2)+3+(4)                   #332:     1+(2)+3+4
#333:   1+(2+((3)+(4)))               #334:     1+(2+((3)+4))
#335:   1+(2+(3))+(4)                 #336:     1+(2+(3))+4
#337:   1+(2+(3)+(4))                 #338:     1+(2+(3)+4)
#339:   1+(2+(3+(4)))                 #340:     1+(2+(3+4))
#341:   1+(2+3)+(4)                   #342:     1+(2+3)+4
#343:   1+(2+3+(4))                   #344:     1+(2+3+4)
#345:   1+2+((3)+(4))                 #346:     1+2+((3)+4)
#347:   1+2+(3)+(4)                   #348:     1+2+(3)+4
#349:   1+2+(3+(4))                   #350:     1+2+(3+4)
#351:   1+2+3+(4)                     #352:     1+2+3+4

Если же запретить брать в скобки отдельную цифру, то столько:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#0:     (((1+2)+3)+4)
#1:     ((1+(2+3))+4)
#2:     ((1+2)+(3+4))
#3:     ((1+2)+3)+4
#4:     ((1+2)+3+4)
#5:     ((1+2+3)+4)
#6:     (1+((2+3)+4))
#7:     (1+(2+(3+4)))
#8:     (1+(2+3))+4
#9:     (1+(2+3)+4)
#10:    (1+(2+3+4))
#11:    (1+2)+(3+4)
#12:    (1+2)+3+4
#13:    (1+2+(3+4))
#14:    (1+2+3)+4
#15:    (1+2+3+4)
#16:    1+((2+3)+4)
#17:    1+(2+(3+4))
#18:    1+(2+3)+4
#19:    1+(2+3+4)
#20:    1+2+(3+4)
#21:    1+2+3+4

Если же оставить только те, что реально задают последовательность выполнения операций, то их на одну меньше, чем у вас.

@lifestyle · 31.10.2010, 09:20 **[ТС]**

мне нужно такие расстиановки как у меня, почему меньше на 1? хотя (1+2+3+4) можно в скобки не брать просто это значение якобы без скобок тоже нужно посчитать поэтому и вписал.
Mr.X,
вы можете что то посоветовать?

@Mr.X · 31.10.2010, 13:47

Сообщение от lifestyle

мне нужно такие расстиановки как у меня, почему меньше на 1? хотя (1+2+3+4) можно в скобки не брать просто это значение якобы без скобок тоже нужно посчитать поэтому и вписал.
Mr.X,
вы можете что то посоветовать?

Что-то я сразу не вчитался внимательно в ваш пример, но он и последовательность действий операторов не задает! Для этого нужна следующая расстановка:

C++
1
2
3
4
5
6
Посл. действий              Расстановка
123:                    (1 + 2) + 3) + 4
132, 312:                   (1 + 2) + (3 + 4)
213:                    (1 + (2 + 3)) + 4
231:                    1 + ((2 + 3) + 4)
321:                    1 + (2 + (3 + 4))

В общем, непонятно что ваши скобки означают. Поясните цель.

silent_1991 · 31.10.2010, 14:45

Моё мнение - глупо было приводить пример для операции "+". Потому что как ты тут скобки не ставь, получишь один и тот же результат. Мне же интересна цель - тупо расставить скобки всеми способами, или же так, чтобы, например, получить только один какой-то результат или, скажем, диапазон результатов. Короче, интересна цель расстановки - получить какой-то результат или же тупо перебрать варианты?

KuKu · 31.10.2010, 16:49

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

@Christopher M. · 31.10.2010, 19:45

Сообщение от KuKu

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

Ага, все замечательно, только там еще есть первая строчка, в которой _две_пары скобок. Так что как минимум понадобится еще один цикл, для перебора всех возможных количеств пар скобок...

Да и вообще, по-моему тут как раз не надо париться с получаемым порядком действий и прочей жестью. Ибо, насколько я понимаю, вложенные скобки не допускаются? И поэтому не каждый порядок действий можно будет получить...

Добавлено через 26 минут
А вообще, если учесть, что:
- правая скобка не может стоять раньше левой
- левая скобка всегда стоит перед числом, а правая - всегда после
можно адресовать скобки строго относительно чисел. Т.е. если около числа - скобка, ставим единицу, а если нету ее - то ноль. Т.е. для приведенного примера картина примерно:
(1+2)+(3+4) - 1111
(1+2)+3+4 - 1100
1+(2+3)+4 - 0011
1+2+(3+4) - 0110
(1+2+3)+4 - 1010
1+(2+3+4) - 0101
(1+2+3+4) - 1001
Вот. Так как цифер не больше восьми, можно тупо перебирать числа, и выбирать те, в которых четное количество бит. Расшифровывать потом легко - первая единица - левая скобка, следующая - правая и т.д.

P.S. \мечтательно\ На ассемблере такое реализуется красиво... с использованием условного перехода по флагу четности...

KuKu · 31.10.2010, 19:51

Christopher M., да вобще красиво получилось.

@Christopher M. · 31.10.2010, 20:00

Сообщение от KuKu

Christopher M., да вобще красиво получилось.

Ага, и с ошибками... На самом деле

Code
1
2
3
4
5
6
7
(1+2)+(3+4) - 1111 
(1+2)+3+4   - 1100
1+(2+3)+4   - 0110
1+2+(3+4)   - 0011
(1+2+3)+4   - 1010
1+(2+3+4)   - 0101
(1+2+3+4)   - 1001

@lifestyle · 31.10.2010, 21:41 **[ТС]**

Сообщение от silent_1991

Моё мнение - глупо было приводить пример для операции "+". Потому что как ты тут скобки не ставь, получишь один и тот же результат. Мне же интересна цель - тупо расставить скобки всеми способами, или же так, чтобы, например, получить только один какой-то результат или, скажем, диапазон результатов. Короче, интересна цель расстановки - получить какой-то результат или же тупо перебрать варианты?

я эе писал не в операторе дело. мне нужно тупо перебор всех вариаций скобок.А на счет глупо оператор +..... читайте внимательнее вопрос, про оператор там тоже написано, не в выборе оператора вопрос.

А вообще задача состоит в следующем:
Есть 4 числа например 2,4,6,8 и 25 нужно написать программу которая бы проверяла существует ли комбинация из данных цифр, 4 операторов и определенной расстановки скобочек чтобы результат был равен 25. итог: программа в файл должна записать все подходящие комбинации .
следующий этап- обобщить данный алгоритм от 4 до 8 цифр + 1 результат.
с перебором операторов и комбинаций проблем нет, вопрос со скобками как сделать?
реализация на Си/Си++. решил вписывать выражение в string что вы посоветуете?

Добавлено через 3 минуты
KuKu,
да , но тогда выпадает такой вариант (1+2)+(3+4)
хотя Б-г с ним, допускается такой расклад (можно его откинуть)
но тогда на 5 цифр отпадет большее количество растановок...

Добавлено через 53 секунды
Christopher M.,
действительно красиво и все бы ничего, НО по какому поринципу формировать эти бинарные числа 1001 1111 и т.д.?

KuKu · 31.10.2010, 21:43

Сообщение от lifestyle

Christopher M.,
действительно красиво и все бы ничего, НО по какому поринципу формировать эти бинарные числа 1001 1111 и т.д.?

все возможные положения четного числа единичек.

@lifestyle · 31.10.2010, 22:02 **[ТС]**

KuKu,
что они обозначают, но или я чего то не допонимаю ,либо лентяй или еще что, НО
ИМХО много лишней работы нужно переберать комбинации после чего их привязывать к индексам в массив/стринге выражения....
не проще ли двигать скобку с каждой итерацией? проблема останеться только в другом- нужно каким-то макаром разработать алгоритм подбора скобок вида (1+2)+(3+4)
или я не прав и чего то не допонимаю?

@Хохол · 31.10.2010, 22:05

Сообщение от lifestyle

Есть 4 числа например 2,4,6,8 и 25 нужно написать программу которая бы проверяла существует ли комбинация из данных цифр, 4 операторов и определенной расстановки скобочек чтобы результат был равен 25. итог: программа в файл должна записать все подходящие комбинации .

Числа обязательно в этом порядке, или можно менять их местами?

@lifestyle · 31.10.2010, 22:30 **[ТС]**

Хохол,
конечно можно менять и алгоритм это иделает

@Mr.X · 01.11.2010, 10:13

Можно подставлять любые положительные целые числа в любом количестве.

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
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
//////////////////////////////////////////////////////////////////////////////////////
//Есть 4 числа например 2,4,6,8 и 25 нужно написать программу которая бы проверяла 
//существует ли комбинация из данных цифр, 4 операторов и определенной расстановки 
//скобочек чтобы результат был равен 25. итог: программа в файл должна записать 
//все подходящие комбинации .
//следующий этап- обобщить данный алгоритм от 4 до 8 цифр + 1 результат.
//////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <cctype>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <set>
#include <sstream>
#include <string>
#include <vector>
//////////////////////////////////////////////////////////////////////////////////////
typedef std::string        T_str;
typedef std::set<T_str>    T_strings;
typedef std::vector<int>   T_operands;
typedef double             T_num;
//////////////////////////////////////////////////////////////////////////////////////
T_num  calculate                (T_str&  s_inp);
void   remove_spaces            (T_str&  s);
bool   calc_expr                (const T_str&  s_inp, T_str&  s_out, T_num& res);
bool   calc_summand             (const T_str&  s_inp, T_str&  s_out, T_num& res);
bool   calc_line_of_summand     (const T_str&  s_inp, T_str&  s_out, T_num& res);
bool   calc_factor              (const T_str&  s_inp, T_str&  s_out, T_num& res);
bool   calc_minus_factor        (const T_str&  s_inp, T_str&  s_out, T_num& res);
bool   calc_line_of_factor      (const T_str&  s_inp, T_str&  s_out, T_num& res);
bool   calc_add_summand         (const T_str&  s_inp, T_str&  s_out, T_num& res);
bool   calc_subtract_summand    (const T_str&  s_inp, T_str&  s_out, T_num& res);
bool   calc_expr_in_brackets    (const T_str&  s_inp, T_str&  s_out, T_num& res);
bool   calc_num                 (const T_str&  s_inp, T_str&  s_out, T_num& res);
bool   calc_mult_to_factor      (const T_str&  s_inp, T_str&  s_out, T_num& res);
bool   calc_div_into_factor     (const T_str&  s_inp, T_str&  s_out, T_num& res);
bool   calc_minus               (const T_str&  s_inp, T_str&  s_out);
bool   calc_plus                (const T_str&  s_inp, T_str&  s_out);
bool   calc_asterisk            (const T_str&  s_inp, T_str&  s_out);
bool   calc_slash               (const T_str&  s_inp, T_str&  s_out);
bool   calc_left_parenthesis    (const T_str&  s_inp, T_str&  s_out);
bool   calc_right_parenthesis   (const T_str&  s_inp, T_str&  s_out);
bool   calc_symb                (const char c, const T_str&  s_inp, T_str&  s_out);
///////////////////////////////////////////////////////////////////////////////
T_num  calculate(T_str&  s_inp)
{
    T_num  res;
    const char FINISH_SYMB = '$';    
    remove_spaces(s_inp);
    T_str  s_out;    
    calc_expr(s_inp + FINISH_SYMB, s_out, res);            
    return  res;
}
///////////////////////////////////////////////////////////////////////////////
void  remove_spaces(T_str&  s)
{    
    for(;;)
    {
        T_str::size_type  pos = s.find_first_of(" \t");   
        if(pos == T_str::npos)
        {
            break;
        }
        s = s.erase(pos, 1);
    }    
}
///////////////////////////////////////////////////////////////////////////////
bool  calc_expr(const T_str&  s_inp, T_str&  s_out, T_num& res)
{    
    return     calc_summand         (s_inp, s_out, res)
            && calc_line_of_summand (s_out, s_out, res);   
}
///////////////////////////////////////////////////////////////////////////////
bool  calc_summand(const T_str&  s_inp, T_str&  s_out, T_num& res)
{    
    return     calc_factor         (s_inp, s_out, res)
            && calc_line_of_factor (s_out, s_out, res);   
}
///////////////////////////////////////////////////////////////////////////////
bool  calc_line_of_summand(const T_str&  s_inp, T_str&  s_out, T_num& res)
{   
    switch(s_inp[0])
    {
    case '+':
        return     calc_add_summand      (s_inp, s_out, res)
                && calc_line_of_summand  (s_out, s_out, res);
    case '-':
        return     calc_subtract_summand (s_inp, s_out, res)
                && calc_line_of_summand  (s_out, s_out, res);
    default:
        return  true;
    }
}
///////////////////////////////////////////////////////////////////////////////
bool  calc_factor(const T_str&  s_inp, T_str&  s_out, T_num& res)
{    
    switch(s_inp[0])
    {
    case '-':
        return  calc_minus_factor     (s_inp, s_out, res);
    case '(':
        return  calc_expr_in_brackets (s_inp, s_out, res);
    default:
        return  calc_num              (s_inp, s_out, res);
    }
}
///////////////////////////////////////////////////////////////////////////////
bool  calc_minus_factor(const T_str&  s_inp, T_str&  s_out, T_num& res)
{    
    bool   bool_res =    calc_minus  (s_inp, s_out)
                      && calc_factor (s_out, s_out, res);
    res *= -1;
    return  bool_res;
}
///////////////////////////////////////////////////////////////////////////////
bool  calc_line_of_factor(const T_str&  s_inp, T_str&  s_out, T_num& res)
{
    switch(s_inp[0])
    {
    case '*':
        return     calc_mult_to_factor  (s_inp, s_out, res)
                && calc_line_of_factor  (s_out, s_out, res);
    case '/':
        return     calc_div_into_factor (s_inp, s_out, res)
                && calc_line_of_factor  (s_out, s_out, res);
    default:
        return  true;
    }
}
///////////////////////////////////////////////////////////////////////////////
bool  calc_add_summand(const T_str&  s_inp, T_str&  s_out, T_num& res)
{    
    T_num  res_summand;
    bool   bool_res =     calc_plus    (s_inp, s_out)
                       && calc_summand (s_out, s_out, res_summand);
    res += res_summand;
    return  bool_res;
}
///////////////////////////////////////////////////////////////////////////////
bool  calc_subtract_summand(const T_str&  s_inp, T_str&  s_out, T_num& res)
{    
    T_num  res_summand;
    bool   bool_res =     calc_minus   (s_inp, s_out)
                       && calc_summand (s_out, s_out, res_summand);
    res -= res_summand;
    return  bool_res;
}
///////////////////////////////////////////////////////////////////////////////
bool  calc_mult_to_factor(const T_str&  s_inp, T_str&  s_out, T_num& res)
{    
    T_num  res_factor;
    bool   bool_res =     calc_asterisk (s_inp, s_out)
                       && calc_factor   (s_out, s_out, res_factor);
    res *= res_factor;
    return  bool_res;
}
///////////////////////////////////////////////////////////////////////////////
bool  calc_div_into_factor(const T_str&  s_inp, T_str&  s_out, T_num& res)
{    
    T_num  res_factor;
    bool   bool_res =     calc_slash  (s_inp, s_out)
                       && calc_factor (s_out, s_out, res_factor);
    res /= res_factor;
    return  bool_res;
}
///////////////////////////////////////////////////////////////////////////////
bool  calc_plus(const T_str&  s_inp, T_str&  s_out)
{
    return  calc_symb('+', s_inp, s_out);
}
///////////////////////////////////////////////////////////////////////////////
bool  calc_asterisk(const T_str&  s_inp, T_str&  s_out)
{
    return  calc_symb('*', s_inp, s_out);
}
///////////////////////////////////////////////////////////////////////////////
bool  calc_slash(const T_str&  s_inp, T_str&  s_out)
{
    return  calc_symb('/', s_inp, s_out);
}
///////////////////////////////////////////////////////////////////////////////
bool  calc_minus(const T_str&  s_inp, T_str&  s_out)
{
    return  calc_symb('-', s_inp, s_out);
}
///////////////////////////////////////////////////////////////////////////////
bool  calc_expr_in_brackets(const T_str&  s_inp, T_str&  s_out, T_num& res)
{
    return     calc_left_parenthesis  (s_inp, s_out)
            && calc_expr              (s_out, s_out, res)
            && calc_right_parenthesis (s_out, s_out);
}
///////////////////////////////////////////////////////////////////////////////
bool  calc_num(const T_str&  s_inp, T_str&  s_out, T_num& res)
{
    std::istringstream  in_potok(s_inp);    
    bool  bool_res = ((in_potok >> res) != 0);
    in_potok >> s_out;
    return  bool_res;
}
///////////////////////////////////////////////////////////////////////////////
bool  calc_left_parenthesis(const T_str&  s_inp, T_str&  s_out)
{
    return  calc_symb('(', s_inp, s_out);
}
///////////////////////////////////////////////////////////////////////////////
bool  calc_right_parenthesis(const T_str&  s_inp, T_str&  s_out)
{
    return  calc_symb(')', s_inp, s_out);
}
///////////////////////////////////////////////////////////////////////////////
bool  calc_symb(const char c, const T_str&  s_inp, T_str&  s_out)
{    
    bool  res = (s_inp[0] == c);
    if(res)
    {        
        s_out = s_inp.substr(1);
    }
    return res;    
}
///////////////////////////////////////////////////////////////////////////////
//calc
 
//////////////////////////////////////////////////////////////////////////////////////
T_strings  get_brackets_placing(const T_str&  str, int step = 0);
//////////////////////////////////////////////////////////////////////////////////////
T_strings  get_brackets_placing
    (
        const T_str&  str_left,
        const T_str&  op,
        const T_str&  str_right,
        int           step
    )
{
    T_strings  res_strings;
    T_strings  left_strings   = get_brackets_placing(str_left,   step + 1);
    T_strings  right_strings  = get_brackets_placing(str_right,  step + 1);
    for(T_strings::const_iterator  left_str_it = left_strings.begin();
        left_str_it != left_strings.end(); ++left_str_it)
    {
        for(T_strings::const_iterator  right_str_it = right_strings.begin();
            right_str_it != right_strings.end(); ++right_str_it)
        {
            res_strings.insert(*left_str_it + op + *right_str_it);
        }   
    }
    return  res_strings;
}
//////////////////////////////////////////////////////////////////////////////////////
T_strings  get_brackets_placing(const T_str&  str, int step)
{
    const  T_str  OP_STR = "+-*/";
    T_strings  res_strings;
    T_str::size_type  op_pos = 0;
    while((op_pos = str.find_first_of(OP_STR, op_pos)) != T_str::npos)
    {
        T_strings  res_strings_loc = get_brackets_placing
                                         (
                                             str.substr(0, op_pos),
                                             str.substr(op_pos, 1),
                                             str.substr(op_pos + 1),
                                             step + 1
                                         );
 
        res_strings.insert(res_strings_loc.begin(), res_strings_loc.end());
        ++op_pos;
    }
 
    if(step)
    {
        for(T_strings::const_iterator  res_str_it = res_strings.begin();
            res_str_it != res_strings.end(); ++res_str_it)
        {
            res_strings.insert(T_str("(") + *res_str_it + ")");
        }    
    }    
    
    if(res_strings.empty())
    {
        res_strings.insert(str);
    }    
 
    return  res_strings;
}
//////////////////////////////////////////////////////////////////////////////////////
bool  inc_op_str(T_str&  op_str)
{
    for(int i = op_str.size() - 1; i >= 0; --i)
    {
        switch(op_str[i])
        {
        case '+':
            op_str[i] = '-';
            return  true;
 
        case '-':
            op_str[i] = '*';
            return  true;
 
        case '*':
            op_str[i] = '/';
            return  true;
 
        default:
            ;
        }
    }
    return  false;
}
//////////////////////////////////////////////////////////////////////////////////////
T_str  int_to_str(int k)
{
    std::ostringstream  sout;
    sout << k;
    return  sout.str();
}
//////////////////////////////////////////////////////////////////////////////////////
void  print_results
    (
        T_operands&  operands, 
        int          res
    )
{
    int  res_count = 0;
    std::sort(operands.begin(), operands.end());
    //Перебираем все перестановки набора операндов.
    do
    {        
        T_str  op_str(operands.size() - 1, '+');
        //Перебираем все возможные перестановки операций.
        do
        {
            T_str  expr_str;
            for(size_t  i = 0; i < operands.size() - 1; ++i)
            {
                expr_str.append(int_to_str(operands[i]) + op_str[i]);
            }    
            expr_str.append(int_to_str(operands.back()));
            //Получаем все возможные расстановки скобок.
            T_strings  expr_strings = get_brackets_placing(expr_str, 0);
            //Перебираем все полученные выражения:
            for(T_strings::iterator  expr_str_it = expr_strings.begin();
                expr_str_it != expr_strings.end(); ++expr_str_it)
            {
                //Печатаем те, результат вычисления  которых равен res:
                T_str  expr_str = *expr_str_it;
                if(calculate(expr_str) == res)
                {
                    std::cout << "#"
                              << ++res_count
                              << ":\t"
                              << *expr_str_it 
                              << std::endl;
                }
            }
        }while(inc_op_str(op_str));        
    }
    while(std::next_permutation(operands.begin(), operands.end())); 
}
//////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    int n;
    do
    {
        std::cout << "Введите количество операндов >= 0: ";
        std::cin >> n;
    }while(n < 0);
 
    std::cout << "Введите целые значения "
              << n
              << " операндов:"
              << std::endl;
 
    T_operands  operands(n);
    for(T_operands::iterator  operand_it = operands.begin(); 
        operand_it != operands.end(); ++operand_it)
    {
        std::cout << "A"
                  << std::distance(operands.begin(), operand_it) + 1
                  << " = ";
        std::cin >> *operand_it;
    }
 
    std::cout << "Введите желаемый целый результат: ";
    int  res;
    std::cin >> res;
    print_results(operands, res);    
}

@lifestyle · 01.11.2010, 11:39 **[ТС]**

Mr.X,
Спасибо огромное))) но я хочу своё реализовать))))ваш поизучаю обязательно))еще раз спасибо)

Добавлено через 14 минут
Хм ваш код не работает на 2 4 6 8 (25)

Добавлено через 4 минуты

ААА дошло , предпологаю изза использования int сей баг

@Mr.X · 01.11.2010, 11: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
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
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
//////////////////////////////////////////////////////////////////////////////////////
//Есть 4 числа например 2,4,6,8 и 25 нужно написать программу которая бы проверяла 
//существует ли комбинация из данных цифр, 4 операторов и определенной расстановки 
//скобочек чтобы результат был равен 25. итог: программа в файл должна записать 
//все подходящие комбинации .
//следующий этап- обобщить данный алгоритм от 4 до 8 цифр + 1 результат.
//////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <cctype>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <set>
#include <sstream>
#include <string>
#include <vector>
//////////////////////////////////////////////////////////////////////////////////////
typedef std::string        T_str;
typedef std::set<T_str>    T_strings;
typedef std::vector<int>   T_operands;
typedef double             T_num;
//////////////////////////////////////////////////////////////////////////////////////
T_num  calculate                (T_str&  s_inp);
void   remove_spaces            (T_str&  s);
bool   calc_expr                (const T_str&  s_inp, T_str&  s_out, T_num& res);
bool   calc_summand             (const T_str&  s_inp, T_str&  s_out, T_num& res);
bool   calc_line_of_summand     (const T_str&  s_inp, T_str&  s_out, T_num& res);
bool   calc_factor              (const T_str&  s_inp, T_str&  s_out, T_num& res);
bool   calc_minus_factor        (const T_str&  s_inp, T_str&  s_out, T_num& res);
bool   calc_line_of_factor      (const T_str&  s_inp, T_str&  s_out, T_num& res);
bool   calc_add_summand         (const T_str&  s_inp, T_str&  s_out, T_num& res);
bool   calc_subtract_summand    (const T_str&  s_inp, T_str&  s_out, T_num& res);
bool   calc_expr_in_brackets    (const T_str&  s_inp, T_str&  s_out, T_num& res);
bool   calc_num                 (const T_str&  s_inp, T_str&  s_out, T_num& res);
bool   calc_mult_to_factor      (const T_str&  s_inp, T_str&  s_out, T_num& res);
bool   calc_div_into_factor     (const T_str&  s_inp, T_str&  s_out, T_num& res);
bool   calc_minus               (const T_str&  s_inp, T_str&  s_out);
bool   calc_plus                (const T_str&  s_inp, T_str&  s_out);
bool   calc_asterisk            (const T_str&  s_inp, T_str&  s_out);
bool   calc_slash               (const T_str&  s_inp, T_str&  s_out);
bool   calc_left_parenthesis    (const T_str&  s_inp, T_str&  s_out);
bool   calc_right_parenthesis   (const T_str&  s_inp, T_str&  s_out);
bool   calc_symb                (const char c, const T_str&  s_inp, T_str&  s_out);
///////////////////////////////////////////////////////////////////////////////
T_num  calculate(T_str&  s_inp)
{
    T_num  res;
    const char FINISH_SYMB = '$';    
    remove_spaces(s_inp);
    T_str  s_out;    
    calc_expr(s_inp + FINISH_SYMB, s_out, res);            
    return  res;
}
///////////////////////////////////////////////////////////////////////////////
void  remove_spaces(T_str&  s)
{    
    for(;;)
    {
        T_str::size_type  pos = s.find_first_of(" \t");   
        if(pos == T_str::npos)
        {
            break;
        }
        s = s.erase(pos, 1);
    }    
}
///////////////////////////////////////////////////////////////////////////////
bool  calc_expr(const T_str&  s_inp, T_str&  s_out, T_num& res)
{    
    return     calc_summand         (s_inp, s_out, res)
            && calc_line_of_summand (s_out, s_out, res);   
}
///////////////////////////////////////////////////////////////////////////////
bool  calc_summand(const T_str&  s_inp, T_str&  s_out, T_num& res)
{    
    return     calc_factor         (s_inp, s_out, res)
            && calc_line_of_factor (s_out, s_out, res);   
}
///////////////////////////////////////////////////////////////////////////////
bool  calc_line_of_summand(const T_str&  s_inp, T_str&  s_out, T_num& res)
{   
    switch(s_inp[0])
    {
    case '+':
        return     calc_add_summand      (s_inp, s_out, res)
                && calc_line_of_summand  (s_out, s_out, res);
    case '-':
        return     calc_subtract_summand (s_inp, s_out, res)
                && calc_line_of_summand  (s_out, s_out, res);
    default:
        return  true;
    }
}
///////////////////////////////////////////////////////////////////////////////
bool  calc_factor(const T_str&  s_inp, T_str&  s_out, T_num& res)
{    
    switch(s_inp[0])
    {
    case '-':
        return  calc_minus_factor     (s_inp, s_out, res);
    case '(':
        return  calc_expr_in_brackets (s_inp, s_out, res);
    default:
        return  calc_num              (s_inp, s_out, res);
    }
}
///////////////////////////////////////////////////////////////////////////////
bool  calc_minus_factor(const T_str&  s_inp, T_str&  s_out, T_num& res)
{    
    bool   bool_res =    calc_minus  (s_inp, s_out)
                      && calc_factor (s_out, s_out, res);
    res *= -1;
    return  bool_res;
}
///////////////////////////////////////////////////////////////////////////////
bool  calc_line_of_factor(const T_str&  s_inp, T_str&  s_out, T_num& res)
{
    switch(s_inp[0])
    {
    case '*':
        return     calc_mult_to_factor  (s_inp, s_out, res)
                && calc_line_of_factor  (s_out, s_out, res);
    case '/':
        return     calc_div_into_factor (s_inp, s_out, res)
                && calc_line_of_factor  (s_out, s_out, res);
    default:
        return  true;
    }
}
///////////////////////////////////////////////////////////////////////////////
bool  calc_add_summand(const T_str&  s_inp, T_str&  s_out, T_num& res)
{    
    T_num  res_summand;
    bool   bool_res =     calc_plus    (s_inp, s_out)
                       && calc_summand (s_out, s_out, res_summand);
    res += res_summand;
    return  bool_res;
}
///////////////////////////////////////////////////////////////////////////////
bool  calc_subtract_summand(const T_str&  s_inp, T_str&  s_out, T_num& res)
{    
    T_num  res_summand;
    bool   bool_res =     calc_minus   (s_inp, s_out)
                       && calc_summand (s_out, s_out, res_summand);
    res -= res_summand;
    return  bool_res;
}
///////////////////////////////////////////////////////////////////////////////
bool  calc_mult_to_factor(const T_str&  s_inp, T_str&  s_out, T_num& res)
{    
    T_num  res_factor;
    bool   bool_res =     calc_asterisk (s_inp, s_out)
                       && calc_factor   (s_out, s_out, res_factor);
    res *= res_factor;
    return  bool_res;
}
///////////////////////////////////////////////////////////////////////////////
bool  calc_div_into_factor(const T_str&  s_inp, T_str&  s_out, T_num& res)
{    
    T_num  res_factor;
    bool   bool_res =     calc_slash  (s_inp, s_out)
                       && calc_factor (s_out, s_out, res_factor);
    res /= res_factor;
    return  bool_res;
}
///////////////////////////////////////////////////////////////////////////////
bool  calc_plus(const T_str&  s_inp, T_str&  s_out)
{
    return  calc_symb('+', s_inp, s_out);
}
///////////////////////////////////////////////////////////////////////////////
bool  calc_asterisk(const T_str&  s_inp, T_str&  s_out)
{
    return  calc_symb('*', s_inp, s_out);
}
///////////////////////////////////////////////////////////////////////////////
bool  calc_slash(const T_str&  s_inp, T_str&  s_out)
{
    return  calc_symb('/', s_inp, s_out);
}
///////////////////////////////////////////////////////////////////////////////
bool  calc_minus(const T_str&  s_inp, T_str&  s_out)
{
    return  calc_symb('-', s_inp, s_out);
}
///////////////////////////////////////////////////////////////////////////////
bool  calc_expr_in_brackets(const T_str&  s_inp, T_str&  s_out, T_num& res)
{
    return     calc_left_parenthesis  (s_inp, s_out)
            && calc_expr              (s_out, s_out, res)
            && calc_right_parenthesis (s_out, s_out);
}
///////////////////////////////////////////////////////////////////////////////
bool  calc_num(const T_str&  s_inp, T_str&  s_out, T_num& res)
{
    std::istringstream  in_potok(s_inp);    
    bool  bool_res = ((in_potok >> res) != 0);
    in_potok >> s_out;
    return  bool_res;
}
///////////////////////////////////////////////////////////////////////////////
bool  calc_left_parenthesis(const T_str&  s_inp, T_str&  s_out)
{
    return  calc_symb('(', s_inp, s_out);
}
///////////////////////////////////////////////////////////////////////////////
bool  calc_right_parenthesis(const T_str&  s_inp, T_str&  s_out)
{
    return  calc_symb(')', s_inp, s_out);
}
///////////////////////////////////////////////////////////////////////////////
bool  calc_symb(const char c, const T_str&  s_inp, T_str&  s_out)
{    
    bool  res = (s_inp[0] == c);
    if(res)
    {        
        s_out = s_inp.substr(1);
    }
    return res;    
}
///////////////////////////////////////////////////////////////////////////////
//calc
 
//////////////////////////////////////////////////////////////////////////////////////
T_strings  get_brackets_placing(const T_str&  str, int step = 0);
//////////////////////////////////////////////////////////////////////////////////////
T_strings  get_brackets_placing
    (
        const T_str&  str_left,
        const T_str&  op,
        const T_str&  str_right,
        int           step
    )
{
    T_strings  res_strings;
    T_strings  left_strings   = get_brackets_placing(str_left,   step + 1);
    T_strings  right_strings  = get_brackets_placing(str_right,  step + 1);
    for(T_strings::const_iterator  left_str_it = left_strings.begin();
        left_str_it != left_strings.end(); ++left_str_it)
    {
        for(T_strings::const_iterator  right_str_it = right_strings.begin();
            right_str_it != right_strings.end(); ++right_str_it)
        {
            res_strings.insert(*left_str_it + op + *right_str_it);
        }   
    }
    return  res_strings;
}
//////////////////////////////////////////////////////////////////////////////////////
T_strings  get_brackets_placing(const T_str&  str, int step)
{
    const  T_str  OP_STR = "+-*/";
    T_strings  res_strings;
    T_str::size_type  op_pos = 0;
    while((op_pos = str.find_first_of(OP_STR, op_pos)) != T_str::npos)
    {
        T_strings  res_strings_loc = get_brackets_placing
                                         (
                                             str.substr(0, op_pos),
                                             str.substr(op_pos, 1),
                                             str.substr(op_pos + 1),
                                             step + 1
                                         );
 
        res_strings.insert(res_strings_loc.begin(), res_strings_loc.end());
        ++op_pos;
    }
 
    if(step)
    {
        for(T_strings::const_iterator  res_str_it = res_strings.begin();
            res_str_it != res_strings.end(); ++res_str_it)
        {
            res_strings.insert(T_str("(") + *res_str_it + ")");
        }    
    }    
    
    if(res_strings.empty())
    {
        res_strings.insert(str);
    }    
 
    return  res_strings;
}
//////////////////////////////////////////////////////////////////////////////////////
bool  inc_op_str(T_str&  op_str)
{
    for(int i = op_str.size() - 1; i >= 0; --i)
    {
        switch(op_str[i])
        {
        case '+':
            op_str[i] = '-';
            return  true;
 
        case '-':
            op_str[i] = '*';
            return  true;
 
        case '*':
            op_str[i] = '/';
            return  true;
 
        default:
            op_str[i] = '+';            
        }
    }
    return  false;
}
//////////////////////////////////////////////////////////////////////////////////////
T_str  int_to_str(int k)
{
    std::ostringstream  sout;
    sout << k;
    return  sout.str();
}
//////////////////////////////////////////////////////////////////////////////////////
void  print_results
    (
        T_operands&  operands, 
        int          res
    )
{
    int  res_count = 0;
    std::sort(operands.begin(), operands.end());
    //Перебираем все перестановки набора операндов.
    do
    {        
        T_str  op_str(operands.size() - 1, '+');
        //Перебираем все возможные перестановки операций.
        do
        {
            T_str  expr_str;
            for(size_t  i = 0; i < operands.size() - 1; ++i)
            {
                expr_str.append(int_to_str(operands[i]) + op_str[i]);
            }    
            expr_str.append(int_to_str(operands.back()));
            //Получаем все возможные расстановки скобок.
            T_strings  expr_strings = get_brackets_placing(expr_str, 0);
            //Перебираем все полученные выражения:
            for(T_strings::iterator  expr_str_it = expr_strings.begin();
                expr_str_it != expr_strings.end(); ++expr_str_it)
            {
                //Печатаем те, результат вычисления  которых равен res:
                T_str  expr_str = *expr_str_it;
                if(calculate(expr_str) == res)
                {
                    std::cout << "#"
                              << ++res_count
                              << ":\t"
                              << *expr_str_it 
                              << std::endl;
                }
            }
        }while(inc_op_str(op_str));        
    }
    while(std::next_permutation(operands.begin(), operands.end())); 
}
//////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    int n;
    do
    {
        std::cout << "Введите количество операндов >= 0: ";
        std::cin >> n;
    }while(n < 0);
 
    std::cout << "Введите целые значения "
              << n
              << " операндов:"
              << std::endl;
 
    T_operands  operands(n);
    for(T_operands::iterator  operand_it = operands.begin(); 
        operand_it != operands.end(); ++operand_it)
    {
        std::cout << "A"
                  << std::distance(operands.begin(), operand_it) + 1
                  << " = ";
        std::cin >> *operand_it;
    }
 
    std::cout << "Введите желаемый целый результат: ";
    int  res;
    std::cin >> res;
    print_results(operands, res);    
}

@lifestyle · 01.11.2010, 13:22 **[ТС]**

Mr.X,
что то с вашим кодом не могу разобраться, как вы скобочки расставляете?

@Mr.X · 01.11.2010, 13:26

Сообщение от lifestyle

Mr.X,
что то с вашим кодом не могу разобраться, как вы скобочки расставляете?

Рекурсивно с помощью двух функций get_brackets_placing.

@lifestyle · 01.11.2010, 13:29 **[ТС]**

Mr.X,
вот их то я и не могу понять=))
скажем так, по какому принципу вы определяете где и когда из ставить?

Новые блоги и статьи Все статьи Все блоги /
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 . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@lifestyle Mobile Developer 238 / 234 / 18 Регистрация: 10.05.2009 Сообщений: 917

	Расстановка скобочек в выражении (все комбинации) 30.10.2010, 21:09. Показов 7142. Ответов 24 Метки нет (Все метки) собственно сабж: расстановка всех комибинаций скобочек в мат. выражении от 4 до 8 цифр в выражении. пример: есть выражение 1+2+3+4 все комб.: (1+2)+(3+4) (1+2)+3+4 1+(2+3)+4 1+2+(3+4) (1+2+3)+4 1+(2+3+4) (1+2+3+4) П.С. + любой оператор может быть (+,-,*,/) Что можете посоветовать. ума не приложу как сие проделать можно еще и в обобщеном варианте до 8 цифр. 0

@lifestyle Mobile Developer 238 / 234 / 18 Регистрация: 10.05.2009 Сообщений: 917
	31.10.2010, 09:20 [ТС]
	мне нужно такие расстиановки как у меня, почему меньше на 1? хотя (1+2+3+4) можно в скобки не брать просто это значение якобы без скобок тоже нужно посчитать поэтому и вписал. Mr.X, вы можете что то посоветовать? 0

silent_1991 5058 / 3118 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	31.10.2010, 14:45
	Моё мнение - глупо было приводить пример для операции "+". Потому что как ты тут скобки не ставь, получишь один и тот же результат. Мне же интересна цель - тупо расставить скобки всеми способами, или же так, чтобы, например, получить только один какой-то результат или, скажем, диапазон результатов. Короче, интересна цель расстановки - получить какой-то результат или же тупо перебрать варианты? 0

KuKu 1563 / 1041 / 94 Регистрация: 17.04.2009 Сообщений: 2,995
	31.10.2010, 16:49
	Левая скобка может находится в n-1 местах и правая в n-1. Левая не может быть правее правой. И обычным перебором: цикл для изменения положения левой скобки и внутри первого цикл для смены правой. 0

KuKu 1563 / 1041 / 94 Регистрация: 17.04.2009 Сообщений: 2,995
	31.10.2010, 19:51
	Christopher M., да вобще красиво получилось. 0

@lifestyle Mobile Developer 238 / 234 / 18 Регистрация: 10.05.2009 Сообщений: 917
	31.10.2010, 22:02 [ТС]
	KuKu, что они обозначают, но или я чего то не допонимаю ,либо лентяй или еще что, НО ИМХО много лишней работы нужно переберать комбинации после чего их привязывать к индексам в массив/стринге выражения.... не проще ли двигать скобку с каждой итерацией? проблема останеться только в другом- нужно каким-то макаром разработать алгоритм подбора скобок вида (1+2)+(3+4) или я не прав и чего то не допонимаю? 0

@lifestyle Mobile Developer 238 / 234 / 18 Регистрация: 10.05.2009 Сообщений: 917
	31.10.2010, 22:30 [ТС]
	Хохол, конечно можно менять и алгоритм это иделает 0

@lifestyle Mobile Developer 238 / 234 / 18 Регистрация: 10.05.2009 Сообщений: 917
	01.11.2010, 11:39 [ТС]
	Mr.X, Спасибо огромное))) но я хочу своё реализовать))))ваш поизучаю обязательно))еще раз спасибо) Добавлено через 14 минут Хм ваш код не работает на 2 4 6 8 (25) Добавлено через 4 минуты ААА дошло , предпологаю изза использования int сей баг 0

@lifestyle Mobile Developer 238 / 234 / 18 Регистрация: 10.05.2009 Сообщений: 917
	01.11.2010, 13:22 [ТС]
	Mr.X, что то с вашим кодом не могу разобраться, как вы скобочки расставляете? 0

@lifestyle Mobile Developer 238 / 234 / 18 Регистрация: 10.05.2009 Сообщений: 917
	01.11.2010, 13:29 [ТС]
	Mr.X, вот их то я и не могу понять=)) скажем так, по какому принципу вы определяете где и когда из ставить? 0