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( ) &gt; 1 and position( ) &lt; 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.

n-äres Äquivalent eines Binärbaums

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 &gt; $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() &gt; 2 and position() &lt; 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 &gt; $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