O'Reilly logo

XSLT Cookbook by Sal Mangano

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Performing an In-Order Traversal

Problem

You have an XML document or fragment that represents an expression to be processed in-order.

Solution

An in-order traversal is most applicable to a binary tree. The general form of the algorithm in this case follows:

<xsl:template match="node(  )">
     <!--Process left subtree -->
     <xsl:apply-templates select="*[1]"/>
     
     <!-- Do something with current node -->
     
     <!--Process right subtree --> 
     <xsl:apply-templates select="*[2]"/>
</xsl:template>

However, in-order traversal can extend to n-ary trees with the following algorithm:

<xsl:template match="node(  )">
     <xsl:variable name="current-node" select="."/>
     <!--Process left subtree -->
     <xsl:apply-templates select="*[1]"/>
     
     <!-- Do something with $current-node -->
   
     <!-- Apply recursively to middle children     
     <xsl:for-each select="*[position(  ) > 1 and position(  ) &lt; last(  )">
          
          <!-- Process "left" subtree --> 
          <xsl:apply-templates select="."/>
   
          <!--Do something with $current-node -->
   
     </xsl:for-each>
   
     <!--Process right subtree -->
     <xsl:apply-templates select="*[last(  )]"/>
   
</xsl:template>

The rational behind this algorithm can be better understood by considering Figure 4-1, which shows the binary equivalent of an n-ary tree. The generalized n-ary in-order traversal produces the same result as the binary in-order traversal on the binary equivalent tree.

N-ary to binary tree equivalent

Figure 4-1. N-ary to binary tree equivalent

Discussion

This form of traversal has a much narrower range of applicability then other traversal examples in this chapter. One notable application, shown in Example 4-23 and Example 4-24, is as a component of a stylesheet that converts MathML markup to C or Java-style infix expressions. Example 4-25 shows the output.

Example 4-23. Input 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>

Example 4-24. In-order traversal of MathML fragment to produce a C expression

<?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="*"/>
   
     <!-- Table to convert from MathML operation names to C operators -->
     <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"/>
     
     <!-- load operation conversion table into a variable -->               
     <xsl:variable name="ops" select="document('')/*/C:operator"/>
          
     <xsl:template match="apply"> 
          <xsl:param name="parent-precedence" select="0"/>
          
          <!-- Map mathML operation to operator name and precedence -->
          <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"/>
          
          <!-- Parenthises required if if the precedence of the containing
           expression is greater than current sub-expression -->
          <xsl:if test="$parent-precedence > $c-opPrecedence">
          <xsl:text>(</xsl:text>
          </xsl:if>
   
          <!-- Recursively process the left sub-tree which is at 
               position 2 in MathML apply element-->          
          <xsl:apply-templates select="*[2]">
               <xsl:with-param name="parent-precedence" 
                    select="$c-opPrecedence"/>
          </xsl:apply-templates>
          
          <!-- Process the current node (i.e. the operator at 
               position 1 in MathML apply element -->
          <xsl:value-of select="concat(' ',$c-opName,' ')"/>
          
          <!-- Recursively process middle children -->
          <xsl:for-each select="*[position(  )>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>
          
          <!-- Recursively process right subtree-->
          <xsl:apply-templates select="*[last(  )]">
               <xsl:with-param name="parent-precedence" 
                         select="$c-opPrecedence"/>
          </xsl:apply-templates>
   
          <!-- Parenthises required if if the precedence of the containing
               expression is greater than current sub-expression -->
          <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>

Example 4-25. Output

y - 2 + 4 * (x + 1) + 8 =  = 0

Obviously, this stylesheet is not a full-fledged MathML-to-C translator. However, Chapter 9 discusses this problem more thoroughly.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required