Generierung eines zufälligen mathematischen Ausdrucks

Ich habe die Idee, zufällige mathematische Ausdrücke zu generieren und auszuwerten. Also habe ich beschlossen, es auszuprobieren und einen Algorithmus auszuarbeiten, bevor ich ihn zum Testen codiere.

Beispiel:

Hier sind einige Beispielausdrücke, die ich zufällig generieren möchte:

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]

Die einfachen und mittleren sind ziemlich direkt. Zufällige ints durch zufällige Operatoren getrennt, hier nichts verrücktes. Aber ich habe einige Probleme mit etwas Sie beginnen , die eine der schaffen könnte hart und härter Beispiele. Ich bin mir nicht mal sicher, ob ein einziger Algorithmus mir die letzten beiden geben könnte.

Was ich überlege:

Ich kann nicht sagen, dass ich diese Ideen ausprobiert habe , weil ich nicht wirklich viel Zeit damit verschwenden wollte, in eine Richtung zu gehen, in der es überhaupt keine Chance gab, zu arbeiten. Trotzdem habe ich mir ein paar Lösungen überlegt:

• Bäume benutzen
• Reguläre Ausdrücke verwenden
• Verwenden einer verrückten "for-type" -Schleife (sicherlich die schlechteste)

Was ich suche:

Ich würde gerne wissen, welcher Weg Ihrer Meinung nach der beste ist, zwischen den von mir in Betracht gezogenen Lösungen und Ihren eigenen Ideen.

Wenn Sie einen guten Einstieg sehen, würde ich mich über einen Hinweis in die richtige Richtung freuen, z. B. mit dem Beginn des Algorithmus oder dessen allgemeiner Struktur.

Beachten Sie auch, dass ich diese Ausdrücke auswerten muss. Dies kann entweder nach der Generierung des Ausdrucks oder während seiner Erstellung erfolgen. Wenn Sie das in Ihrer Antwort berücksichtigen, ist das großartig.

Ich bin nicht auf der Suche nach sprachbezogenen Inhalten, aber für die Aufzeichnung denke ich darüber nach, sie in Objective-C zu implementieren, da dies die Sprache ist, mit der ich in letzter Zeit am meisten arbeite.

In diesen Beispielen war der :Operator nicht enthalten , da ich nur ints manipulieren möchte , und dieser Operator fügt viele Überprüfungen hinzu. Wenn Ihre Antwort eine Lösung für diese Frage liefert, ist das großartig.

Wenn meine Frage einer Klärung bedarf, bitte in den Kommentaren nachfragen. Danke für Ihre Hilfe.

Hier ist eine theoretische Interpretation Ihres Problems.

Sie möchten Wörter (algebraische Ausdrücke) aus einer bestimmten Sprache (der unendlichen Menge aller syntaktisch korrekten algebraischen Ausdrücke) zufällig generieren . Hier ist eine formale Beschreibung einer vereinfachten algebraischen Grammatik, die nur Addition und Multiplikation unterstützt:

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

Hierbei Ehandelt es sich um einen Ausdruck (dh ein Wort Ihrer Sprache) und Ium ein Endsymbol (dh es wird nicht weiter erweitert), das eine Ganzzahl darstellt. Die obige Definition für Ehat drei Produktionsregeln . Basierend auf dieser Definition können wir eine gültige Arithmetik wie folgt zufällig erstellen:

1. Beginnen Sie mit Eals einzelnes Symbol des Ausgangsworts.
2. Wählen Sie eines der nicht terminalen Symbole gleichmäßig nach dem Zufallsprinzip aus.
3. Wählen Sie eine der Produktionsregeln für dieses Symbol nach dem Zufallsprinzip aus und wenden Sie sie an.
4. Wiederholen Sie die Schritte 2 bis 4, bis nur noch Terminalsymbole übrig sind.
5. Ersetzen Sie alle Terminalsymbole Idurch zufällige ganze Zahlen.

Hier ist ein Beispiel für die Anwendung dieser Algorithmen:

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

Ich nehme an, Sie würden einen Ausdruck mit einer Schnittstelle darstellen, Expressiondie von Klassen implementiert wird IntExpression, AddExpressionund MultiplyExpression. Die beiden letzteren hätten dann ein leftExpressionund rightExpression. Alle ExpressionUnterklassen müssen eine evaluateMethode implementieren , die die durch diese Objekte definierte Baumstruktur rekursiv bearbeitet und das zusammengesetzte Muster effektiv implementiert .

Es ist zu beachten, dass für die obige Grammatik und den obigen Algorithmus die Wahrscheinlichkeit, einen Ausdruck Ein ein Endsymbol zu erweitern, Inur ist p = 1/3, während die Wahrscheinlichkeit, einen Ausdruck in zwei weitere Ausdrücke zu erweitern, gleich ist 1-p = 2/3. Daher ist die erwartete Anzahl von Ganzzahlen in einer Formel, die durch den obigen Algorithmus erzeugt wird, tatsächlich unendlich. Die erwartete Länge eines Ausdrucks hängt von der Wiederholungsrelation ab

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

wo l(n)bezeichnet die erwartete Länge des arithmetischen Ausdrucks nach nAnwendungen der Produktionsregeln. Ich schlage daher vor, dass Sie pder Regel eine ziemlich hohe Wahrscheinlichkeit zuweisen, E -> Isodass Sie einen ziemlich kleinen Ausdruck mit hoher Wahrscheinlichkeit erhalten.

EDIT : Wenn Sie befürchten, dass die obige Grammatik zu viele Klammern erzeugt, lesen Sie die Antwort von Sebastian Negraszus , dessen Grammatik dieses Problem auf elegante Weise umgeht.

Zunächst einmal würde ich den Ausdruck in der Postfix-Notation generieren. Sie können ihn nach dem Generieren Ihres zufälligen Ausdrucks problemlos in ein Infix konvertieren oder auswerten. Wenn Sie dies jedoch in der Postfix-Notation tun, müssen Sie sich keine Gedanken über Klammern oder Vorrang machen.

Außerdem würde ich die Anzahl der Begriffe, die dem nächsten Operator in Ihrem Ausdruck zur Verfügung stehen (vorausgesetzt, Sie möchten vermeiden, fehlerhafte Ausdrücke zu generieren), dh in etwa wie folgt zusammenfassen:

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

Dies ist offensichtlich Pseudocode, wird also nicht getestet / enthält möglicherweise Fehler, und Sie würden wahrscheinlich keine Zeichenfolge verwenden, sondern einen Stapel eines diskriminierten union-ähnlichen Typs

Die Antwort von blubb ist ein guter Anfang, aber seine formale Grammatik schafft zu viele Klammern.

Hier ist meine Meinung dazu:

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

Eist ein Ausdruck, Ieine Ganzzahl und Mein Ausdruck, der ein Argument für eine Multiplikationsoperation ist.

Die Klammern im "harten" Ausdruck geben die Reihenfolge der Bewertung an. Anstatt zu versuchen, das angezeigte Formular direkt zu generieren, erstellen Sie einfach eine Liste von Operatoren in zufälliger Reihenfolge und leiten die Anzeigeform des Ausdrucks daraus ab.

Zahlen: 1 3 3 9 7 2

Betreiber: + * / + *

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

Das Ableiten der Anzeigeform ist ein relativ einfacher rekursiver Algorithmus.

Update: Hier ist ein Algorithmus in Perl, um das Anzeigeformular zu generieren. Da +und *distributive sind, randomisiert es die Reihenfolge der Bedingungen für die Betreiber. Dies verhindert, dass sich die Klammern auf einer Seite aufbauen.

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

Nehmen wir zum Erweitern des Baumansatzes an, dass jeder Knoten entweder ein Blatt oder ein binärer Ausdruck ist:

Node := Leaf | Node Operator Node

Beachten Sie, dass ein Blatt hier nur eine zufällig generierte Ganzzahl ist.

Jetzt können wir zufällig einen Baum erzeugen. Wenn Sie die Wahrscheinlichkeit bestimmen, dass jeder Knoten ein Blatt ist, können Sie die erwartete Tiefe steuern. Möglicherweise möchten Sie jedoch auch eine absolute maximale Tiefe:

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

Die einfachste Regel für das Drucken des Baums besteht darin, ()jeden Nicht-Blatt-Ausdruck zu umbrechen und sich nicht um die Priorität des Operators zu sorgen.

Zum Beispiel, wenn ich Ihren letzten Beispielausdruck in Klammern setze:

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

Sie können den Baum ablesen, der ihn erzeugen würde:

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

Ich würde Bäume benutzen. Sie können Ihnen eine gute Kontrolle über die Erzeugung der Ausdrücke geben. Sie können z. B. die Tiefe pro Zweig und Breite jeder Ebene separat begrenzen. Die baumbasierte Generierung gibt bereits während der Generierung die Antwort. Dies ist hilfreich, wenn Sie sicherstellen möchten, dass auch das Ergebnis (und die Unterergebnisse) schwer genug und / oder nicht zu schwer zu lösen sind. Insbesondere wenn Sie irgendwann einen Divisionsoperator hinzufügen, können Sie Ausdrücke generieren, die ganze Zahlen ergeben.

Hier ist eine etwas andere Einstellung zu Blubbs hervorragender Antwort:

Was Sie hier erstellen möchten, ist im Wesentlichen ein Parser, der umgekehrt arbeitet. Was Ihrem Problem und einem Parser gemeinsam ist, ist eine kontextfreie Grammatik , diese 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> ')'

Parser beginnen mit einem Stream von Terminals (wörtliche Token wie 5oder *) und versuchen, sie zu Nicht-Terminals zusammenzusetzen (Dinge, die aus Terminals und anderen Nicht-Terminals wie numberoder bestehen op). Ihr Problem beginnt mit Nicht-Endgeräten und funktioniert in umgekehrter Reihenfolge. Wählen Sie bei Auftreten eines Problems nach dem Zufallsprinzip zwischen den Symbolen "oder" (Pipe) und wiederholen Sie den Vorgang rekursiv, bis Sie ein Terminal erreichen.

Einige andere Antworten haben darauf hingewiesen, dass dies ein Baumproblem ist, und zwar für eine bestimmte enge Klasse von Fällen, in denen es keine Nichtterminale gibt, die sich direkt oder indirekt über ein anderes Nichtterminale beziehen. Da Grammatiken dies zulassen, handelt es sich bei diesem Problem in Wirklichkeit um einen gerichteten Graphen . (Indirekte Verweise durch andere Nichtterminale zählen auch dazu.)

Es gab ein Programm namens Spew, das Ende der 1980er Jahre im Usenet veröffentlicht wurde und ursprünglich dazu gedacht war, zufällige Boulevard-Schlagzeilen zu generieren. Es war auch ein großartiges Mittel, um mit diesen "umgekehrten Grammatiken" zu experimentieren. Es funktioniert durch Lesen einer Vorlage, die die Produktion eines zufälligen Datenstroms von Terminals steuert. Abgesehen von seinem Vergnügungswert (Schlagzeilen, Country-Songs, aussprechbares Englisch-Kauderwelsch) habe ich zahlreiche Vorlagen geschrieben, mit denen sich Testdaten generieren lassen, die von Klartext über XML bis hin zu syntaktisch korrektem, aber nicht kompilierbarem C reichen. Trotzdem ich 26 Jahre alt bin und in K & R C geschrieben und mit einem hässlichen Vorlagenformat, kompiliert es ganz gut und funktioniert wie beworben. Ich habe eine Vorlage erstellt, die Ihr Problem löst, und sie im Pastebin veröffentlicht da das Hinzufügen von so viel Text hier nicht angemessen erscheint.