Re: matching nested heads
- To: mathgroup at smc.vnet.net
- Subject: [mg36297] Re: [mg36271] matching nested heads
- From: Daniel Lichtblau <danl at wolfram.com>
- Date: Fri, 30 Aug 2002 01:19:23 -0400 (EDT)
- References: <200208290537.BAA08107@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Sidney Cadot wrote:
>
> Hi all,
>
> In order to do some transformations on a tree I need to be able to replace
> an expression with head hdA if and if only its parent has head hdB and its
> grandparent had head hdC. Furthermore, the item itself and its parent may
> have any number sibling elements.
>
> What I do now is the following. Give the expression:
>
> ttexpr = grandparent[
> parent1[grandchild2[], grandchild1[], grandchild4[], grandchild1[]],
> grandchild1[],
> parent2[grandchild2[], grandchild1[], grandchild4[], grandchild1[]]];
>
> I apply a rule:
>
> ttexpr /. {
> grandparent[left1___, parent1[left2___, grandchild1[], right2___],
> right1___] ->
> grandparent[left1, parent1[left2, MATCHED[], right2], right1]}
>
> which gives the desired expression:
>
> grandparent[parent1[grandchild2[], MATCHED[], grandchild4[], grandchild1[]],
> grandchild1[],
> parent2[grandchild2[], grandchild1[], grandchild4[], grandchild1[]]]
>
> But I have the feeling that it should be possible to do this more elegantly.
> Does anybody have an idea in this respect?
>
> Best regards,
>
> Sidney Cadot
I think your technique is fine for small to medium size trees. For large
ones it might be very slow due to all the work of patten matching. If
you anticipate large inputs you might thus want to code a simple
tree-walk using old-fashioned procedural code. Any time you match a
grandparent head, put that subtree onto a stack that enters the next
state, looking for parent nodes, etc.
Daniel Lichtblau
Wolfram Research
- References:
- matching nested heads
- From: Sidney Cadot <sidney@science-and-technology.nl>
- matching nested heads