Expression equivalence checking - Programmers Heaven

#### Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

# Expression equivalence checking

Posts: 1Member
Hi All.

I'm trying to solve following problem:

Given two ariphmetic expressions, operations are +, -, *, /, () and operands are just identifiers.
Operations are not associative, but + and * are commutative.
The question is: whether it is possible to rename identifiers and to rearrange operands at commutative operations (+, *) so that to reduce one expression to another.

For example:

1.
Input:
A+B
C+B
Output:
Yes

2.
Input:
(A+A)+B
C+(D+D)
?????:
Yes

3.
Input:
(A+A)+B
(A+B)+A
Output:
No

4.
Input:
A+A+B
A+B+A
Output:
NO

5.
Input:
A+B*C
A1+A2*A2
Output:
No

6.
Input:
(A+B-C)*(C+C)
(D+D)*(B+A-D)
Output:
Yes

I created following algorithm:

1. Build expressions' trees. (They are binaries trees).
2. Check for trees ismorphism with fixed roots.
3. Check identifiers sets.

But is this algorithm correct?
And how to do stage 3 except full recursive?

Thanks.