Генерация случайного математического выражения

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

Пример:

Вот несколько примеров выражений, которые я хочу генерировать случайным образом:

4 + 2                           [easy]
3 * 6 - 7 + 2                   [medium]
6 * 2 + (5 - 3) * 3 - 8         [hard]
(3 + 4) + 7 * 2 - 1 - 9         [hard]
5 - 2 + 4 * (8 - (5 + 1)) + 9   [harder]
(8 - 1 + 3) * 6 - ((3 + 7) * 2) [harder]

Эти легкие и средние из них являются довольно прямо вперед. Случайные ints разделены случайными операторами, здесь нет ничего сумасшедшего. Но у меня возникли проблемы с началом работы с чем-то, что могло бы создать один из сложных и сложных примеров. Я даже не уверен, что один алгоритм может дать мне последние два.

Что я рассматриваю:

Я не могу сказать, что испробовал эти идеи, потому что на самом деле я не хотел тратить много времени, двигаясь в направлении, которое не имело шансов работать в первую очередь. Но все же я подумал о паре решений:

• Использование деревьев
• Использование регулярных выражений
• Использование сумасшедшего цикла for-type (безусловно, худшего)

Что я ищу:

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

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

Также обратите внимание, что мне придется оценить эти выражения. Это можно сделать либо после генерации выражения, либо во время его создания. Если вы примите это во внимание в своем ответе, это здорово.

Я не ищу ничего связанного с языком, но для записи, я думаю о реализации этого в Objective-C, поскольку это язык, с которым я больше всего работаю в последнее время.

Эти примеры не включали :оператор, так как я только хочу манипулировать ints, и этот оператор добавляет много проверок. Если ваш ответ дает решение по этому вопросу, это здорово.

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

Вот теоретическая интерпретация вашей проблемы.

Вы ищете случайным образом генерировать слова (алгебраические выражения) из заданного языка (бесконечный набор всех синтаксически правильных алгебраических выражений). Вот формальное описание упрощенной алгебраической грамматики, поддерживающей только сложение и умножение:

E -> I 
E -> (E '+' E)
E -> (E '*' E)

Здесь E- это выражение (т. Е. Слово вашего языка) и Iявляется терминальным символом (т. Е. Больше не раскрывается), представляющим целое число. Вышеприведенное определение Eимеет три правила производства . Основываясь на этом определении, мы можем случайным образом построить правильную арифметику следующим образом:

1. Начните с Eодного символа выходного слова.
2. Равномерно выбирайте один из нетерминальных символов.
3. Выберите случайным образом одно из правил производства для этого символа и примените его.
4. Повторите шаги 2 - 4, пока не останутся только символы терминала.
5. Заменить все терминальные символы Iслучайными целыми числами.

Вот пример применения этих алгоритмов:

E
(E + E)
(E + (E * E))
(E + (I * E))
((E + E) + (I * E))
((I + E) + (I * E))
((I + E) + (I * I))
((I + (E * E)) + (I * I))
((I + (E * I)) + (I * I))
((I + (I * I)) + (I * I))
((2 + (5 * 1)) + (7 * 4))

Я предполагаю, что вы решили представить выражение с интерфейсом, Expressionкоторый реализуется классами IntExpression, AddExpressionи MultiplyExpression. Последние два затем будут иметь leftExpressionи rightExpression. Все Expressionподклассы необходимы для реализации evaluateметода, который рекурсивно работает с древовидной структурой, определенной этими объектами, и эффективно реализует составной шаблон .

Обратите внимание, что для приведенной выше грамматики и алгоритма вероятность расширения выражения Eв конечный символ Iравна только p = 1/3, тогда как вероятность расширения выражения в два дополнительных выражения равна 1-p = 2/3. Следовательно, ожидаемое число целых чисел в формуле, полученной с помощью вышеуказанного алгоритма, фактически бесконечно. Ожидаемая длина выражения зависит от отношения повторения

l(0) = 1
l(n) = p * l(n-1) + (1-p) * (l(n-1) + 1)
     = l(n-1) + (1-p)

где l(n)обозначает ожидаемую длину арифметического выражения после nприменения правил производства. Поэтому я предлагаю вам присвоить pправилу довольно высокую вероятность E -> I, так что в итоге вы получите довольно маленькое выражение с высокой вероятностью.

РЕДАКТИРОВАТЬ : Если вы беспокоитесь, что приведенная выше грамматика приводит к слишком большому количеству скобок, посмотрите на ответ Себастьяна Неграсуса , чья грамматика очень элегантно избегает этой проблемы.

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

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

string postfixExpression =""
int termsCount = 0;
while(weWantMoreTerms)
{
    if (termsCount>= 2)
    {
         var next = RandomNumberOrOperator();
         postfixExpression.Append(next);
         if(IsNumber(next)) { termsCount++;}
         else { termsCount--;}
    }
    else
    {
       postfixExpression.Append(RandomNumber);
       termsCount++;
     }
}

очевидно, это псевдокод, поэтому он не тестируется / может содержать ошибки, и вы, вероятно, не будете использовать строку, а стек какого-то различного объединения типа типа

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

Вот мой взгляд на это:

E -> I
E -> M '*' M
E -> E '+' E
M -> I
M -> M '*' M
M -> '(' E '+' E ')'

Eявляется выражением, Iцелым числом и Mявляется выражением, которое является аргументом для операции умножения.

Скобки в «жестком» выражении представляют порядок оценки. Вместо того, чтобы пытаться сгенерировать отображаемую форму напрямую, просто придумайте список операторов в случайном порядке и извлеките форму отображения выражения из этого.

Числа: 1 3 3 9 7 2

Операторы: + * / + *

Результат: ((1 + 3) * 3 / 9 + 7) * 2

Вывод формы отображения - это относительно простой рекурсивный алгоритм.

Обновление: вот алгоритм на Perl для генерации формы отображения. Поскольку +и *являются дистрибутивными, это рандомизирует порядок членов для этих операторов. Это помогает сохранить круглые скобки на одной стороне.

use warnings;
use strict;

sub build_expression
{
    my ($num,$op) = @_;

    #Start with the final term.
    my $last_num = pop @$num; 
    my $last_op = pop @$op;

    #Base case: return the number if there is just a number 
    return $last_num unless defined $last_op;

    #Recursively call for the expression minus the final term.
    my $rest = build_expression($num,$op); 

    #Add parentheses if there is a bare + or - and this term is * or /
    $rest = "($rest)" if ($rest =~ /[+-][^)]+$|^[^)]+[+-]/ and $last_op !~ /[+-]/);

    #Return the two components in a random order for + or *.
    return $last_op =~ m|[-/]| || rand(2) >= 1 ? 
        "$rest $last_op $last_num" : "$last_num $last_op $rest";        
}

my @numbers   = qw/1 3 4 3 9 7 2 1 10/;
my @operators = qw|+ + * / + * * +|;

print build_expression([@numbers],[@operators]) , "\n";

Чтобы расширить древовидный подход, скажем, каждый узел является либо листовым, либо двоичным выражением:

Node := Leaf | Node Operator Node

Обратите внимание, что лист - это просто случайное целое число.

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

Node random_tree(leaf_prob, max_depth)
    if (max_depth == 0 || random() > leaf_prob)
        return random_leaf()

    LHS = random_tree(leaf_prob, max_depth-1)
    RHS = random_tree(leaf_prob, max_depth-1)
    return Node(LHS, RHS, random_operator())

Тогда самое простое правило для печати дерева - это оборачивать ()каждое неконечное выражение и избегать беспокойства о приоритетах операторов.

Например, если я заключу в скобки ваше последнее примерное выражение:

(8 - 1 + 3) * 6 - ((3 + 7) * 2)
((((8 - 1) + 3) * 6) - ((3 + 7) * 2))

Вы можете прочитать дерево, которое его сгенерирует:

                    SUB
                  /      \
               MUL        MUL
             /     6     /   2
          ADD          ADD
         /   3        3   7
       SUB
      8   1

Я бы использовал деревья. Они могут дать вам большой контроль над генерацией выражений. Например, вы можете ограничить глубину для каждой ветви и ширину каждого уровня отдельно. Древовидная генерация также дает ответ уже во время генерации, что полезно, если вы хотите убедиться, что результат (и подрезультаты) достаточно сложный и / или не слишком сложный для решения. Особенно, если вы добавите оператор деления в какой-то момент, вы можете генерировать выражения, которые вычисляются в целые числа.

Вот немного другой взгляд на превосходный ответ Blubb:

То, что вы пытаетесь построить здесь, это по сути парсер, который работает в обратном порядке. Что общего между вашей проблемой и парсером , так это грамматика без контекста , в форме Бэкуса-Наура :

digit ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
number ::= <digit> | <digit> <number>
op ::= '+' | '-' | '*' | '/'
expr ::= <number> <op> <number> | '(' <expr> ')' | '(' <expr> <op> <expr> ')'

Парсеры начинают с потока терминалов (буквальных токенов, таких как 5или *) и пытаются собрать их в нетерминалы (вещи, состоящие из терминалов и других нетерминалов, таких как numberили op). Ваша проблема начинается с нетерминалов и работает в обратном порядке, выбирая что-либо между символами «или» (труба) в случайном порядке, когда встречаются, и рекурсивно повторяя процесс до достижения терминала.

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

В конце 1980-х годов в Usenet была опубликована программа под названием « Spew», которая первоначально была разработана для генерации случайных заголовков таблоидов, а также оказалась отличным средством для экспериментов с этими «обратными грамматиками». Он работает путем чтения шаблона, который управляет производством случайного потока терминалов. Помимо его развлечения (заголовки, песни кантри, произносимая английская тарабарщина), я написал множество шаблонов, которые полезны для генерации тестовых данных, начиная от простого текста до XML и заканчивая синтаксически-правильным, но не компилируемым C. Несмотря на то, что мне 26 лет написанный на K & R C и имеющий уродливый шаблонный формат, он прекрасно компилируется и работает как рекламируется. Я создал шаблон, который решает вашу проблему, и разместил его на pastebin поскольку добавление такого большого количества текста здесь не представляется целесообразным.