La multiplicación entre 2 enteros se puede reducir en una serie de sumas así

3 * 5 = 3 + 3 + 3 + 3 + 3 = 5 + 5 + 5

La exponenciación (elevar a a la potencia b ) también se puede reducir en una serie de multiplicaciones:

5 ^ 3 = 5 * 5 * 5

Por lo tanto, la exponenciación puede reducirse en una serie de adiciones, creando una expresión de multiplicación y luego en una serie de adiciones. Por ejemplo, 5 ^ 3(5 cubos) se puede reescribir como

5 ^ 3 = 5 * 5 * 5
      = (5 + 5 + 5 + 5 + 5) * 5
      = (5 + 5 + 5 + 5 + 5) + (5 + 5 + 5 + 5 + 5) + (5 + 5 + 5 + 5 + 5) + (5 + 5 + 5 + 5 + 5) + (5 + 5 + 5 + 5 + 5)
      = 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5

Su tarea es, dadas expresiones agregadas juntas que consisten en exponenciación, multiplicación y suma, reducirla a la serie más corta de adiciones. La expresión "más corta" se define como la expresión con el menor número de +símbolos, utilizando solo uno de los dos números en la expresión original. Por ejemplo, la expresión más corta de 10 * 2es 10 + 10.

Los números involucrados en la entrada serán todos enteros positivos, y la expresión consistirá solo en +(suma), *(multiplicación) y ^(exponenciación), junto con enteros y corchetes (() ) para indicar la precedencia.

La salida debe consistir en enteros positivos y +símbolos solamente. No debe generar los pasos individuales de las reducciones, solo el resultado final. La salida puede no consistir en ningún número que no aparezca en la entrada. Sin embargo, puede usar 3 símbolos distintos en lugar de +*^, pero diga qué símbolos son

Los espacios que separan las entradas y las salidas pueden o no usarse en sus programas, es decir, 3 * 5pueden salir como 5 + 5 + 5o 5+5+5.

Tenga en cuenta que en la mayoría de los casos, la adición no se realiza realmente. El único caso en el que se debe realizar la suma es cuando tiene algo como 5 ^ (1 + 2), en cuyo caso, la adición es necesaria para continuar-> 5 ^ 3 -> 5 * 5 * 5 -> ... . Ver caso de prueba # 4.

Su código no necesita manejar entradas que llegan a una expresión ambigua. Por ejemplo, (2 + 2) * (4 + 1). Debido a las reglas establecidas hasta ahora, el objetivo no es calcular la respuesta, sino simplificar las adiciones. Entonces, el resultado podría ser diferente dependiendo del orden en que las expresiones se resuelvan o conmuten (¿qué adiciones simplificar, cuáles dejar?). Otro ejemplo válido: ((3 + 2) ^ 2) ^ 3 -> ((3 + 2) * (3 + 2)) ^ 3 -> ???.

Esto es código golf por lo que el código más corto gana

Casos de prueba

Input => output

5 ^ 3 + 4 * 1 ^ 5 => 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 4
2 ^ 1 * 2 + 3 + 9 => 2 + 2 + 3 + 9
2 ^ 1 * (2 + 3) + 9 => 2 + 3 + 2 + 3 + 9
2 ^ (1 * (2 + 3)) + 9 => 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 9
10 + 3 * 2 + 33 ^ 2 => 10 + 3 + 3 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33
100 * 3 => 100 + 100 + 100
2 ^ 1 + 2 ^ 1 + 2 ^ 2 + 8 ^ 1 => 2 + 2 + 2 + 2 + 8
(1 + 2 + 5 * 8 + 2 ^ 4) * 2 => 1 + 2 + 8 + 8 + 8 + 8 + 8 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 1 + 2 + 8 + 8 + 8 + 8 + 8 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2

Retina , 302 bytes

Estoy seguro de que se puede jugar al golf, pero en este punto, me alegro de que funcione. Las secciones de exponenciación y multiplicación son muy similares, pero como el orden de las operaciones es importante, no sé cómo combinarlas.

y- Exponenciación
x- Multiplicación
p- Suma

\d+
$*
{1`(\(\w+\)|1+)y(\(\w+\)|1+)
>$0<
(?<=>(\(\w+\)|1+)y1*)1
$1x
>(\(\w+\)|1+)y
(
x<
)
\((1+(x1+)*)\)(?!y)
$1
(?<!1)(1+)x(\(\w+\)|1+\1)(?!1)
$2x$1
1`(\(\w+\)|1+)x1+
>$0<
(?<=>(\(\w+\)|1+)x1*)1
$1p
>(\(\w+\)|1+)x
(
p<
)
(?<!x|y)\((1+(p1+)*)\)(?!x|y)
$1
y\((1+)p([1p]*\))
y($1$2
}`y\((1+)\)
y$1
1+
$.0

Pruébelo en línea : todos los casos de prueba

Convertidor de casos de prueba

Explicación

\d+                             Convert to unary
$*
{1`(\(\w+\)|1+)y(\(\w+\)|1+)    Begin loop: Delimit current exponentiation group
>$0<
(?<=>(\(\w+\)|1+)y1*)1          Replace exponentiation with multiplication
$1x
>(\(\w+\)|1+)y                  Replace garbage with parentheses
(
x<
)
\((1+(x1+)*)\)(?!y)             Remove unnecessary parentheses around multiplication
$1
(?<!1)(1+)x(\(\w+\)|1+\1)(?!1)  Maybe swap order of multiplicands
$2x$1
1`(\(\w+\)|1+)x1+               Delimit current multiplication group
>$0<
(?<=>(\(\w+\)|1+)x1*)1          Replace multiplication with addition
$1p
>(\(\w+\)|1+)x                  Replace garbage with parentheses
(
p<
)
(?<!x|y)\((1+(p1+)*)\)(?!x|y)   Remove unnecessary parentheses around addition
$1
y\((1+)p([1p]*\))               Handle the 4th test case by adding if necessary
y($1$2
}`y\((1+)\)                     End of loop
y$1
1+                              Convert unary back to decimal
$.0

También puede notar que el grupo más utilizado es (\(\w+\)|1+). Esto coincide con una expresión interna con paréntesis o un número entero. Elegí usar los símbolos que hice para poder usar en \wlugar de una clase de caracteres. No estoy seguro de si sería mejor usar símbolos que no sean palabras y reemplazar algunas búsquedas con bordes de palabras ( \b).

Mathematica, 250 218 183 170 bytes

f~(s=SetAttributes)~HoldAll;{a,t}~s~Flat;f@n_:=Infix[Hold@n//.{a_~Power~b_:>t@@Hold@a~Table~b,Times->t,Plus->a,Hold->Dot}/.t->(a@@Table[#,1##2]&@@Reverse@Sort@{##}&),"+"]

^{¡Funciona! ¡Finalmente!}

Define la función en f .

La entrada es una expresión matemática simple. (es decir, 1 + 2no"1 + 2" ).

Pruébalo en línea!

Tenga en cuenta que el enlace TIO tiene un código ligeramente diferente, ya que TIO (que, supongo, usa el núcleo de Mathematica) no le gusta Infix. solíaRiffle obtener la misma apariencia que Mathematica REPL.

Sin golf

f~(s = SetAttributes)~HoldAll;  (* make f not evaluate its inputs *)

{a, t}~s~Flat;  (* make a and t flat, so that a[a[1,a[3]]] == a[1,3] *)

f@n_ :=  (* define f, input n *)

 Infix[

  Hold@n  (* hold the evaluation of n for replacement *)

    //. {  (* expand exponents *)

     (* change a^b to t[a,a,...,a] (with b a's) *)
     a_~Power~b_ :> t @@ Hold@a~Table~b,

     (* Replace Times and Plus with t and a, respectively *)
     Times -> t, 
     Plus -> a, 

     (* Replace the Hold function with the identity, since we don't need
         to hold anymore (Times and Plus are replaced) *)
     Hold -> Dot 

     } /.  (* Replace; expand all t (= `Times`) to a (= `Plus`) *)

        (* Take an expression wrapped in t. *)
        (* First, sort the arguments in reverse. This puts the term
            wrapped in `a` (if none, the largest number) in the front *)
        (* Next, repeat the term found above by <product of rest
            of the arguments> times *)
        (* Finally, wrap the entire thing in `a` *)
        (* This will throw errors when there are multiple elements wrapped
           in `a` (i.e. multiplying two parenthesized elements) *)
        t -> (a @@ Table[#, 1 ##2] & @@
               Reverse@Sort@{##} &),

  "+"]  (* place "+" between each term *)

Mathematica, 405 406 bytes

f~SetAttributes~HoldAll;p=(v=Inactive)@Plus;t=v@Times;w=v@Power;f@x_:=First@MinimalBy[Inactivate@{x}//.{w[a___,b_List,c___]:>(w[a,#,c]&/@b),t[a___,b_List,c___]:>(t[a,#,c]&/@b),p[a___,b_List,c___]:>(p[a,#,c]&/@b),p[a_]:>a,w[a_,b_]:>t@@Table[a,{Activate@b}],t[a___,t[b__],c___]:>t[a,b,c],p[a___,p[b__],c___]:>p[a,b,c],{a___,{b__},c___}:>{a,b,c},t[a__]:>Table[p@@Table[i,{Activate[t@a/i]}],{i,{a}}]},Length];f

Desengañado y explicado

SetAttributes[f, HoldAll]
p = Inactive[Plus]; t = Inactive[Times]; w = Inactive[Power];
f[x_] := First@MinimalBy[
   Inactivate[{x}] //. {
     w[a___, b_List, c___] :> (w[a, #, c] & /@ b),
     t[a___, b_List, c___] :> (t[a, #, c] & /@ b),
     p[a___, b_List, c___] :> (p[a, #, c] & /@ b),
     (* distribute lists of potential expansions over all operations *)
     p[a_] :> a,
     (* addition of a single term is just that term *)
     w[a_, b_] :> t @@ Table[a, {Activate@b}],
     (* a^b simplifies to a*a*...*a b times no matter what b is *)
     t[a___, t[b__], c___] :> t[a, b, c],
     p[a___, p[b__], c___] :> p[a, b, c],
     {a___, {b__}, c___} :> {a, b, c},
     (* operations are associative *)
     t[a__] :> Table[p @@ Table[i, {Activate[t@a/i]}], {i, {a}}]
     (* for a product, generate a list of potential expansions *)}
   , Length]
f

Fui a una gran cantidad de problemas para obtener el siguiente efecto: esta función toma como entrada una expresión estándar de Mathematica, con el habitual +, *y^ las operaciones (y entre paréntesis) en el mismo, y salidas de lo que parece ser una expresión estándar de Mathematica (pero con "desactivado" más signos) como la respuesta.

La función anterior comienza desactivando todas las operaciones en la entrada. Luego, aplica las reglas de expansión repetidamente hasta que ya no se pueda simplificar nada. Cada vez que encuentra un producto como 2 * 3 * 4, que se puede expandir de múltiples maneras, hace una lista de posibles expansiones y continúa. Al final, obtenemos una lista de posibles respuestas finales, y se elige la más corta.