應(yīng)用二叉樹解析-XML-表示的函數(shù)計(jì)算表達(dá)式

應(yīng)用二叉樹解析XML表示的函數(shù)計(jì)算表達(dá)式XForms的函數(shù)計(jì)算表達(dá)式簡介XForms是用于XML數(shù)據(jù)處理的Web表單規(guī)范,它允許您將表單的用途和外觀分開?目前W3C組織正在審查XForms1.1的候選工作草案（1.0是正式的Internet推薦標(biāo)準(zhǔn)）。IBM?LotusForms(電子表單領(lǐng)域的杰出產(chǎn)品之一)就是基于XForms和XFDL(ExtensibleFormsDescriptionLanguage)語言的，它把XForms強(qiáng)大的數(shù)據(jù)處理能力和XFDL語言豐富的表示能力緊密的結(jié)合在一起。XForms的數(shù)據(jù)模型（DataModel）封裝了對表單數(shù)據(jù)的一些邏輯處理操作。如清單1所示，xforms:bind元素?fù)碛幸粋€(gè)calculate屬性。該屬性通過函數(shù)計(jì)算表達(dá)式來實(shí)現(xiàn)表單數(shù)據(jù)的處理邏輯。

清單1.XForms的函數(shù)計(jì)算表達(dá)式<xforms:model…><xforms:instance>…</xforms:instance>…<xforms:bindcalculate="../SubTotal+../TaxAmount+../Shipping"nodeset="instance('INSTANCE')/P001/Total"></xforms:bind><xforms:bindcalculate="if(../BudgetMeals!='',../BudgetMeals,'0')-../ActualMeals"nodeset="instance('INSTANCE')/P001/VarianceMeals"></xforms:bind><xforms:bindcalculate="min(../aAccount,../bAccount,../cAccount)"nodeset="instance('INSTANCE')/P001/minAccount"></xforms:bind>…</xforms:model>諸多領(lǐng)域，特別是電子商務(wù)領(lǐng)域，存在很多基于XML語言的產(chǎn)品。企業(yè)集成，數(shù)據(jù)交換以及轉(zhuǎn)換工具等都涉及XML2XML的轉(zhuǎn)換工作。那么如何解析轉(zhuǎn)換另一種XML表示的函數(shù)計(jì)算表達(dá)式呢？本文試圖解決這一問題。回頁首簡單介紹另一種的XML表示的函數(shù)計(jì)算表達(dá)式在清單2中，我們簡單介紹了另一種XML表示的函數(shù)計(jì)算表達(dá)式，其應(yīng)用于一款基于XML語法的電子表單產(chǎn)品中。窺豹可見一斑，本文同樣適用于其它基于XML語法的函數(shù)計(jì)算表達(dá)式。

清單2.XForms的函數(shù)計(jì)算表達(dá)式…<calculation><funcname="IfThen"><funcname="Less"><cellname="DateTo"/><cellname="DateFrom"/></func><funcname="Alert"><booleanvalue="False"/><stringvalue="ThisdatemustcomeafterthedateyouhaveenteredintheDateFromfield"/></func></func><plainText>IfDateTo<DateFromThenFalseWithAlert"ThisdatemustcomeafterthedateyouhaveenteredintheDateFromfield"End</plainText></calculation><calculation><funcname="Min"><funcname="Abs"><cellname="Summary"/></func><funcname="Subtract"><cellname="Demo1"><cellname="Demo2"></func><numbervalue="100"/></func><plainText>Min(Abs(Summary),Demo1-Demo2,100)</plainText></calculation>…在清單2中<func>標(biāo)簽用以標(biāo)識函數(shù)或操作符。其name的屬性值既是函數(shù)或操作符的名稱。<cell>標(biāo)簽，讀者可以理解為用以標(biāo)識函數(shù)計(jì)算表達(dá)式中的變量；而<number>,<string>等標(biāo)簽則是標(biāo)識函數(shù)計(jì)算表達(dá)式中的常量內(nèi)容。當(dāng)我們需要解析函數(shù)計(jì)算表達(dá)式的時(shí)候,我們都有什么辦法呢？比如在上面的代碼片段中，直接解析<plainText>元素的內(nèi)容似乎是一個(gè)辦法。直接解析<plainText>Min(Abs(Summary),Demo1-Demo2,100)</plainText>就已經(jīng)得到了正確的結(jié)果。然而，解析含有大量嵌套的條件判斷語句的函數(shù)計(jì)算表達(dá)式，如解析第一個(gè)<plainText>元素中的內(nèi)容就變得非常困難了。當(dāng)我們要想進(jìn)一步分析并處理<plainText>元素中的函數(shù)計(jì)算表達(dá)式的時(shí)候，表達(dá)式已經(jīng)丟失了很多重要的原始信息（比如說類型信息），這樣處理起來就難上加難了。有什么更好的辦法么？我們可以嘗試解析除了<plainText>元素以外的以<calculation>元素為根的XML代碼片段中的信息?；仨撌捉⒂靡越馕龊瘮?shù)計(jì)算表達(dá)式的二叉樹數(shù)據(jù)結(jié)構(gòu)模型仔細(xì)分析一下清單2所示的函數(shù)計(jì)算表達(dá)式，我們不難得出其數(shù)據(jù)結(jié)構(gòu)模型，如圖1所示:

圖1.函數(shù)計(jì)算表達(dá)式的樹模型

我們可以通過XML解析器（DOM,SAX,StAXetc.）解析XML得到基于以樹為數(shù)據(jù)結(jié)構(gòu)的內(nèi)存模型。但是遍歷以二叉樹為數(shù)據(jù)結(jié)構(gòu)的內(nèi)存模型要比以樹為數(shù)據(jù)結(jié)構(gòu)的內(nèi)存模型更方便明了（讀者更為熟悉）。在圖2中，我們把以樹為數(shù)據(jù)結(jié)構(gòu)的模型轉(zhuǎn)換為對應(yīng)的以二叉樹為數(shù)據(jù)結(jié)構(gòu)的模型（結(jié)點(diǎn)的孩子結(jié)點(diǎn)為該結(jié)點(diǎn)的左孩子結(jié)點(diǎn)；結(jié)點(diǎn)的兄弟結(jié)點(diǎn)為該結(jié)點(diǎn)的右孩子結(jié)點(diǎn)）。

圖2.函數(shù)計(jì)算表達(dá)式的二叉樹（BinTree）模型

清單3.XML結(jié)點(diǎn)對應(yīng)的內(nèi)存模型publicclassCalNode{publicCalNodeleft;publicCalNoderight;privateStringvalue;privateStringtype;//Threekindsoftype:cell,func,constpublicCalNode(Stringtype,Stringvalue){this.type=type;this.value=value;}publicCalNode(CalNodeleft,Stringtype,Stringvalue,CalNoderight){this.left=left;this.type=type;this.value=value;this.right=right;}publicStringgetValue(){returnvalue;}publicvoidsetValue(Stringvalue){this.value=value;}publicStringgetType(){returntype;}}在清單3中，我們創(chuàng)建XML結(jié)點(diǎn)對應(yīng)的內(nèi)存模型類——CalNode。該類非常簡單，包括左孩子結(jié)點(diǎn)，右孩子結(jié)點(diǎn)，結(jié)點(diǎn)本身的值以及結(jié)點(diǎn)的類型。根據(jù)這種函數(shù)計(jì)算表達(dá)式所涉及的XML元素的標(biāo)簽值（tag）結(jié)點(diǎn)的類型可分為三種：func，函數(shù)和操作符；cell，函數(shù)計(jì)算表達(dá)式中的變量;const,表達(dá)式中所涉及的字符串或數(shù)值常量（當(dāng)我們遍歷二叉樹的時(shí)候，我們需要根據(jù)結(jié)點(diǎn)的類型進(jìn)行相應(yīng)的邏輯處理。）拿上面的例子來說，當(dāng)解析<funcname=”Min”>的時(shí)候，就生成了一個(gè)值為Min,類型是func的calNode類的實(shí)例對象。

清單4.應(yīng)用DOM解析XML生成以二叉樹為數(shù)據(jù)結(jié)構(gòu)的內(nèi)存模型privateCalNodecreateCalBinTree(Noderoot){StringrootName=ParserHelper.validateSID(XMLUtil.getAttribute((Element)root,Constants.ATTR_NAME));//For<numbervalue=""/>and<stringvalue="xxxx"/>elementswithin<func>if(StringHelper.isEmpty(rootName)){//isEmpty方法判斷是否為空rootName=ParserHelper.validateComputeContent(XMLUtil.getAttribute((Element)root,Constants.ATTR_VALUE));}Stringtype=root.getNodeName();//結(jié)點(diǎn)的類型if(!CalConstants.CELL.equals(type)&&!CalConstants.FUNC.equals(type))type=CalConstants.CONST;//如果類型不是func或cell，則設(shè)置為constCalNoderootNode=newCalNode(null,type,rootName,null);//生成CalNode類的實(shí)例對象NodefirstNode=root.getFirstChild();//拿到結(jié)點(diǎn)root的第一個(gè)孩子（DOMAPI）if(firstNode!=null){//遞歸遍歷第一個(gè)孩子結(jié)點(diǎn)，生成CalNode的實(shí)例對象。CalNodefirstCalNode=createCalBinTree(firstNode);rootNode.left=firstCalNode;//把第一個(gè)孩子結(jié)點(diǎn)設(shè)置為該結(jié)點(diǎn)的左孩子結(jié)點(diǎn)//考慮該結(jié)點(diǎn)的其它孩子結(jié)點(diǎn)NodepNode=firstNode;CalNodeqCalNode=firstCalNode;while(pNode.getNextSibling()!=null){NodenextNode=pNode.getNextSibling();if(nextNode!=null){CalNodenextCalNode=createCalBinTree(nextNode);//遞歸遍歷其它孩子結(jié)點(diǎn)qCalNode.right=nextCalNode;//設(shè)置為其上一個(gè)兄弟結(jié)點(diǎn)的右孩子結(jié)點(diǎn)//loopfororg.w3c.dom.NodepNode=nextNode;//loopforCalNodeqCalNode=nextCalNode;}}}returnrootNode;}如清單4所示，createCalBinTree方法遞歸生成以二叉樹為數(shù)據(jù)結(jié)構(gòu)的內(nèi)存模型（一棵CalNode類的實(shí)例對象樹）。我們只要拿到對象樹的根，就可以對其進(jìn)行遍歷處理了?；仨撌讘?yīng)用棧中序遍歷并預(yù)處理函數(shù)計(jì)算表達(dá)式清單5是一個(gè)使用棧的二叉樹中序遍歷算法。GoFarLeft函數(shù)用來返回當(dāng)前結(jié)點(diǎn)t的最左孩子結(jié)點(diǎn)。

清單5.二叉樹中序非遞歸算法（應(yīng)用棧）privateTreeNode<Elem>GoFarLeft(TreeNode<Elem>t,Stack<TreeNode<Elem>>S){if(t==null)returnnull;while(t.left!=null){S.push(t);t=t.left;}returnt;}//inorderiterativescanprivatevoidInorder_I(TreeNode<Elem>t,voidvisit(Elemc)){Stack<TreeNode<Elem>>S=newStack<TreeNode<Elem>>();t=GoFarLeft(t,S);//continueuntiltisNULLwhile(t!=null){visit(t.data);if(t.right!=null)t=GoFarLeft(t.right,S);elseif(!S.isEmpty())t=S.pop();elset=null;//wearedone}}在本文中，我們應(yīng)用此算法預(yù)處理函數(shù)表達(dá)式。比如，我們想把函數(shù)表達(dá)式轉(zhuǎn)換成XForms的函數(shù)表達(dá)式，而我們在遍歷此二叉樹的過程中，發(fā)現(xiàn)某一個(gè)函數(shù)在XForms規(guī)范中是不支持的，比如上面清單1中的Alert函數(shù)，那么我們就可以結(jié)束此此遍歷操作。當(dāng)然，更多的預(yù)處理情況是根據(jù)業(yè)務(wù)邏輯的實(shí)際需要。比如本文的函數(shù)轉(zhuǎn)換邏輯，我們希望知道函數(shù)表達(dá)式是否包含些特殊的函數(shù)，比如說Sum函數(shù)，此函數(shù)的包含與否直接影響處理邏輯的實(shí)現(xiàn)?；仨撌字行蚍菞＿f歸遍歷并生成XForms函數(shù)計(jì)算表達(dá)式在應(yīng)用清單5的非遞歸算法預(yù)處理函數(shù)計(jì)算表達(dá)式之后，我們要應(yīng)用中序遍歷的遞歸算法真正處理和解析函數(shù)計(jì)算表達(dá)式。在解析的過程中，加入XForms函數(shù)計(jì)算表達(dá)式的相關(guān)邏輯，從而完成解析轉(zhuǎn)換工作。在圖3中，我們應(yīng)用流程圖來描述中序非棧遞歸遍歷的解析處理過程。

圖3.解析處理函數(shù)計(jì)算機(jī)表達(dá)式的流程圖

如上圖所示，流程圖根據(jù)rootNode的值是否為函數(shù)，操作符而分為三部分。第一部分就是對函數(shù)計(jì)算表達(dá)式中的函數(shù)進(jìn)行處理。第二部分就是遞歸處理表達(dá)式中的操作符。最后處理表達(dá)式中的常量和變量。其源代碼如下：

清單6.中序非棧遞歸遍歷并解析函數(shù)表達(dá)式publicvoidcreateXFormsBinding(CalNoderootNode,StringBufferstr){//參數(shù)str用來存放解析結(jié)果if(rootNode==null){//結(jié)點(diǎn)為空，返回return;}StringfoName=rootNode.getValue();//獲取結(jié)點(diǎn)的值//如果類型是func,并且是合法的函數(shù)if(rootNode.getType().equals(CalConstants.FUNC)&&FunctionConstants.isValidFNFunction(foName)){if(rootNode.left==null){//該結(jié)點(diǎn)的左孩子結(jié)點(diǎn)是空的時(shí)候，邏輯操作如下：if(FunctionConstants.NOW.equals(foName)){str.append("now()");}elseif(…){…}return;}else{//該結(jié)點(diǎn)是帶有參數(shù)的函數(shù)//特殊函數(shù)的處理（如：IfThen和IFT）if(FunctionConstants.IFTHEN.equals(foName)||FunctionConstants.IFT.equals(foName)){…return;}elseif(…){//其它特殊的函數(shù)的處理邏輯…return;}else{//非特殊函數(shù)的處理str.append(FunctionConstants.getMappedFunction(foName)+"(");//$NON-NLS-1$//加左括號//遞歸調(diào)用，用以處理函數(shù)的參數(shù)createXFormsBinding(rootNode.left,str);}}//右孩子信息CalNodep=rootNode.left;CalNodeq=null;if(p!=null)q=rootNode.left.right;while(p!=null&&q!=null){str.append(",");//$NON-NLS-1$//參數(shù)用逗號分隔createXFormsBinding(q,str);//遞歸調(diào)用，處理該參數(shù)q=q.right;}//加右括號str.append(")");//$NON-NLS-1$//如果類型是func,并且是合法的操作符}elseif(rootNode.getType().equals(CalConstants.FUNC)&&OperatorConstants.isValidFNOperator(foName)){//若沒有左孩子結(jié)點(diǎn)，返回if(rootNode.left==null){return;}//如果是乘，除以及求模等操作符，需要進(jìn)一步判斷，根據(jù)需要對左右孩子樹加括號if(OperatorConstants.DIV.equals(foName)||OperatorConstants.MULTIPLY.equals(foName)||…){//處理操作符的左孩子樹if(OperatorConstants.isValidFNOperator(rootNode.left.getValue())&&…){str.append("(");//$NON-NLS-1$createXFormsBinding(rootNode.left,str);str.append(")");//$NON-NLS-1$}else{createXFormsBinding(rootNode.left,str);}//取操作符的名字str.append(""+OperatorConstants.getMappedXFDLOperator(foName)+"");//處理操作符的右孩子樹if(rootNode.left.right!=null&&OperatorConstants.isValidFNOperator(rootNode.left.right.getValue())&&…){str.append("(");//$NON-NLS-1$createXFormsBinding(rootNode.left.right,str);str.append(")");//$NON-NLS-1$}else{createXFormsBinding(rootNode.left.right,str);}}//對%操作符的邏輯處理elseif(OperatorConstants.PERCENT.equals(foName)){…}//對其它特殊操作符的邏輯處理elseif(OperatorConstants.XXX.equals(foName)||…){…}//對非func類型進(jìn)行處理（cell類型以及表達(dá)式中的常量）else{if(rootNode.getType().equals(CalConstants.CELL)){//轉(zhuǎn)成XPATH表達(dá)式的中結(jié)點(diǎn)str.append("../"+foName);//$NON-NLS-1$}else{//表達(dá)式中的常量處理str.append("'"+foName+"'"