Expression equivalence checking

[superbonzo]

As I sead before you must tackle the problem formally:

first of all let's get rid of minuses: given that you're not allowed manipualting signs ( A -> -(-A), and so on) we simply define two sets of symbols {A,B,C,...} and {Z,Y,X,...} of "positive" and "negative" symbols, respectively. Equivalence of expression will not allow swapping symbols of different "sign" (so, the inputs A and Z are not equivalent ).

then

1- "A","B",...,"Z" are expressions, called "symbols"
2- "(e)" is an expression whenever "e" is an expression
3- "e1+e2+..+en" ,n>=2 is an expression whenever "ej" is an expression for every j
4- "f1*f2*...*fk" ,k>=2 is an expression whenever for every j "fj" has the form "X" and X is a symbol or it has the form "(e)" and e is an expression
5- "f1/f2" is an expression whenever for every j "fj" has the form "X" and X is a symbol or it has the form "(e)" and e is an expression

in general, we say that an input form is a well formed expression iff there exists a unique sequence of steps 1-5 to build it.

in particular, we could think of steps 1-5 as functions:

1: capital letter -> the associated expression
2: expression e -> (e)
3: expression e1,...,en, n>=2 -> e1+...+en
...and so on

for example

A*(B+C)*(D) -> 4(1(A),2(3(1(B),1(C))),2(1(D)))

we will call the right hand side the "structure tree" S(e) of the input expression e.

finally, two inputs are equivalent if one can be cast into the other by the application of the following transformations to their structure trees:

I) a permutation of the set of positive symbols
II) a permutation of the set of negative symbols
III) a permutation of the arguments of function 3
IV) a permutation of the arguments of function 4

conditions III) and IV) are equivalent to asking if the labeled trees S(e1) and S(e2) are isomorphic; google for tree isomorphism or tree canonicalization problems, as far as I can remember its solution is logtime.
Given finite sets of positive and negative symbols this makes the whole algorithm logtime. Bye!