Minimalizowanie instrukcji matematycznych

18

Wyzwanie

Jesteś właścicielem niesamowitej usługi o nazwie Coyote Beta , która w magiczny sposób odpowiada na pytania matematyczne wysyłane do niej przez Internet.

Ale okazuje się, że przepustowość jest droga. Masz dwie możliwości: albo utworzyć „ Coyote Beta Pro”, albo znaleźć sposób na rozwiązanie tego problemu. Niedawno ktoś zapytał (x + 2). Czy klient nie mógł wysłać x+2, a użytkownik nie widziałby różnicy?

Zadanie

Twoim zadaniem jest „zminimalizowanie” wyrażeń matematycznych. Biorąc pod uwagę wyrażenie wejściowe, musisz pozbyć się białych znaków i nawiasów, aż da minimalną reprezentację tego samego wejścia. Nawiasy wokół operacji asocjacyjnych nie muszą być zachowane.

Jedyne operatory podane tutaj są +, -, *, /, i ^(potęgowanie), ze standardowym skojarzeń matematycznej i pierwszeństwa. Jedyną białą spacją podaną na wejściu będą rzeczywiste znaki spacji.

Przykładowe wejście / wyjście

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

Punktacja

Wejścia / wyjścia mogą wykorzystywać dowolną preferowaną metodę. Najmniejszy program w bajtach wygrywa.

Dokładne bity

Potęgowanie jest właściwe asocjacyjne, a także zgodne ze standardowym pierwszeństwem matematycznym (będąc najwyższym). Poprawnym literałem liczbowym jest /[0-9]+/, a poprawnym literałem zmiennym jest /[a-z]+/. Pojedynczy literał zmiennej reprezentuje pojedynczą wartość, nawet jeśli jego długość znaku jest większa niż 1.

„Nawiasy wokół operacji asocjacyjnych nie muszą być zachowane” oznacza, że ​​dane wyjściowe powinny składać się z wyrażenia, które daje identyczne drzewo analizy, z wyjątkiem tego, że operacje asocjacyjne można zmienić.

TND
źródło
Chodzi o to, aby utworzyć minimalną równoważną instrukcję, która da to samo drzewo parsowania. Dzieje się tak, aby Coyote Beta mógł wyświetlić go wizualnie, gdy użytkownik wykona zapytanie.
TND
Jeśli poprawna jest zmienna /[a-z]+/, oznacza to pomnożenie przez zestawienie, tak jak abniedozwolone?
Joe Z.
1
Chcesz 2+(3+4)się zmienić 2+3+4, prawda? To zmienia drzewo analizy.
feersum
2
Nie zgadzam się z twierdzeniem, że x^(y/2)=x^y/2; potęgowanie ma wyższy priorytet zlecenia, ergo x^y/2=(x^y)/2.
Conor O'Brien
1
Aww człowieku, zamierzałem przesłać Prompt X:expr(X)w TI-BASIC, ale nie można uprościć :(
DankMemes

Odpowiedzi:

1

C #, 523 519 504 bajtów

Sprawdź komentarze w kodzie, aby zobaczyć, jak to działa!


Grał w golfa

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

Bez golfa

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

Notatki dodatkowe

  1. Naprawiono niektóre literówki i zmieniono nazwy niektórych zmiennych.
  2. Zagnieżdżono przełącznik, aby pozbyć się niepotrzebnej zmiennej. Naprawiono również błąd, który powodował, że niektóre rozwiązania były nieważne, zgłoszone przez Andersa Kaseorga .

PS: Jeśli masz wskazówkę lub znalazłeś błąd, daj mi znać w komentarzach, a ja postaram się go naprawić (dodam notatkę o usunięciu błędu wraz z Twoim imieniem;))

auhmaan
źródło
Niezła odpowiedź! : D merytoryczne odpowiedzi tutaj są na ogół lepiej odbierane, jeśli załączysz wyjaśnienie: P
kot
Czy mogę to zrobić w formie komentarzy do kodu?
auhmaan
Jasne, cokolwiek działa c:
kot
Więc to zrobię! Spróbuję też gdzieś dodać streszczenie.
auhmaan
Nawiasem mówiąc, witamy w Programowaniu Puzzle i Code Golf! (chociaż nie jest to twoja pierwsza odpowiedź)
kot
0

C ++, 284 bajty

Grał w golfa

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

Bez golfa

#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
źródło
Nie ma to żadnej logiki pierwszeństwa i zawodzi wiele podanych przypadków testowych.
Anders Kaseorg,