Durchführen eines In-Order Traversal
(Auszug aus "XSLT Kochbuch" von Sal Mangano)
Problem
Sie haben ein XML-Dokument oder -Fragment, das einen Ausdruck repräsentiert, der in-order verarbeitet werden muss.
Lösung
Ein In-Order Traversal wird meist auf einen Binärbaum angewandt. Die allgemeine Form des Algorithmus in diesem Fall folgt:
<xsl:template match="node( )">
<!--Verarbeiten des linken Teilbaums -->
<xsl:apply-templates select="*[1]"/>
<!-- Irgendetwas mit dem aktuellen Knoten tun -->
<!--Verarbeiten des rechten Teilbaums -->
<xsl:apply-templates select="*[2]"/>
</xsl:template>
Mit dem folgenden Algorithmus kann ein In-Order Traversal jedoch auf n-äre Bäume ausgeweitet werden:
<xsl:template match="node( )">
<xsl:variable name="current-node" select="."/>
<!--Verarbeiten des linken Teilbaums -->
<xsl:apply-templates select="*[1]"/>
<!-- Irgendetwas mit $current-node tun -->
<!-- Rekursiv auf die mittleren Kinder anwenden -->
<xsl:for-each select="*[position( ) > 1 and position( ) < last( )">
<!-- Verarbeiten des "linken" Teilbaums -->
<xsl:apply-templates select="."/>
<!--Irgendetwas mit $current-node tun -->
</xsl:for-each>
<!--Verarbeiten des rechten Teilbaums -->
<xsl:apply-templates select="*[last( )]"/>
</xsl:template>
Das Grundprinzip hinter diesem Algorithmus wird besser verständlich, wenn Sie sich die folgende Abbildung anschauen. Diese Abbildung zeigt das binäre Äquivalent eines n-ären Baums. Das verallgemeinerte n-äre In-Order Traversal erzeugt das gleiche Ergebnis wie das binäre In-Order Traversal auf dem binären, äquivalenten Baum.
Abbildung: N-äres Äquivalent eines Binärbaums.
Diskussion
Diese Form des Durchlaufens hat eine deutlich eingeschränktere Anwendbarkeit als die anderen Traversal-Beispiele in diesem Kapitel. Eine nennenswerte Anwendung, die auch in den folgenden beiden Beispielien gezeigt wird, ist die einer Komponente eines Stylesheets, das MathML-Auszeichnungen in C- oder Java-artige Infix-Ausdrücke umwandelt.
Beispiel: Eingegebenes MathML-Fragment.
<apply>
<eq/>
<apply>
<plus/>
<apply>
<minus/>
<ci>y</ci>
<cn>2</cn>
</apply>
<apply>
<times/>
<cn>4</cn>
<apply>
<plus/>
<ci>x</ci>
<cn>1</cn>
</apply>
</apply>
<cn>8</cn>
</apply>
<cn>0</cn>
</apply>
Beispiel: In-Order Traversal des MathML-Fragments zum Erzeugen eines C-Ausdrucks.
<?xml version="1.0" encoding="UTF-8"?>
<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform" xmlns:C="http://www.ora.com/XSLTCookbook/nampespaces/C">
<xsl:output method="text"/>
<xsl:strip-space elements="*"/>
<!-- Tabelle zum Umwandeln der Namen der MathML-Operation in C-Operatoren -->
<C:operator mathML="plus" c="+" precedence="2"/>
<C:operator mathML="minus" c="-" precedence="2"/>
<C:operator mathML="times" c="*" precedence="3"/>
<C:operator mathML="div" c="/" precedence="3"/>
<C:operator mathML="mod" c="%" precedence="3"/>
<C:operator mathML="eq" c="= =" precedence="1"/>
<!-- Laden der Tabelle mit den Operationskonvertierungen in eine Variable -->
<xsl:variable name="ops" select="document('')/*/C:operator"/>
<xsl:template match="apply">
<xsl:param name="parent-precedence" select="0"/>
<!-- Abbilden der mathML-Operation auf den Operatornamen und die Präzedenz -->
<xsl:variable name="mathML-opName" select="local-name(*[1])"/>
<xsl:variable name="c-opName" select="$ops[@mathML=$mathML-opName]/@c"/>
<xsl:variable name="c-opPrecedence" select="$ops[@mathML=$mathML-opName]/@precedence"/>
<!-- Es sind Klammern erforderlich, wenn die Präzedenz des äußeren Ausdrucks größer ist als die des aktuellen Teilausdrucks -->
<xsl:if test="$parent-precedence > $c-opPrecedence">
<xsl:text>(</xsl:text>
</xsl:if>
<!-- Rekursive Verarbeitung des linken Teilbaums, der sich an Position 2 im MathML-apply-Element befindet-->
<xsl:apply-templates select="*[2]">
<xsl:with-param name="parent-precedence" select="$c-opPrecedence"/>
</xsl:apply-templates>
<!-- Verarbeitung des aktuellen Knotens (d.h. des Operators an Position 1 im MathML-apply-Element) -->
<xsl:value-of select="concat(' ',$c-opName,' ')"/>
<!-- Rekursive Verarbeitung der mittleren Kinder -->
<xsl:for-each select="*[position() > 2 and position() < last()]">
<xsl:apply-templates select=".">
<xsl:with-param name="parent-precedence" select="$c-opPrecedence"/>
</xsl:apply-templates>
<xsl:value-of select="concat(' ',$c-opName,' ')"/>
</xsl:for-each>
<!-- Rekursive Verarbeitung des rechten Teilbaums-->
<xsl:apply-templates select="*[last()]">
<xsl:with-param name="parent-precedence" select="$c-opPrecedence"/>
</xsl:apply-templates>
<!-- Es sind Klammern erforderlich, wenn die Präzedenz des äußeren Ausdrucks größer ist als die des aktuellen Teilausdrucks -->
<xsl:if test="$parent-precedence > $c-opPrecedence">
<xsl:text>)</xsl:text>
</xsl:if>
</xsl:template>
<xsl:template match="ci|cn">
<xsl:value-of select="."/>
</xsl:template>
</xsl:stylesheet>
Beispiel: Ausgabe.
y - 2 + 4 * (x + 1) + 8 = = 0
Offensichtlich handelt es sich bei diesem Stylesheet nicht um einen vollwertigen MathML-zu-C-Übersetzer. Allerdings geht XML abfragen näher auf dieses Problem ein.
<< zurück | vor >> |
Tipp der data2type-Redaktion: Zum Thema XSLT bieten wir auch folgende Schulungen zur Vertiefung und professionellen Fortbildung an: |
Copyright © 2006 O'Reilly Verlag GmbH & Co. KG
Für Ihren privaten Gebrauch dürfen Sie die Online-Version ausdrucken.
Ansonsten unterliegt dieses Kapitel aus dem Buch "XSLT Kochbuch" denselben Bestimmungen, wie die gebundene Ausgabe: Das Werk einschließlich aller seiner Teile ist urheberrechtlich geschützt. Alle Rechte vorbehalten einschließlich der Vervielfältigung, Übersetzung, Mikroverfilmung sowie Einspeicherung und Verarbeitung in elektronischen Systemen.
O'Reilly Verlag GmbH & Co. KG, Balthasarstraße 81, 50670 Köln, kommentar(at)oreilly.de