CODEWITHSUNDEEP
algorithmexpression
Alex O
Alex O

Reputation: 1867

Algorithm to detect equivalent expressions

For fun I am playing around with a program to solve the 24 game, and I'm trying to find a way to avoid displaying equivalent expressions when checking for multiple solutions.

For example, given the numbers 6, 6, 6, 6, the algorithm may (iteratively or recursively) generate several equivalent expressions.
For example: ((6 + 6) + 6) + 6, (6 + 6) + (6 + 6) and others, since all of them mean "add the four sixes together".

Obviously, things become more interesting when dealing with all four arithmetic operands.
For example, the expressions A * B + C * D and C * D + B * A are also equivalent.

Another case, which may be more difficult to detect is A - B - C - D vs A - (C + B + D)

Ideas that I have so far:

  1. Only using parentheses when needed (by tracking precedence and associativity).
  2. Ordering operands for easy comparisons.

Upvotes: 0

Views: 162

Answers (1)

Salvador Dali
Salvador Dali

Reputation: 222581

After you generated all the possible expressions that result in 24, I would add a normalization step. The goal of this step is to remove redundant parenthesis.

A nice explanation of how to remove redundant parenthesis is given here. After that you just have a set of all your normalized expressions.

Upvotes: 1

Related Questions