Генерация математических выражений предпочтительно без использования стеков или очередей

Question

Учитывая разрешенные операторы +, /, -, * и заданный пользователем список однозначных чисел (любая разрешенная длина), как я могу вывести все возможные комбинации математических выражений (и результирующие значения), которые могут быть сформированы с числами и заданным константным набором операторов? Я также хочу учесть масштабируемость, например, чтобы я мог легко добавить еще один оператор в микс (если это возможно).

Предпочтительно, чтобы решение не использовало стек или очередь, но они не являются неприемлемыми.

Например, если введено:

{1,3,5,7}

тогда возможный вывод будет

(1+3)-(5+7) = -8
(1+5)-(3-7) = 10
etc...  

(13 + 57) - это , а не возможная комбинация, поскольку не допускается объединение цифр.

Также обратите внимание: мне удалось написать нечто подобное, используя Scheme, но я не могу сделать это с помощью Java или C #.

Answer 1

Я не программист на Java или C #, поэтому здесь идет с невежественным ответом. Кажется, ни один из выбранных вами языков не имеет функции eval. Я бы посоветовал взять на борт обратную польскую запись. Захватывайте входные данные как символы в строке или как хотите; кодировать операторы как символы тоже. Затем, используя итераторы или что-то еще, сгенерируйте все возможные упорядочения входных цифр, а затем все возможные упорядочения правильного числа двоичных операторов. Затем используйте пару или около того операторов switch для перевода каждой строки в результат.

Извините, я не могу быть более ясным, надо торопиться.

Answer 2

Классическая задача перестановки.

Хитрость заключается в том, чтобы передать набор указателей на функции для создания массива операторов (стек, список и т. Д.). В C # и Java указатели функций могут быть реализованы объектами и интерфейсами.

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

Обратите внимание, что вы можете иметь только 3 оператора и что неоднозначно, могут ли некоторые операторы применяться к наборам с обеих сторон по-разному.

Например //

a+b / c - d <> (a+b) / (c-d)

Я не уверен, следует ли учитывать скобки. Если они есть, решение немного сложнее (хотя принципы одинаковы). Просто включите набор скобок и пропустите их тоже (хотя вы также должны учитывать ограничение, что левая скобка должна иметь закрывающую правую скобку). Я не буду освещать это здесь.

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

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

Например //

public interface Operator {
    public Double calc(int val1, int val2);
}

public class Add implements Operator {
    public Double calc(int val1, int val2){
        return Double(val1 + val2);
    } 
}

public class Sub implements Operator {
    public Double calc(int val1, int val2){
        return Double(val1 - val2);
    } 
}
public class Mul implements Operator {
    public Double calc(int val1, int val2){
        return Double(val1 * val2);
    } 
}

public class Div implements Operator {
    public Double calc(int val1, int val2){
        return Double(val1 / val2);
    } 
}

public static Double calc(Operator[] operator_list, int[] value_list)
{
  Double ret_val = Double(value_list[0]);

  for (int j = 0; j < operator_list.length(); j++){
    Operator oper = operator_list[j];
    ret_val = oper.calc(ret_val, value_list[j+1]);                 
  }

  return ret_val;
}

public static void main(String[] args)
{ 
int[] values = {1,2,3,4};

Operator add = new Add();
Operator div = new Div();
Operator mul = new Mul();
Operator sub = new Sub();

Operator[] operators = {add, div, sub, mul};

// Calculate from permutation algorithm...
// Don't forget to only generate three values for each permutation!
// out_perm_1 = {add, div, sub};
// out_perm_2 = {div, add, sub};
Operator[] operator_permutations = perm(operators);

// Calculate from permutation algorithm...    
// val_perm_1 = {1,2,3,4};
// val_perm_2 = {2,1,3,4};
int[] value_permutations = perm(values);

// Interleave the two lists...
for (int i=0; i < output_permutations.length(); i++)
{
    for (int j=0; j < value_permutations.length(); j ++)
    {
        System.out.println(calc(output_permutations[i], output_permutations[j]));
    }
}
}

и т.д ...