Declaraciones matemáticas minimizadoras

18

El reto

Usted es propietario de un servicio increíble llamado Coyote Beta , que responde mágicamente las preguntas de matemáticas que sus usuarios le envían a través de Internet.

Pero resulta que el ancho de banda es costoso. Tiene dos opciones: crear un " Coyote Beta Pro" o encontrar alguna forma de resolverlo. Recientemente, alguien preguntó (x + 2). ¿No podría enviar el cliente x+2y el usuario no vería ninguna diferencia?

La tarea

Su tarea es "minificar" las expresiones matemáticas. Dada una expresión de entrada, debe eliminar los espacios en blanco y los paréntesis hasta que proporcione una representación mínima de la misma entrada. Los paréntesis alrededor de las operaciones asociativas no necesitan ser preservados.

Los únicos operadores que se dan aquí son +, -, *, /, y ^(exponenciación), la asociatividad y precedencia matemática estándar. El único espacio en blanco dado en la entrada serán caracteres de espacio real.

Muestra de entrada / salida

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

Puntuación

La entrada / salida puede usar cualquier método preferido. El programa más pequeño en bytes gana.

Bits exactos

La exponenciación es correcta asociativa y también sigue la precedencia matemática estándar (siendo la más alta). Un literal numérico válido es /[0-9]+/, y un literal variable válido es /[a-z]+/. Un literal variable único representa un valor único incluso cuando la longitud de su carácter es mayor que 1.

Lo que se entiende por "los paréntesis alrededor de las operaciones asociativas no necesitan ser preservados" es que la salida debe consistir en una expresión que dé como resultado un árbol de análisis idéntico, con la excepción de que las operaciones asociativas pueden reorganizarse.

TND
fuente
La idea es crear una declaración equivalente mínima que dé como resultado el mismo árbol de análisis. Esto es para que Coyote Beta pueda mostrarlo visualmente cuando el usuario realiza una consulta.
TND
Si una variable válida es /[a-z]+/, ¿eso significa que abno se permite la multiplicación por yuxtaposición ?
Joe Z.
1
¿Quieres 2+(3+4)que te cambien 2+3+4, verdad? Esto cambia el árbol de análisis.
feersum
2
Estoy en desacuerdo con la afirmación de que x^(y/2)=x^y/2; exponenciación tiene una precedencia orden superior, ergo, x^y/2=(x^y)/2.
Conor O'Brien
1
Aww hombre, iba a presentar Prompt X:expr(X)en TI-BASIC pero no puede simplificar :(
DankMemes

Respuestas:

1

C #, 523 519 504 bytes

¡Comprueba los comentarios en código para ver cómo funciona!


Golfed

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

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

Notas al margen

  1. Se corrigieron algunos errores tipográficos y se cambió el nombre de algunos vars.
  2. Anidado un interruptor para deshacerse de una variable innecesaria. Además, se corrigió un error que invalidaría algunas soluciones, según informó Anders Kaseorg .

PD: Si tiene una sugerencia o encontró un error, hágamelo saber en los comentarios e intentaré solucionarlo (luego agregaré una nota sobre la corrección del error con su nombre;))

auhmaan
fuente
¡Buena respuesta! : D las respuestas sustanciales aquí generalmente se reciben mejor si incluye una explicación: P
cat
¿Puedo hacerlo en forma de comentarios de código?
auhmaan
Claro, lo que sea que funcione c:
gato
¡Entonces lo haré! También intentaré agregar un resumen en alguna parte.
auhmaan
¡Bienvenido a Programming Puzzles y Code Golf, por cierto! (aunque no es su primera respuesta)
gato
0

C ++, 284 bytes

Golfed

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

Sin 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
fuente
Esto no tiene ninguna lógica de precedencia y falla muchos de los casos de prueba dados.
Anders Kaseorg