Minimiser les énoncés mathématiques

18

Le défi

Vous êtes le propriétaire d'un service incroyable appelé Coyote Beta , qui répond comme par magie aux questions mathématiques que ses utilisateurs lui envoient sur Internet.

Mais il s'avère que la bande passante coûte cher. Vous avez deux choix, soit créer un " Coyote Beta Pro" ou trouver un moyen de résoudre ce problème. Tout récemment, quelqu'un a demandé (x + 2). Le client n'a-t-il pas pu envoyerx+2 et l'utilisateur ne verrait aucune différence?

La tâche

Votre tâche consiste à «réduire» les expressions mathématiques. Étant donné une expression d'entrée, vous devez vous débarrasser des espaces et des parenthèses jusqu'à ce qu'elle donne une représentation minimale de la même entrée. Les parenthèses autour des opérations associatives n'ont pas besoin d'être conservées.

Les seuls opérateurs donnés ici sont +, -, *, /et^ (exponentiation), avec associativité mathématique standard et priorité. Les seuls espaces fournis dans l'entrée seront des caractères d'espace réels.

Exemple d'entrée / sortie

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

Notation

L'entrée / sortie peut utiliser n'importe quelle méthode préférée. Le plus petit programme en octets gagne.

Bits exacts

L'exponentiation est associative à droite et suit également la priorité mathématique standard (étant la plus élevée). Un littéral numérique valide est /[0-9]+/, et un littéral de variable valide est /[a-z]+/. Un littéral de variable unique représente une valeur unique même lorsque sa longueur de caractère est supérieure à 1.

Ce que l'on entend par «les parenthèses autour des opérations associatives n'ont pas besoin d'être conservées» est que la sortie doit consister en une expression qui aboutit à un arbre d'analyse identique, à l'exception que les opérations associatives peuvent être réorganisées.

TND
la source
L'idée est de créer une instruction équivalente minimale qui donne le même arbre d'analyse. Cela permet à Coyote Beta de l' afficher visuellement lorsque l'utilisateur fait une requête.
TND
Si une variable valide est /[a-z]+/, cela signifie que la multiplication par juxtaposition comme abest interdite?
Joe Z.17
1
Vous voulez 2+(3+4)être changé pour 2+3+4, non? Cela change l'arbre d'analyse.
feersum
2
Je conteste l'affirmation selon laquelle x^(y/2)=x^y/2; exponentiation a une priorité d'ordre supérieur, ergo, x^y/2=(x^y)/2.
Conor O'Brien
1
Aww mec, j'allais soumettre Prompt X:expr(X)en TI-BASIC mais vous ne pouvez pas simplifier :(
DankMemes

Réponses:

1

C #, 523 519 504 octets

Vérifiez les commentaires dans le code pour voir comment cela fonctionne!


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

Non golfé

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

Notes annexes

  1. Correction de quelques fautes de frappe et renommé certains vars.
  2. Imbriqué un commutateur pour se débarrasser d'une variable inutile. Correction d'un bug qui rendrait certaines solutions invalides, signalé par Anders Kaseorg .

PS: Si vous avez une astuce ou avez trouvé un bug, faites-le moi savoir dans les commentaires et j'essaierai de le corriger (je vais ensuite ajouter une note sur le bug avec votre nom;))

auhmaan
la source
Bonne réponse! : D les réponses substantielles ici sont généralement mieux reçues si vous incluez une explication: P
cat
Puis-je le faire sous forme de commentaires de code?
auhmaan
Bien sûr, tout ce qui fonctionne c:
cat
Alors je ferai ça! J'essaierai également d'ajouter un résumé quelque part.
auhmaan
Bienvenue dans Programmation de puzzles et Code Golf, au fait! (même si ce n'est pas votre première réponse)
chat du
0

C ++, 284 octets

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

Non 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;
}
Michelfrancis Bustillos
la source
Cela n'a pas de logique de priorité et échoue à la plupart des cas de test donnés.
Anders Kaseorg