Minimierung mathematischer Aussagen

18

Die Herausforderung

Sie sind der Besitzer eines erstaunlichen Dienstes namens Coyote Beta , der auf magische Weise mathematische Fragen beantwortet, die seine Benutzer über das Internet an ihn senden.

Es stellt sich jedoch heraus, dass Bandbreite teuer ist. Sie haben zwei Möglichkeiten, entweder ein " Coyote Beta Pro" zu erstellen oder einen Weg zu finden, dies zu lösen. Erst kürzlich hat sich jemand erkundigt (x + 2). Konnte der Client nicht senden x+2und der Benutzer würde keinen Unterschied sehen?

Die Aufgabe

Ihre Aufgabe ist es, mathematische Ausdrücke zu "minimieren". Bei einem Eingabeausdruck müssen Sie Leerzeichen und Klammern entfernen, bis eine minimale Darstellung derselben Eingabe vorliegt. Die Klammern um assoziative Operationen müssen nicht beibehalten werden.

Die einzigen Operatoren, die hier angegeben werden +, -sind *, /und ^(Exponentiation) mit mathematischer Standardassoziativität und -priorität. Das einzige in der Eingabe angegebene Leerzeichen sind Leerzeichen.

Sample 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

Wertung

Die Eingabe / Ausgabe kann nach einer beliebigen Methode erfolgen. Das kleinste Programm in Bytes gewinnt.

Genaue Bits

Die Potenzierung ist rechtsassoziativ und folgt ebenfalls der mathematischen Rangfolge (wobei sie die höchste ist). Ein gültiges numerisches Literal ist /[0-9]+/und ein gültiges variables Literal ist /[a-z]+/. Ein einzelnes Variablenliteral repräsentiert einen einzelnen Wert, auch wenn seine Zeichenlänge länger als 1 ist.

Mit "die Klammern um assoziative Operationen müssen nicht beibehalten werden" ist gemeint, dass die Ausgabe aus einem Ausdruck bestehen sollte, der zu einem identischen Analysebaum führt, mit der Ausnahme, dass assoziative Operationen neu angeordnet werden können.

TND
quelle
Die Idee ist, eine minimale äquivalente Anweisung zu erstellen, die zum gleichen Analysebaum führt. Auf diese Weise kann Coyote Beta es visuell anzeigen, wenn der Benutzer eine Abfrage vornimmt.
TND
Wenn eine gültige Variable ist /[a-z]+/, bedeutet dies, dass die Multiplikation mit einer Nebeneinanderstellung abnicht zulässig ist.
Joe Z.
1
Du willst 2+(3+4)doch geändert werden 2+3+4, oder? Dies ändert den Analysebaum.
Feersum
2
Ich bezweifle die Behauptung, dass x^(y/2)=x^y/2; Potenzierung hat einen höheren Vorrang x^y/2=(x^y)/2.
Conor O'Brien
1
Oh Mann, ich wollte Prompt X:expr(X)in TI-BASIC einreichen, aber Sie können nicht vereinfachen :(
DankMemes

Antworten:

1

C #, 523 519 504 Bytes

Überprüfen Sie die In-Code-Kommentare, um zu sehen, wie es funktioniert!


Golf gespielt

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

Ungolfed

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

Randnotizen

  1. Einige Tippfehler behoben und einige Vars umbenannt.
  2. Verschachtelte einen Schalter, um eine unnötige Variable loszuwerden. Außerdem wurde ein Fehler behoben, durch den einige von gemeldete Lösungen ungültig wurden Anders Kaseorg .

PS: Wenn Sie einen Tipp haben oder einen Fehler gefunden haben, lassen Sie es mich bitte in den Kommentaren wissen und ich werde versuchen, ihn zu beheben.

auhmaan
quelle
Gute Antwort! : D substanzielle Antworten hier sind in der Regel besser, wenn Sie eine Erklärung enthalten: P
Katze
Kann ich das in Form von Code-Kommentaren machen?
Auhmaan
Klar, was auch immer funktioniert c:
Katze
Dann mache ich das! Ich werde auch versuchen, irgendwo eine Zusammenfassung hinzuzufügen.
Auhmaan
Übrigens, Willkommen bei Programming Puzzles und Code Golf! (obwohl es nicht Ihre erste Antwort ist)
Katze
0

C ++, 284 Bytes

Golf gespielt

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

Ungolfed

#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
quelle
Dies hat keine Prioritätslogik und schlägt viele der angegebenen Testfälle fehl.
Anders Kaseorg