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!

Categories

Expression equivalence checking

amberovskyamberovsky 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.


Sign In or Register to comment.