A multiplicação entre 2 números inteiros pode ser reduzida em uma série de adição como essa

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

Exponenciação (aumentando um para o poder b ) também pode ser reduzida para uma série de multiplicações:

5 ^ 3 = 5 * 5 * 5

Portanto, a exponenciação pode ser reduzida em uma série de adições, criando uma expressão de multiplicação e depois em uma série de adições. Por exemplo, 5 ^ 3(5 em cubos) pode ser reescrito 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

Sua tarefa é, dadas expressões somadas que consistem em exponenciação, multiplicação e adição, reduza-a à menor série de adições. A expressão "menor" é definida como a expressão com o menor número de +símbolos, ainda usando apenas um dos dois números na expressão original. Por exemplo, a expressão mais curta de 10 * 2é 10 + 10.

Os números envolvidos na entrada serão todos números inteiros positivos, e a expressão consistirá em apenas +(adição), *(multiplicação) e ^(exponenciação), juntamente com números inteiros e colchetes ( ()) para indicar precedência.

A saída deve consistir apenas de números inteiros positivos e +símbolos. Você não deve emitir as etapas individuais das reduções, apenas a saída final. A saída pode não consistir em números que não apareçam na entrada. No entanto, você pode usar quaisquer 3 símbolos distintos em vez de +*^, mas diga quais símbolos eles são

Os espaços que separam entradas e saídas podem ou não ser usados ​​em seus programas, ou seja, 3 * 5podem ser gerados como 5 + 5 + 5ou 5+5+5.

Observe que, na maioria dos casos, a adição não é realmente executada. O único caso em que a adição deve ser realizada é quando você tem algo como 5 ^ (1 + 2), nesse caso, a adição é necessária para continuar -> 5 ^ 3 -> 5 * 5 * 5 -> .... Veja o caso de teste nº 4.

Seu código não precisa manipular entradas que cheguem a uma expressão ambígua. Por exemplo (2 + 2) * (4 + 1),. Devido às regras estabelecidas até agora, o objetivo não é calcular a resposta, o objetivo é simplificar as adições. Portanto, o resultado pode ser diferente dependendo da ordem em que as expressões são resolvidas ou comutadas (quais adições simplificar, quais deixar?). Outro exemplo inválido: ((3 + 2) ^ 2) ^ 3 -> ((3 + 2) * (3 + 2)) ^ 3 -> ???.

Isso é código-golfe, então o código mais curto ganha

Casos de teste

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

Tenho certeza de que isso pode ser jogado, mas, neste momento, estou feliz que funcione. As seções de exponenciação e multiplicação são muito semelhantes, mas como a ordem das operações é importante, não sei como combiná-las.

y- Exponenciação
x- Multiplicação
p- Adição

\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

Experimente online - todos os casos de teste

Conversor de caso de teste

Explicação

\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

Você também pode perceber que o grupo mais usado é (\(\w+\)|1+). Isso corresponde a uma expressão interna entre parênteses ou um número inteiro. Eu escolhi usar os símbolos que fiz para poder usar em \wvez de uma classe de personagem. Não tenho certeza se seria melhor usar símbolos que não sejam palavras e substituir algumas soluções alternativas por bordas de palavras ( \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 a função em f.

A entrada é uma expressão matemática simples. (ou seja, 1 + 2não "1 + 2").

Experimente Online!

Observe que o link TIO tem um código ligeiramente diferente, pois o TIO (que, presumo, usa o kernel do Mathematica) não gosta Infix. Em Rifflevez disso, usei a mesma aparência do Mathematica REPL.

Ungolfed

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

Ungolfed e explicou

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

Eu tive muitos problemas para obter o seguinte efeito: essa função usa como entrada uma expressão padrão do Mathematica, com o habitual +,* e ^operações (e parênteses) na mesma, e saídas que parece ser uma expressão Mathematica padrão (mas com sinais de adição "desativados") como resposta.

A função acima começa desativando todas as operações na entrada. Em seguida, aplica regras de expansão repetidamente até que nada mais possa ser simplificado. Sempre que encontra um produto como 2 * 3 * 4, que pode ser expandido de várias maneiras, ele faz uma lista de possíveis expansões e continua. No final, obtemos uma lista de possíveis respostas finais, e a mais curta é escolhida.