Generazione di espressioni matematiche casuali

Ecco un'interpretazione teorica del tuo problema.

Stai cercando di generare casualmente parole (espressione algebrica) da un determinato linguaggio (l'insieme infinito di tutte le espressioni algebriche sintatticamente corrette). Ecco una descrizione formale di una grammatica algebrica semplificata che supporta solo l'aggiunta e la moltiplicazione:

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

Qui, E è un'espressione (cioè una parola della tua lingua) e I è un simbolo del terminale (cioè, non è espanso ulteriormente) che rappresenta un numero intero. La precedente definizione di E ha tre regole di produzione . In base a questa definizione, possiamo costruire casualmente un'aritmetica valida come segue:

1. Inizia con E come singolo simbolo della parola in uscita.
2. Scegli in modo uniforme a caso uno dei simboli non terminali.
3. Scegli uniformemente a caso una delle regole di produzione per quel simbolo e applicala.
4. Ripeti i passaggi 2 - 4 finché non rimangono solo i simboli dei terminali.
5. Sostituisci tutti i simboli del terminale I con numeri casuali.

Ecco un esempio dell'applicazione di questo algoritmo:

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

Suppongo che tu sceglieresti di rappresentare un'espressione con un'interfaccia Expression implementata dalle classi IntExpression , AddExpression e MultiplyExpression . Gli ultimi due avrebbero quindi un leftExpression e rightExpression . Sono richieste tutte le sottoclassi Expression per implementare un metodo evaluate , che funziona in modo ricorsivo sulla struttura ad albero definita da questi oggetti e implementa efficacemente modello composito .

Si noti che per la grammatica e l'algoritmo di cui sopra, la probabilità di espandere un'espressione E in un simbolo terminale I è solo p = 1/3 , mentre la probabilità di espandere un'espressione in altre due espressioni è 1-p = 2/3 . Pertanto, il numero previsto di numeri interi in una formula prodotta dall'algoritmo di cui sopra è in realtà infinito. La durata prevista di un'espressione è soggetta alla relazione di ricorrenza

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

dove l(n) indica la lunghezza prevista dell'espressione aritmetica dopo n delle applicazioni delle regole di produzione. Pertanto ti suggerisco di assegnare una percentuale piuttosto elevata di p alla regola E -> I tale che ti ritroverai con un'espressione abbastanza piccola con alta probabilità.

EDIT : se sei preoccupato che la grammatica sopra riportata produca troppe parentesi, consulta La risposta di Sebastian Negraszus , la cui grammatica evita questo problema in modo molto elegante.

prima di tutto avrei effettivamente generato l'espressione nella notazione postfix , puoi facilmente convertire in infisso o valutare dopo generare la tua espressione casuale, ma farlo in postfix significa che non devi preoccuparti della parentesi o della precedenza.

Conserverei anche un totale parziale del numero di termini disponibili per l'operatore successivo nell'espressione (supponendo che tu voglia evitare di generare espressioni che sono malformate), ad esempio qualcosa del genere:

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

ovviamente questo è pseudo codice quindi non è testato / potrebbe contenere errori e probabilmente non useresti una stringa ma una pila di un tipo di unione discriminato come

La risposta del blubb è un buon inizio, ma la sua grammatica formale crea troppe paraste.

Ecco la mia opinione su questo:

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

E è un'espressione, I un numero intero e M è un'espressione che è un argomento per un'operazione di moltiplicazione.

Le parentesi nell'espressione "hard" rappresentano l'ordine di valutazione. Piuttosto che provare a generare direttamente il modulo visualizzato, basta creare un elenco di operatori in ordine casuale e ricavare il formato di visualizzazione dell'espressione da quello.

Numeri: 1 3 3 9 7 2

Operatori: + * / + *

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

La derivazione del modulo di visualizzazione è un algoritmo ricorsivo relativamente semplice.

Aggiornamento: ecco un algoritmo in Perl per generare il modulo di visualizzazione. Poiché + e * sono distributivi, randomizza l'ordine dei termini per tali operatori. Ciò aiuta a mantenere le parentesi da tutte le parti su un lato.

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

Per espandere l'approccio ad albero, diciamo che ogni nodo è una foglia o un'espressione binaria:

Node := Leaf | Node Operator Node

Nota che una foglia è solo un intero generato casualmente qui.

Ora, possiamo generare a caso un albero. Decidere la probabilità che ogni nodo sia una foglia ci consente di controllare la profondità prevista, sebbene tu possa volere anche una profondità massima assoluta:

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

Quindi, la regola più semplice per la stampa dell'albero è di avvolgere () attorno ad ogni espressione non fogliare ed evitare di preoccuparsi della precedenza degli operatori.

Ad esempio, se metto in parentesi la tua ultima espressione di esempio:

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

puoi leggere l'albero che lo genererebbe:

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

Userei gli alberi. Possono darti un grande controllo sulla generazione delle espressioni. Per esempio. puoi limitare separatamente la profondità per ramo e la larghezza di ogni livello. La generazione ad albero fornisce anche la risposta già durante la generazione, il che è utile se si vuole assicurare che anche il risultato (e il sottoscribuzione) siano abbastanza difficili e / o non troppo difficili da risolvere. Soprattutto se aggiungi un operatore di divisione a un certo punto, puoi generare espressioni che valutano a numeri interi.

Ecco una presa leggermente diversa sull'eccellente risposta di Blubb:

Quello che stai cercando di costruire qui è essenzialmente un parser che opera al contrario. Ciò che il tuo problema e un parser hanno in comune è una grammatica senza contesto , questa in Backus-Naur form :

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

I parser iniziano con un flusso di terminali (token letterali come 5 o * ) e cercano di assemblarli in non-terminali (cose composte da terminali e altri non terminali, come number o op ). Il tuo problema inizia con nonminerminali e funziona in senso inverso, scegliendo qualsiasi cosa tra i simboli "o" (pipe) in modo casuale quando ne viene rilevato uno e ripetendo ricorsivamente il processo fino a raggiungere un terminale.

Un paio di altre risposte hanno suggerito che si tratta di un problema ad albero, che è per una certa classe ristretta di casi in cui non ci sono non terminali che si riferiscono direttamente o indirettamente attraverso un altro non terminale. Dal momento che le grammatiche lo consentono, questo problema è in realtà un grafico diretto . (Anche i riferimenti indiretti attraverso altri non terminali contano per questo.)

C'era un programma chiamato Spew pubblicato su Usenet nel tardo pomeriggio Anni '80 che originariamente era stato progettato per generare titoli scandalistici casuali ed è anche un ottimo veicolo per sperimentare queste "grammatiche inverse". Funziona leggendo un modello che indirizza la produzione di un flusso casuale di terminali. Al di là del suo valore di divertimento (titoli, canzoni country, pronuncia inglese senza senso), ho scritto numerosi modelli utili per generare dati di test che vanno dal semplice testo all'XML fino alla sintassi corretta, ma non compattabile. Nonostante abbia 26 anni e scritto in K & RC e con un brutto formato di modello, si compila bene e funziona come pubblicizzato. Ho montato un modello che risolve il problema e lo ha pubblicato su pastebin , poiché l'aggiunta di tale testo qui non sembra appropriata.