Проблема со скобками)))))))?

Question

[Wolfbethowen]

В сборниках занимательных математических задач встречается такой тип задач, когда надо из заданных чисел и арифметических знаков составить выражение, дающее какое-то заданное число. Пример такой задачи: "Составьте из чисел 4, 1, 8, 7 и арифметических знаков выражение, равное 24". Ответом может служить такое выражение: "(8-4) * (7-1)". К сожалению, некоторые авторы допускают ошибки и предлагают нерешаемую задачу, поэтому их начальник обратился к программистам.

Необходимо написать такую программу, которая определяет, можно ли построить из заданного набора выражение, равное числу N или нет. Так как это только прототип, то достаточно написать программу, которая работает только с наборами из 4-х чисел, а число N всегда равно 24.

Допустимые арифметические операторы: сложение, вычитание, умножение, деление, скобки.

На входе: массив из 4-х целых чисел от 1 до 9.

На выходе: true (если из заданного набора можно построить выражение, равное 24) или false (если из заданного набора такого выражения построить нельзя).

Пример 1.

На входе: [4, 1, 8, 7]

На выходе: true

Пояснение: (8-4) * (7-1) = 24

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

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
     int a, b, c, d;
     char x, y, z, e, q, w;
     a = 1;
     b = 2;
     c = 3;
     d = 4;
     int[] arr = new int[4];
        arr[0] = 1;
        arr[1] = 2;
        arr[2] = 3;
        arr[3] = 4;
     char[] charr = new char[6];
        charr[0] = '+';
        charr[1] = '-';
        charr[2] = '/';
        charr[3] = '*';
        charr[4] = '(';
        charr[5] =  ')';
 
            for (int i = 0; i < 4; i++) {
                a = arr[i];
                for (int j = 0; j < 4; j++) {
                    if (i != j) {
                        b = arr[j];
                        for (int k = 0; k < 4; k++) {
                            if (k != j & k != i) {
                                c = arr[k];
                                for (int l = 0; l < 4; l++) {
                                    if (l != j & l != k & l != i) {
                                        d = arr[l];
                                        for (int m = 4; m < 5; m++) {  // цикл символов
                                            for (int n = 0; n < 6; n++) {
                                                if (n != m ) {
                                                    for (int o = 0; o < 6; o++) {
                                                        if (o != n & o != m) {
                                                            for (int p = 0; p < 6; p++) {
                                                                if (p != o & p != n & p != m) {
                                                                    for (int r = 0; r < 6; r++) {
                                                                        if (r != m & r != n & r != o & r != p) {
                                                                            for (int s = 0; s < 6; s++) {
                                                                                if (s != m & s != n & s != o & s != p & s != r) {
                                                                                    System.out.println (charr[s] + a + charr[m]  );
 
 
                                                                                }
                                                                            }
                                                                        }
                                                                    }
                                                                }
                                                            }
                                                        }
                                                    }
                                                }
                                            }
                                        }
 
 
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }

Comments

[Максим Федоров]

поэтому их начальник обратился к программистам.

К программистам на Тостере  и вы и есть начальник 
     или к вам обратился  и вы не начальник
          или обратился к программистам, вы не начальник, но и не программист
               или вы начальник и обратился к программистам, но вы не программист..
                    КАК ТУТ НЕ ЗАПУТАТЬСЯ!?!?

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

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

Цикломатическая сложность части программного кода — количество линейно независимых маршрутов через программный код. Например, если исходный код не содержит никаких точек ветвления или циклов, то сложность равна единице, поскольку есть только единственный маршрут через код. Если код имеет единственный оператор IF, содержащий простое условие, то существует два пути через код: один если условие оператора IF имеет значение TRUE и один — если FALSE.

[dollar]

Господи, что за код я только что увидел??
Теперь же заснуть не смогу!

А задача ведь на обычную комбинаторику с полным перебором вариантов.

Answer 1

[dollar]

Я не специалист по Java, но ответ - рекурсия.
Можно и без неё, с эмуляцией стека в массиве, но это по сути то же самое.
Это решает проблему огромной вложенности одинаковых циклов.

Также очень советую изучить формат RPN - он вам значительно упростит как перебор вариантов, так и вычисления. Например, ваш ответ (8-4) * (7-1) будет выглядеть, как массив 8, 4, -, 7, 1, -, *. Скобки исчезают. Задача сводится к перестановке 4 цифр в 7 позициях и перебору операций в оставшихся. Не все варианты валидны, но как именно оптимизировать, и надо ли оно вам или просто чтоб работало - решайте уже сами.

Answer 2

[longclaps]

Я не специалист по Java, но ответ - python.

from itertools import permutations, product
from operator import add, sub, mul, truediv

def f(data):
    oops, res = (add, sub, mul, truediv), {}
    sign = {add: '+', sub: '-', mul: '*', truediv: '/'}
    for t in permutations(data):
        for order in product([0, 1, 2], [0, 1], [0]):
            for ops in product(oops, repeat=3):
                try:
                    ll, ss = list(map(float, t)), list(map(str, t))
                    for i, op in zip(order, ops):
                        ll[i:i + 2] = [op(*ll[i:i + 2])]
                        ss[i:i + 2] = [f'({ss[i]}{sign[op]}{ss[i + 1]})']
                    if ll[0].is_integer():
                        res[int(ll[0])] = ss[0][1:-1]
                except ZeroDivisionError:
                    pass
    return res

for x, s in sorted(f([4, 1, 8, 7]).items()):
    print(f'{x:>4} : {s}')

Фрагмент вывода (там слишком много):

20 : 7+(8+(1+4))
21 : 7*(8-(1+4))
22 : ((7/4)+1)*8
23 : ((7-4)*8)-1
24 : (7-1)*(8-4)
25 : ((7-4)*8)+1
26 : (8*4)-(7-1)
27 : (7*(8-4))-1
28 : 7*(8-(1*4))
29 : (7*(8-4))+1