Distribute the additions!

Question

Challenge: Given an expressions made of additions and multiplications, output an expression that is a sum of products. The output must be equivalent to the input modulo the law of distribution. For example, \$1 + ((2 + 5\times 6) \times(3+4))\$ becomes \$1 + 2 \times 3 + 2 \times 4 + 5\times6\times3 + 5 \times 6 \times 4 \$. This is code-golf.

This task is useful in automatic theorem proving, since the conversion to disjunctive normal forms is exactly the same task. (Oops, that gives away a Mathematica builtin!)

Clarifications:

• You can assume the numbers are whatever you want, integers, floats, or even just strings of symbols, as long as it's convenient.
• You can use the law of distribution, commutativity and associativity of addition and multiplication. But you cannot use any other property of addition or multiplication. So e.g. \$3 \times (1 + 3) \to 3 + 3 \times 3\$ is not acceptable.
• This means that answers are not unique, the test cases are just a reference.
• Parentheses are optional, you won't need them anyway.
• You can assume any reasonable input form.

Test cases:

2 -> 2 (Corner case, you can ignore this.)
1+3 -> 1+3
1+(3*4) -> 1+3*4
1+3*4 -> 1+3*4
(1+3)*4 -> 1*4+3*4
(1+2+3)*(4+5+6) -> 1*4+2*4+3*4+1*5+2*5+3*5+1*6+2*6+3*6
(1+2*(3+4))*((5+6)*7)+8 -> 1*5*7+1*6*7+2*3*5*7+2*3*6*7+2*4*5*7+2*4*6*7+8

Answer 1

Haskell, 139 bytes

data M=I Int|M:*M|M:+M deriving(Show,Read)
f(x:*y)|z:+w<-f y=f(x:*z):+f(x:*w)|z:+w<-f x=f(z:*y):+f(w:*y)
f(x:+y)=f x:+f y
f x=x
show.f.read

Try it online!

IO Format

Here our IO format uses the functions :+ for addition and :* for multiplication. We also require that numbers themselves are prefixed with I , and that all parentheses be explicit.

So for example

2 * (3 * (1 + 2))

is

I 2 :* (I 3 :* (I 1 :+ I 2))

We uses this format because we are parsing into a native haskell data type defined on the first line. If I could operate on the data type directly the code would be a lot shorter:

Haskell, 107 bytes

data M=I Int|M:*M|M:+M
f(x:*y)|z:+w<-f y=f(x:*z):+f(x:*w)|z:+w<-f x=f(z:*y):+f(w:*y)
f(x:+y)=f x:+f y
f x=x

Try it online!

Since this gets rid of all the parsing bits and just includes the manipulations.

Answer 2

Python 3, 157 bytes

lambda e:"+".join(eval(re.sub("\d","A('\g<0>')",e)))
import re
class A(list):__mul__=lambda s,x:A(i+"*"+j for i in s for j in x);__add__=lambda s,x:A([*s]+x)

How it works :

We define a new object named A with the wanted properties for addition and multiplication.

• each digit is stored as a list of string
• an expression like 1+2 is converted into ['1', '2']
• an expression like 1*2 is converted into ['1*2']
• the sum is equivalent to the python list addition
• the product is a double iteration over the 2 lists

Then we let python do the multiplication over addition priority

• re.sub("\d","A('\g<0>')",e) we convert all the digits in our expression into instances of this object
• "+".join(eval(...)) we evaluate and formate the result

Try it online!

Answer 3

Retina 0.8.2, 118 bytes

{`\(([\d*]+)\)
$1
\(([\d*]+)\+([^()]+\))(\*([\d*]+|\([^()]+\)))
$1$3+($2$3
([\d*]+\*)\(([\d*]+)\+([^()]+\))
$1$2+$1($3

Try it online! Link includes test cases. Explanation:

{`

Perform all possible reductions.

\(([\d*]+)\)
$1

(a*b*...) becomes a*b*....

\(([\d*]+)\+([^()]+\))(\*([\d*]+|\([^()]+\)))
$1$3+($2$3

(a*b*...+c*d*...+...)*f*g*... becomes a*b*...*f*g*...+(c*d*...+...)*f*g*, where f*g*... could instead be (f*g*...+h*i*...+...).

([\d*]+\*)\(([\d*]+)\+([^()]+\))
$1$2+$1($3

a*b*...*(c*d*...+e*f*...+...) becomes a*b*...*c*d*...+a*b*...(e*f*...+...).