Recipe5.6.Performing an In-Order Traversal

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.