Algorithm to judge whether two expressions are equivalent

Question

Given two arithmetic expressions e1 and e2 that have same four operands, judge if they are equivalent. Two expression are equivalent if they can be arranged to be the same expression according to mathematical properties. Return true if they are equivalent, otherwise false.

I just cannot figure out an algorithm to solve this problem. I need this algorithm to solve the problem to list all solutions without replication of 24 Game.

Examples

Example 1:

• Input: e1 is "6 * (2 + 5 - 3)", e2 is "(5 - 3 + 2) * 6".
• Output: true

Example 2:

• Input: e1 is "5 - (2 - 7 * 3)", e2 is "3 * 7 + 5 - 3".
• Output: true

Example 3:

• Input: e1 is "(7 + 5) / (2 / 4)", e2 is "(7 + 5) * 4 / 2".
• Output: true

Example 4:

• Input: e1 is "(7 + 5) * 4 / 2", e2 is "(7 + 5) * (4 - 2)".
• Output: false.

Constraints

• e1 and e2 have exactly the same four integer number as operands that is between 1 to 10.
• Only four basic binary arithmetic operation can be used: addition(+), subtraction(-), multiplication(*), division(/).
• Minus(-) can only be used as a subtraction operator and not as a unary operator to compute the numeric negation of its operand.
• Parentheses can be used.

Answer 1

Finding an algorithm to solve this is challenging, since a special case of the problem as you've presented it is determining whether to polynomials are equivalent.

Polynomial identity testing has unknown computational complexity, but it's known that brute force solutions can take exponential time. Therefore, the standard approach to this is to use randomized inputs and test for equality using the Schwartz-Zippel lemma.

I expect that writing an implementation of this will be easier than other approaches and have better performance.

Note that you need to be careful of both integer overflow and floating-point issues in implementing this. For your case, it's probably sufficient to use unsigned 64-bit integers or long doubles.

You may worry about the probabilistic nature of the algorithm. But consider that we can transfer the question of whether p=q into the question of whether p-q=0. If p-q is zero across its entire range, then p=q. Otherwise, p-q is a d-degree polynomial with at most d points where it equals zero. If we choose test values from a set S of size |S| then the probability of finding one of these points is d/|S|, which becomes small as |S| grows. If we make multiple evaluations we can drive the probability even lower.

Answer 2

I will describe an approach, and indicate another more complex, but more efficient, approach.

If you didn't include division, then there would be a simple way to do this. Namely you multiply everything out, get a polynomial, write each term in lexicographic order (ie a before b, etc), then sort the terms in lexicographic order (by power of a, by power of b, etc), then combine like terms. This would turn each expression into a normalized form. Expressions match if and only if the polynomials match.

As @Richard notes, this algorithm has exponential complexity. But with only 4 operands, its complexity will be fine. You will have to think carefully while coding it, but you should be able to succeed.

BUT..we have division.

There are two ways you can go.

The simplest is to multiply out top and bottom to a multivariate polynomial of the form X/Y. If you want to know whether X1/Y1 = X2/Y2 you cross multiply and see whether X1*Y2 = X2*Y1. This requires pairwise comparisons between every pair of expressions. For a one time operation, this may be acceptable.

If it is not, then it is time to go down a rabbit hole. We need to put X/Y itself into normalized form. That requires computing a GCD, which Polynomial GCDs by Syzygies provides an algorithm for. To complete normalized form we not only want to be in the form X/Y with GCD(X, Y) = 1, but we also want to make sure that Y is in normalized form with a positive leading coefficient. (If the coefficient winds up negative, multiply top and bottom by -1.)

And now all of the expressions can be normalized, you can then compare (eg sort them), and see which are the same.

Good luck!