Menghasilkan ekspresi matematika acak

Saya memiliki ide ini berkeliaran di kepala saya, untuk menghasilkan dan mengevaluasi ekspresi matematika acak. Jadi, saya memutuskan untuk mencobanya dan menguraikan algoritma, sebelum mengkodekannya untuk mengujinya.

Contoh:

Berikut adalah beberapa contoh ekspresi yang ingin saya hasilkan secara acak:

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]

Yang mudah dan sedang cukup mudah. Acak intdipisahkan oleh operator acak, tidak ada yang gila di sini. Tapi aku mengalami beberapa masalah memulai dengan sesuatu yang bisa membuat salah satu keras dan lebih keras contoh. Saya bahkan tidak yakin algoritma tunggal dapat memberi saya dua yang terakhir.

Apa yang saya pertimbangkan:

Saya tidak bisa mengatakan saya mencoba ide-ide itu, karena saya tidak benar-benar ingin membuang banyak waktu untuk pergi ke arah yang tidak memiliki kesempatan untuk bekerja di tempat pertama. Tapi tetap saja, saya memikirkan beberapa solusi:

• Menggunakan pohon
• Menggunakan ekspresi reguler
• Menggunakan loop "for-type" yang gila (pasti yang terburuk)

Apa yang saya cari:

Saya ingin tahu ke arah mana Anda percaya yang terbaik, antara solusi yang saya pertimbangkan, dan ide-ide Anda sendiri.

Jika Anda melihat cara yang baik untuk memulai, saya akan menghargai petunjuk di arah yang benar, misalnya dengan awal algoritma, atau struktur umum dari itu.

Perhatikan juga bahwa saya harus mengevaluasi ekspresi itu. Ini dapat dilakukan baik setelah ekspresi dihasilkan, atau selama pembuatannya. Jika Anda mempertimbangkannya dalam jawaban Anda, itu bagus.

Saya tidak mencari apa pun yang berhubungan dengan bahasa, tetapi sebagai catatan, saya berpikir untuk mengimplementasikannya di Objective-C, karena itulah bahasa yang paling saya gunakan saat ini.

Contoh-contoh itu tidak termasuk :operator, karena saya hanya ingin memanipulasi int, dan operator ini menambahkan banyak verifikasi. Jika jawaban Anda memberikan solusi menangani yang ini, itu bagus.

Jika pertanyaan saya membutuhkan klarifikasi, silakan tanyakan di komentar. Terima kasih atas bantuan Anda.

Berikut ini adalah interpretasi teoretis dari masalah Anda.

Anda mencari untuk menghasilkan kata-kata secara acak (ekspresi aljabar) dari bahasa tertentu (rangkaian tak terbatas dari semua ekspresi aljabar yang benar secara sintaksis). Berikut adalah deskripsi formal tata bahasa aljabar sederhana yang hanya mendukung penambahan dan perkalian:

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

Di sini, Eadalah ekspresi (yaitu, kata dari bahasa Anda) dan Imerupakan simbol terminal (yaitu, itu tidak diperluas lebih jauh) yang mewakili integer. Definisi di atas untuk Ememiliki tiga aturan produksi . Berdasarkan definisi ini, kita dapat secara acak membangun aritmatika yang valid sebagai berikut:

1. Mulai dengan Esebagai simbol tunggal dari kata keluaran.
2. Pilih seragam secara acak salah satu simbol non-terminal.
3. Pilih secara acak salah satu aturan produksi untuk simbol itu, dan terapkan.
4. Ulangi langkah 2 - 4 sampai hanya simbol terminal yang tersisa.
5. Ganti semua simbol terminal Idengan bilangan bulat acak.

Berikut ini contoh penerapan algoritma ini:

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

Saya berasumsi Anda akan memilih untuk mewakili ekspresi dengan antarmuka Expressionyang diimplementasikan oleh kelas IntExpression, AddExpressiondan MultiplyExpression. Dua yang terakhir kemudian akan memiliki leftExpressiondan rightExpression. Semua Expressionsubclass diharuskan untuk mengimplementasikan suatu evaluatemetode, yang bekerja secara rekursif pada struktur pohon yang ditentukan oleh objek-objek ini dan secara efektif mengimplementasikan pola komposit .

Perhatikan bahwa untuk tata bahasa dan algoritma di atas, probabilitas memperluas ekspresi Eke simbol terminal Ihanya p = 1/3, sedangkan probabilitas untuk memperluas ekspresi menjadi dua ekspresi lebih lanjut adalah 1-p = 2/3. Oleh karena itu, jumlah bilangan bulat yang diharapkan dalam rumus yang dihasilkan oleh algoritma di atas sebenarnya tidak terbatas. Panjang yang diharapkan dari suatu ekspresi tunduk pada relasi yang berulang

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

di mana l(n)menunjukkan panjang yang diharapkan dari ekspresi aritmatika setelah npenerapan aturan produksi. Karena itu saya menyarankan agar Anda menetapkan probabilitas yang agak tinggi puntuk aturan E -> Isehingga Anda berakhir dengan ekspresi yang cukup kecil dengan probabilitas tinggi.

EDIT : Jika Anda khawatir bahwa tata bahasa di atas menghasilkan terlalu banyak tanda kurung, lihat jawaban Sebastian Negraszus , yang tata bahasanya menghindari masalah ini dengan sangat elegan.

pertama-tama saya benar-benar menghasilkan ekspresi dalam notasi postfix , Anda dapat dengan mudah mengkonversi ke infix atau mengevaluasi setelah menghasilkan ekspresi acak Anda, tetapi melakukannya dalam postfix berarti Anda tidak perlu khawatir tentang tanda kurung atau prioritas.

Saya juga akan terus menjalankan total jumlah istilah yang tersedia untuk operator berikutnya dalam ekspresi Anda (dengan asumsi Anda ingin menghindari menghasilkan ekspresi yang cacat) yaitu sesuatu seperti ini:

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

jelas ini adalah kode semu sehingga tidak diuji / mungkin mengandung kesalahan dan Anda mungkin tidak akan menggunakan string tetapi tumpukan beberapa jenis serikat seperti

jawaban blubb adalah awal yang baik, tetapi tata bahasa formalnya menciptakan terlalu banyak paranthes.

Inilah pendapat saya:

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

Eadalah ekspresi, Iinteger dan Mekspresi yang merupakan argumen untuk operasi multiplikasi.

Tanda kurung dalam ekspresi "keras" mewakili urutan evaluasi. Alih-alih mencoba membuat formulir yang ditampilkan secara langsung, buat saja daftar operator dalam urutan acak, dan turunkan bentuk tampilan dari ekspresi itu.

Angka: 1 3 3 9 7 2

Operator: + * / + *

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

Turunkan bentuk tampilan adalah algoritma rekursif yang relatif sederhana.

Pembaruan: di sini adalah algoritma di Perl untuk menghasilkan formulir tampilan. Karena +dan *bersifat distributif, itu mengacak urutan ketentuan untuk operator tersebut. Itu membantu menjaga tanda kurung dari semua membangun di satu sisi.

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

Untuk memperluas pendekatan pohon, katakanlah setiap node adalah daun atau ekspresi biner:

Node := Leaf | Node Operator Node

Perhatikan bahwa daun hanyalah bilangan bulat yang dihasilkan secara acak di sini.

Sekarang, kita dapat menghasilkan pohon secara acak. Menentukan probabilitas setiap node menjadi daun memungkinkan kami untuk mengontrol kedalaman yang diharapkan, meskipun Anda mungkin menginginkan kedalaman maks absolut juga:

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

Kemudian, aturan paling sederhana untuk mencetak pohon adalah membungkus ()setiap ekspresi non-daun dan menghindari kekhawatiran tentang prioritas operator.

Misalnya, jika saya mengurung ekspresi sampel terakhir Anda:

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

Anda dapat membaca dari pohon yang akan menghasilkannya:

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

Saya akan menggunakan pohon. Mereka dapat memberi Anda kendali besar pada generasi ekspresi. Misalnya, Anda dapat membatasi kedalaman per cabang dan lebar setiap tingkat secara terpisah. Generasi berbasis pohon juga sudah memberikan jawaban selama generasi, yang berguna jika Anda ingin memastikan bahwa juga hasilnya (dan sub-hasil) cukup sulit dan / atau tidak terlalu sulit untuk dipecahkan. Terutama jika Anda menambahkan operator divisi di beberapa titik, Anda dapat menghasilkan ekspresi yang mengevaluasi ke bilangan bulat.

Inilah pendapat yang sedikit berbeda dari jawaban Blubb yang sangat baik:

Apa yang Anda coba bangun di sini pada dasarnya adalah parser yang beroperasi secara terbalik. Kesamaan yang dimiliki masalah dan pengurai adalah tata bahasa bebas konteks , yang ini dalam bentuk 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> ')'

Parser mulai dengan aliran terminal (token literal suka 5atau *) dan mencoba untuk merakitnya menjadi nonterminals (hal-hal yang terdiri dari terminal dan nonterminals lainnya, seperti numberatau op). Masalah Anda dimulai dengan nonterminals dan bekerja secara terbalik, memilih apa pun di antara simbol "atau" (pipa) secara acak ketika seseorang ditemui dan mengulangi proses secara berulang sampai mencapai terminal.

Beberapa jawaban lain menyatakan bahwa ini adalah masalah pohon, yaitu untuk kelas kasus tertentu yang sempit dimana tidak ada nonterminal yang merujuk diri secara langsung atau tidak langsung melalui nonterminal lain. Karena tata bahasa mengizinkannya, masalah ini benar-benar grafik terarah . (Referensi tidak langsung melalui nonterminals lain juga diperhitungkan.)

Ada sebuah program bernama Spew yang diterbitkan di Usenet pada akhir 1980-an yang pada awalnya dirancang untuk menghasilkan tajuk berita tabloid acak dan juga merupakan sarana yang hebat untuk bereksperimen dengan "tata bahasa terbalik" ini. Ini beroperasi dengan membaca templat yang mengarahkan produksi aliran acak terminal. Di luar nilai hiburannya (tajuk utama, lagu country, omong kosong bahasa Inggris yang dapat diucapkan), saya telah menulis banyak templat yang berguna untuk menghasilkan data uji yang berkisar dari teks biasa ke XML hingga C. secara sintaksis benar-benar-tetapi-tidak dapat dikompilasi. Meskipun berusia 26 tahun dan ditulis dalam K&R C dan memiliki format template yang jelek, itu mengkompilasi dengan baik dan berfungsi seperti yang diiklankan. Saya membuat templat yang memecahkan masalah Anda dan mempostingnya di pastebin karena menambahkan banyak teks di sini sepertinya tidak tepat.