Problem Detail: 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?
Asked By : LaBird
Answered By : Rob
Note that if you just want to know if two equations without variables have the same result, then just evaluate them already. But it’s more tricky with variables: I assume that you are basically just functionally rearranging lists (ie: like Python/JavaScript/Lisp code). For associative binary operators, it’s convenient to make them have n operands to avoid a re-association pattern matching mess. A sum or product of one operand is a redundant parenthesis. Because they happen to be commutative, have the sum and product objects consistently sort their operands if you want them to be efficiently comparable (ie: define a canonical form that everything should reduce to). It is harder if variables are involved though. The equals sign can be treated as just another binary operator to create new expressions, where you do things like: a, (a=(b*2)), ((a=(b*2))+6), ((a+6)=(b*2)+6), ((a+6)=(2*b)+6). At that point, you construct new expressions like: equate(expr,expr), add(expr,expr), mul(expr, expr), ldistribute(expr,expr), rdistribute(expr,expr), commute(expr), etc. Some of the rules are obvious like distributing multiplication over addition, or additive or multiplicative cancellation; and usually go in one direction (like automatic differentiation). But there will be other times where you will need to do a more clever search (like a chess engine), doing things like multiply an expression times 1, and equate it with a new variable divided by itself, etc. One of the more tricky things in an algorithm for solving is that some operations like division add new logical constraints. If you construct div(add(a,b),x), you implicitly construct a logical constraint for x!=0; and you need to work these constraints in so that the search for the solution doesn’t generate nonsense. These kinds of programs are usually written as pattern matching and rewriting, with provisions made to not go in infinite loops.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/40033 Ask a Question Download Related Notes/Documents
