# Algorithm to determine two binary expression trees will give the same result based on associative and commutative properties of some operators

Given n different numbers, I would like to find out whether there exists an algebraic expression using all the n numbers, with n−1 binary operators and unlimited number of parentheses, that evaluates to a certain number T. My idea is to make use of binary expression trees, construct all possible trees and then find the result by brute force.

As I have learned, the number of possible combinations will be:

\begin{aligned} \frac{(2(n-1))!}{(n-1)!n!} n! s^{n-1}\\ \end{aligned}

where s is the number of different binary operators that is allowed to be used (e.g. if we allow +, −, × and ÷, then s=4), and

\begin{aligned} \frac{(2(n-1))!}{(n-1)!n!} \end{aligned}

is the number of different types of binary expression trees that can be constructed without considering the content of the nodes.

To speed up the search, I have an idea to make use of the associative and commutative properties of the operators + and ×. An intuitive case will be, if all the n−1 operators chosen are all +, then all the trees will evaluate to the same result, regardless of how the n numbers are allocated in the leaf nodes. However, this obviously does not apply to operators − and ÷. And, in the general case, the operators chosen will consist of a mixture of +, −, × and ÷, so is there an algorithm to check the trees will evaluate to the same result without actually doing the calculation?

e.g. A binary expression tree that represents (8−5)×(6+3)×(7−4) will give the same result as a binary expression tree that represents (8−5)×((6+3)×(7−4)). Going even further, they will also give the same result as a binary expression tree that represents (3+6)×(7−4)×(8−5). Is there such an algorithm to detect these trees will evaluate to the same result?

• You are aware that this problem is NP-hard? Show via reduction from PARTITION (allow only + and -, target value 0).
– Raphael
Mar 4 '15 at 6:15