Recipe 5.6. 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 rationale behind this algorithm can be better understood by considering Figure 5-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.

Figure 5-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 5-8 and Example 5-9, is as a component of a stylesheet that converts MathML markup to C or Java-style infix expressions. Example 5-10 shows the output.

Example 5-10. 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 5-11. 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"/>
          
          <!-- Parenthesis required 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>
   
          <!-- Parenthesis required 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 5-12. 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.