Expression equivalence checking

[superbonzo]

usually this kind of problems are solved by translating the expression into a properly defined normal form.
first of all suppose the input has no spaces and it's well formed.
let's use the letter A... for identifier placeholders, a... for operators placeholders, Z... as generic placeholders and z... as generic expression placeholders.
We'll go by structural induction:

1) aAbBcCd... where abc are + or -
	-> split the symbol placeholders in a positive and a negative n-uple (A is positive if a=+...)
	-> order the n-uples lexicographically
	-> substitute each n-uple element with its order
	( example: +B-A+A-C -> {B,A}{A,C} -> {A,B}{A,C} -> {1,2}{1,3} )

2) AaBbCc... where abc are + or -
	-> +AaBbCc -> the proceed as in 1)

3) z(ZYX...)y
	-> z(Z)(Y)(X)y...
		where (+) -> +, (-) -> - and so on
		and (A),(B),... are treated as new symbols

( examples:
	(A+A)+B-C -> (A)(+)(A)+B-C -> (A)+(A)+B-C -> {(A),(A),B}{C} -> {1,1,2}{3}
	(B+B)-C+A -> (B)(+)(B)-C+A -> (B)+(B)-C+A -> {(B),(B),A}{C} -> {1,1,2}{3}
	(A+B)+A-C -> ... -> {1,2,3}{4}
	)

4) given expressions z*y -> the lexicographically ordered pair of ... well look at the examples
5) given expressions z/y -> the ordered pair  ... again, it's better looking at the examples

examples:

(A+B-C)*(C+C) ->
	(A+B-C) -> {(A),(B)}{(C)}
	(C+C)	-> {(C),(C)}{}
		-> {{(A),(B)}{(C)},{(C),(C)}{}} -> {{1,2}{3},{3,3}{}}

(D+D)*(B+A-D) ->
	(D+D)	-> 	{(D),(D)}{}
	(B+A-D)	->	{(A),(B)}{(D)}
		-> {{{(A),(B)}{(D)}}{(D),(D)}{}} -> {{1,2}{3},{3,3}{}}

Z/A -> {{Z}{},{A}{}} -> {{1}{},{2}{}}

so two inputs are equivalent if their normal forms coincide. At frst sight the resulting algorithm should be nlog(n), but I've not payed much attention to details. I hope this give you some ideas to work on...