0

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.
Improve this question
11
  • 1
    Construct the parsing tree, compact it to canonical form, then compare the tree shape. Commented Apr 4, 2023 at 15:32
  • @Mike'Pomax'Kamermans what is the canonical form? Expanded out with variables in alphabetical order? Commented Apr 4, 2023 at 15:40
  • 2
    @Mike'Pomax'Kamermans I think you're glossing your way past some major challenges when it comes to rational expressions. Commented Apr 4, 2023 at 16:58
  • 2
    See stackoverflow.com/a/75932183/585411 for a description of how to handle the challenges around rational expressions. Commented Apr 4, 2023 at 17:23
  • 2
    "I need this algorithm to solve the problem to list all solutions without replication of 24 Game" -- no, you don't. What you're asking for is a lot harder than what you're trying to use it for. Commented Apr 4, 2023 at 22:53

2 Answers 2

Reset to default
1

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!

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

The method is globally ok. however, I would use as normalized form a list of terms. Each term defined by the number of occurences (that may be negative if term is preceeded by "-") and a list of items sorted by variable name. Each item being defined by the value identifying the variable and the "power" (1 indicates how many time the item is found, negative numbers denote that the variable is in the denominator. For comparison, a sort method is required, if the number of terms of the 2 expressions are different.
@Mike'Pomax'Kamermans The problem as stated allows a/a - b/(b+c). Without some sort of GCD logic, how will you recognize that this is the same as c/(b+c)? (Note, values must be integers greater than 0 so a/a is guaranteed not to blow up.)
@Mike'Pomax'Kamermans No additional rules. Read the problem again. a/a - b/(b+c) uses 6 operands, only allowed operations, and is the same for all positive integer inputs as c/(b+c). You can only forbid it by insisting on rules not stated in the problem.
@Mike'Pomax'Kamermans I would need to see working code to believe that it is always trivial. Because I don't think it is, and can easily imagine code in which it is not.
removed my comments that were detracting from the 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.

Improve this answer

6 Comments

I'm not sure why you'd want to evaluate anything here, rather than looking at the arithmetic parsing tree? You don't actually care about what values the symbols can take on, you just want to rewrite the expressions to a canonical form that you can then directly compare.
No floating point issues as all numbers (coefficients) involved are integer, and variables remain as symbols
@Mike'Pomax'Kamermans: There's not an efficient algorithm that can do such a rearrangement for the general case, though perhaps there is one for this limited set of operators.
@Richard There definitely is one for this limited set of operators.
@Richard absolutely, but this question isn't about all of calculus, just arithmetics, and doesn't even allow the unitary minus sign. A time-honred computer science homework exercise for the "write a math parser" class =)
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.