Generowanie losowego wyrażenia matematycznego

Mam w głowie ten pomysł, aby generować i oceniać losowe wyrażenia matematyczne. Postanowiłem więc spróbować i opracować algorytm, zanim zakoduję go w celu przetestowania.

Przykład:

Oto kilka przykładowych wyrażeń, które chcę generować losowo:

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]

Te łatwe i średnie są dość proste. Losowe introzdzielone losowymi operatorami, nic szalonego tutaj. Ale mam pewne problemy podręczny z czegoś, co może stworzyć jeden z twardych i twardszych przykładów. Nie jestem nawet pewien, czy jeden algorytm mógłby dać mi dwa ostatnie.

Co rozważam:

Nie mogę powiedzieć, że wypróbowałem te pomysły, ponieważ tak naprawdę nie chciałem tracić dużo czasu, idąc w kierunku, który nie miał szans na pracę w pierwszej kolejności. Ale wciąż myślałem o kilku rozwiązaniach:

• Korzystanie z drzew
• Używanie wyrażeń regularnych
• Korzystanie z szalonej pętli typu „for-type” (na pewno najgorsza)

Czego szukam:

Chciałbym wiedzieć, którą drogę według ciebie najlepiej wybrać, między rozwiązaniami, które rozważałem, a własnymi pomysłami.

Jeśli widzisz dobry sposób na rozpoczęcie, doceniłbym trop we właściwym kierunku, np. Wraz z początkiem algorytmu lub jego ogólną strukturą.

Zauważ też, że będę musiał ocenić te wyrażenia. Można to zrobić po wygenerowaniu wyrażenia lub podczas jego tworzenia. Jeśli weźmiesz to pod uwagę w swojej odpowiedzi, to świetnie.

Nie szukam niczego związanego z językiem, ale dla przypomnienia, myślę o wdrożeniu go w Objective-C, ponieważ jest to język, z którym ostatnio najbardziej pracuję.

Te przykłady nie obejmowały :operatora, ponieważ chcę jedynie manipulować ints, a ten operator dodaje wiele weryfikacji. Jeśli Twoja odpowiedź zawiera rozwiązanie tego problemu, to świetnie.

Jeśli moje pytanie wymaga wyjaśnień, proszę pytać w komentarzach. Dzięki za pomoc.

Oto teoretyczna interpretacja twojego problemu.

Chcesz losowo wygenerować słowa (wyrażenie algebraiczne) z danego języka (nieskończony zestaw wszystkich poprawnych składniowo wyrażeń algebraicznych). Oto formalny opis uproszczonej gramatyki algebraicznej obsługującej tylko dodawanie i mnożenie:

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

Tutaj Ejest wyrazem (tj Słowo języku polskim) i Ijest symbolem zacisk (czyli nie jest rozwinięty dalej) reprezentujących liczbę całkowitą. Powyższa definicja Ema trzy reguły produkcji . Na podstawie tej definicji możemy losowo zbudować poprawną arytmetykę w następujący sposób:

1. Zacznij od Ejako pojedynczy symbol słowa wyjściowego.
2. Wybierz jednolicie losowo jeden z symboli nieterminalnych.
3. Wybierz jednolicie losowo jedną z reguł produkcji dla tego symbolu i zastosuj ją.
4. Powtarzaj kroki 2–4, aż pozostaną tylko symbole zacisków.
5. Zastąp wszystkie symbole terminali Ilosowymi liczbami całkowitymi.

Oto przykład zastosowania tych algorytmów:

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))

Zakładam, że wybrałbyś reprezentację wyrażenia z interfejsem, Expressionktóry jest implementowany przez klasy IntExpression, AddExpressioni MultiplyExpression. Dwa ostatnie miałyby wtedy leftExpressioni rightExpression. Wszystkie Expressionpodklasy są wymagane do wdrożenia evaluatemetody, która działa rekurencyjnie na strukturę drzewa zdefiniowaną przez te obiekty i skutecznie implementuje wzorzec złożony .

Zauważ, że dla powyższej gramatyki i algorytmu prawdopodobieństwo rozwinięcia wyrażenia Ew symbol końcowy Ijest tylko p = 1/3, podczas gdy prawdopodobieństwo rozwinięcia wyrażenia w dwa dalsze wyrażenia wynosi 1-p = 2/3. Dlatego oczekiwana liczba liczb całkowitych we wzorze utworzonym przez powyższy algorytm jest w rzeczywistości nieskończona. Oczekiwana długość wyrażenia zależy od relacji powtarzalności

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

gdzie l(n)oznacza oczekiwaną długość wyrażenia arytmetycznego po nzastosowaniu reguł produkcji. Dlatego sugeruję, aby przypisać pregule raczej wysokie prawdopodobieństwo, aby E -> Iuzyskać dość małe wyrażenie z dużym prawdopodobieństwem.

EDYCJA : Jeśli martwisz się, że powyższa gramatyka powoduje zbyt wiele nawiasów, spójrz na odpowiedź Sebastiana Negraszusa , którego gramatyka bardzo elegancko omija ten problem.

po pierwsze wygenerowałbym wyrażenie w notacji postfiksowej , możesz łatwo przekonwertować na infix lub ocenić po wygenerowaniu losowego wyrażenia, ale robienie tego w postfiksie oznacza, że ​​nie musisz się martwić nawiasami ani pierwszeństwem.

Chciałbym również zachować bieżącą liczbę terminów dostępnych dla następnego operatora w twoim wyrażeniu (zakładając, że chcesz uniknąć generowania wyrażeń, które są zniekształcone), tj. Coś takiego:

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++;
     }
}

oczywiście jest to pseudo kod, więc nie jest testowany / może zawierać błędy i prawdopodobnie nie użyłbyś łańcucha, ale stosu jakiegoś dyskryminowanego związku, takiego jak typ

Odpowiedź Blubba to dobry początek, ale jego formalna gramatyka tworzy zbyt wiele nawiasów.

Oto moje zdanie na ten temat:

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

Ejest wyrażeniem, Iliczbą całkowitą i Mjest wyrażeniem będącym argumentem operacji mnożenia.

Nawiasy w „twardym” wyrażeniu przedstawiają kolejność oceny. Zamiast próbować wygenerować wyświetlaną formę bezpośrednio, po prostu wymyśl listę operatorów w losowej kolejności i na tej podstawie uzyskaj formę wyświetlania wyrażenia.

Liczby: 1 3 3 9 7 2

Operatorzy: + * / + *

Wynik: ((1 + 3) * 3 / 9 + 7) * 2

Wyprowadzenie formy wyświetlania jest stosunkowo prostym algorytmem rekurencyjnym.

Aktualizacja: tutaj jest algorytm w Perlu do generowania formularza wyświetlania. Ponieważ +i *są dystrybuowane, losowo kolejność warunków dla tych operatorów. Pomaga to uniknąć nawiasów tworzących się po jednej stronie.

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";

Aby rozwinąć podejście oparte na drzewie, powiedzmy, że każdy węzeł jest liściem lub wyrażeniem binarnym:

Node := Leaf | Node Operator Node

Zauważ, że liść jest tutaj tylko losowo generowaną liczbą całkowitą.

Teraz możemy losowo wygenerować drzewo. Określenie prawdopodobieństwa, że ​​każdy węzeł jest liściem, pozwala nam kontrolować oczekiwaną głębokość, chociaż możesz również chcieć absolutnej maksymalnej głębokości:

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())

Następnie najprostszą zasadą drukowania drzewa jest owijanie ()każdego wyrażenia nie będącego liściem i unikanie obawy o pierwszeństwo operatora.

Na przykład, jeśli nawiasuję twoje ostatnie przykładowe wyrażenie:

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

możesz odczytać drzewo, które je wygeneruje:

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

Użyłbym drzew. Mogą dać ci wielką kontrolę nad generowaniem wyrażeń. Np. Możesz ograniczyć głębokość na gałąź i szerokość każdego poziomu osobno. Generowanie na podstawie drzewa daje również odpowiedź już podczas generowania, co jest przydatne, jeśli chcesz się upewnić, że również wynik (i wyniki podrzędne) są wystarczająco trudne i / lub niezbyt trudne do rozwiązania. Zwłaszcza jeśli w pewnym momencie dodasz operator dzielenia, możesz wygenerować wyrażenia, które będą miały wartości całkowite.

Oto nieco inne spojrzenie na doskonałą odpowiedź Blubba:

To, co próbujesz zbudować tutaj, to zasadniczo parser działający w odwrotnej kolejności. To, co łączy Twój problem i parser , to gramatyka bezkontekstowa , ta w formie Backus-Naur :

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

Parsery zaczynają się od strumienia terminali (dosłowne tokeny, takie jak 5lub *) i próbują złożyć je w nieterminale (rzeczy złożone z terminali i innych nieterminali, takich jak numberlub op). Twój problem zaczyna się od nieterminali i działa w odwrotnej kolejności, wybierając losowo dowolne symbole „lub” (potok), gdy się je napotyka, i powtarzając cyklicznie proces aż do osiągnięcia terminalu.

Kilka innych odpowiedzi sugeruje, że jest to problem drzewa, co dotyczy pewnej wąskiej klasy przypadków, w których nie ma nieterminali, które odwołują się bezpośrednio lub pośrednio przez inny nieterminal. Ponieważ pozwalają na to gramatyki, ten problem jest tak naprawdę grafem ukierunkowanym . (Pośrednie odniesienia również do innych nieterminali również się liczą.)

Pod koniec lat 80. na Usenecie opublikowano program o nazwie Spew, który pierwotnie miał na celu generowanie losowych nagłówków tabloidów, a także okazał się świetnym narzędziem do eksperymentowania z tymi „gramatykami wstecznymi”. Działa poprzez odczyt szablonu, który kieruje wytwarzaniem losowego strumienia terminali. Oprócz wartości rozrywkowej (nagłówki, piosenki country, wymowny angielski bełkot) napisałem wiele szablonów, które są przydatne do generowania danych testowych, od zwykłego tekstu po XML, do syntaktycznie poprawnego, ale nie dającego się skompilować C. Pomimo tego, że ma 26 lat i napisany w K&R C, z brzydkim formatem szablonu, kompiluje się dobrze i działa jak w reklamie. Podniosłem szablon, który rozwiązuje twój problem i opublikowałem go na pastebin ponieważ dodanie takiej ilości tekstu tutaj nie wydaje się właściwe.