Matching templates against a tree - any ideas?

[Ian Clarke]

This isn't a Python question, but I would imagine that it might appeal
to the type of people who frequent this list.

While recently thinking of good ways to automatically solve equations, I
came across the problem of trying to find an efficient method to match a
tree, or subtree of that tree, against a template - so that a
transformation could be applied.

Lets say that I defined a transformation (expressed in Polish notation)
as such:

*+AB+CD -> ++*AC*AD+*BC*BD

This represents:

(A+B)*(C+D) -> (A*C)+(A*D)+(B*C)+(B*D)

Now lets say I had an expression, say:

++m*++mkp+f*nkf

The tree for this looks like:

                         +
                        / \
                       +   f
                      / \
                     /   \
                    m     *
                         / \
                        /   \
                       +     \
                      / \     \
                     /   \     +
                    +     p   / \
                   / \       f   *
                  m   k         / \
                               n   k

Can I apply the transformation given above to this equation?

In fact I can, the segment *++mkp+f*nk matches the template, where:

A=+mk
B=p
C=f
D=*nk

The obvious algorithm for this is to traverse the tree attempting to
match each subtree in the tree against the template, however this would
be inefficient (there could be many trees, each if which may be large,
and many templates).

But I need an efficient algorithm for performing that match.  Anyone got
any ideas?

Ian.

-- 
"Don't throw your PC out the window, throw Windows out of
 your PC, and install Linux"
Ian Clarke                    http://www.gnu.demon.co.uk/