Meminimalkan pernyataan matematika

18

Tantangan

Anda adalah pemilik layanan luar biasa yang disebut Coyote Beta , yang secara ajaib menjawab pertanyaan matematika yang dikirimkan penggunanya melalui internet.

Tapi ternyata, bandwidth itu mahal. Anda memiliki dua pilihan, baik membuat " Coyote Beta Pro" atau menemukan beberapa cara untuk menyelesaikannya. Baru-baru ini, seseorang bertanya (x + 2). Tidak bisakah klien mengirim x+2, dan pengguna tidak akan melihat perbedaan?

Tugas

Tugas Anda adalah untuk "mengurangi" ekspresi matematika. Diberikan ekspresi input, Anda harus menyingkirkan spasi dan tanda kurung sampai memberikan representasi minimal dari input yang sama. Tanda kurung di sekitar operasi asosiatif tidak perlu dipertahankan.

Satu-satunya operator yang diberikan di sini +, -, *, /, dan ^(eksponensial), dengan standar associativity matematika dan diutamakan. Satu-satunya spasi putih yang diberikan dalam input adalah karakter spasi aktual.

Contoh Input / Output

Input       | Output
------------|--------------
(2+x) + 3   | 2+x+3
((4+5))*x   | (4+5)*x
z^(x+42)    | z^(x+42)
x - ((y)+2) | x-(y+2)
(z - y) - x | z-y-x
x^(y^2)     | x^y^2
x^2 / z     | x^2/z
- (x + 5)+3 | -(x+5)+3

Mencetak gol

Input / output dapat menggunakan metode yang disukai. Program terkecil dalam byte menang.

Bit yang tepat

Eksponensial adalah asosiatif yang benar dan juga mengikuti presedensi matematika standar (menjadi yang tertinggi). Literal numerik yang valid adalah /[0-9]+/, dan literal variabel yang valid adalah /[a-z]+/. Literal variabel tunggal mewakili nilai tunggal bahkan ketika panjang karakternya lebih panjang dari 1.

Apa yang dimaksud dengan "tanda kurung di sekitar operasi asosiatif tidak perlu dipertahankan" adalah bahwa output harus terdiri dari ekspresi yang menghasilkan pohon parse yang identik, dengan pengecualian bahwa operasi asosiatif dapat disusun ulang.

TND
sumber
Idenya adalah untuk membuat pernyataan ekivalen minimal yang menghasilkan pohon parse yang sama. Ini agar Coyote Beta dapat menampilkannya secara visual saat pengguna membuat kueri.
TND
Jika variabel yang valid adalah /[a-z]+/, itu berarti perkalian dengan penjajaran seperti abtidak diizinkan?
Joe Z.
1
Anda memang ingin 2+(3+4)diubah 2+3+4, bukan? Ini mengubah pohon parse.
feersum
2
Saya mempermasalahkan klaim itu x^(y/2)=x^y/2; eksponensial memiliki prioritas lebih tinggi, ergo x^y/2=(x^y)/2,.
Conor O'Brien
1
Aww man, saya akan mengirimkan Prompt X:expr(X)TI-BASIC tetapi Anda tidak dapat menyederhanakan :(
DankMemes

Jawaban:

1

C #, 523 519 504 byte

Periksa komentar dalam kode untuk melihat cara kerjanya!


Golf

using System;using System.Collections.Generic;namespace n{class p{static void Main(string[]a){foreach(String s in a){String r=s.Replace(" ","");List<int>l=new List<int>();for(int i=0;i<r.Length;i++){if(r[i]=='('){l.Add(i);continue;}if(r[i]==')'){switch(r[Math.Max(l[l.Count-1]-1,0)]){case'+':case'(':switch(r[Math.Min(i+1,r.Length-1)]){case'+':case'-':case')':r=r.Remove(Math.Max(l[l.Count-1],0),1);r=r.Remove(Math.Min(i,r.Length)-1,1);i-=2;break;}break;}l.RemoveAt(l.Count-1);}}Console.WriteLine(r);}}}}

Tidak disatukan

using System;
using System.Collections.Generic;

namespace n {
    class p {
        static void Main( string[] a ) {
            // Loop every String given for the program
            foreach (String s in a) {
                // Get rid of the spaces
                String r = s.Replace( " ", "" );

                // A little helper that will have the indexes of the '('
                List<int> l = new List<int>();

                // Begin the optimizatio process
                for (int i = 0; i < r.Length; i++) {
                    // If char is an '(', add the index to the helper list and continue
                    if (r[ i ] == '(') {
                        l.Add( i );
                        continue;
                    }

                    // If the char is an ')', validate the group
                    if (r[ i ] == ')') {
                        // If the char before the last '(' is an '+' or '(' ...
                        switch (r[ Math.Max( l[ l.Count - 1 ] - 1, 0 ) ]) {
                            case '+':
                            case '(':
                                // ... and the char after the ')' we're checking now is an '+', '-' or ')' ...
                                switch (r[ Math.Min( i + 1, r.Length - 1 ) ]) {
                                    case '+':
                                    case '-':
                                    case ')':
                                        // Remove the '()' since they're most likely desnecessary.
                                        r = r.Remove( Math.Max( l[ l.Count - 1 ], 0 ), 1 );
                                        r = r.Remove( Math.Min( i, r.Length ) - 1, 1 );

                                        // Go two steps back in the loop since we removed 2 chars from the String,
                                        //   otherwise we would miss some invalid inputs
                                        i -= 2;
                                        break;
                                }

                                break;
                        }

                        // Remove the last inserted index of '(' from the list,
                        //   since we matched an ')' for it.
                        l.RemoveAt( l.Count - 1 );
                    }
                }

                // Print the result
                Console.WriteLine( r );
            }
        }
    }
}

Catatan samping

  1. Memperbaiki beberapa kesalahan ketik dan mengganti nama beberapa vars.
  2. Nested switch untuk menyingkirkan variabel yang tidak perlu. Juga, perbaiki bug yang akan membuat beberapa solusi tidak valid, dilaporkan oleh Anders Kaseorg .

PS: Jika Anda memiliki tip atau menemukan bug, beri tahu saya di komentar dan saya akan mencoba memperbaikinya (Saya kemudian akan menambahkan catatan tentang perbaikan bug dengan nama Anda;))

auhmaan
sumber
Jawaban bagus! : D jawaban substansial di sini umumnya lebih baik diterima jika Anda memasukkan penjelasan: P
cat
Bisakah saya melakukannya dalam bentuk komentar kode?
auhmaan
Tentu, apa pun yang berhasil c:
cat
Maka saya akan melakukannya! Saya juga akan mencoba menambahkan ringkasan di suatu tempat.
auhmaan
Selamat datang di Programming Puzzles and Code Golf! (meskipun itu bukan jawaban pertama Anda)
kucing
0

C ++, 284 byte

Golf

#include<iostream>
#include<algorithm>
int main(){std::string e;std::getline(std::cin,e);e.erase(std::remove_if(e.begin(),e.end(),isspace),e.end());for(int x=0;x<e.length();x++){if(e[x]=='('&&e[x+1]=='('){e.erase(x,1);}if(e[x]==')'&&e[x+1]==')'){e.erase(x,1);}}std::cout<<e;return 0;}

Tidak disatukan

#include<iostream>
#include<algorithm>

int main()
{
    std::string e;
    std::getline(std::cin, e);
    e.erase(std::remove_if(e.begin(), e.end(), isspace), e.end());
    for(int x = 0; x < e.length(); x++) {
        if (e[x] == '(' && e[x+1] == '('){
            e.erase(x, 1);
        }
        if (e[x] == ')' && e[x+1] == ')'){
            e.erase(x, 1);
        }
    }
    std::cout<<e;
    return 0;
}
Michelfrancis Bustillos
sumber
Ini tidak memiliki logika prioritas dan gagal banyak kasus uji yang diberikan.
Anders Kaseorg