home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / VSCPPv8.zip / VACPP / IBMCPP / samples / IOC / NARY / NARY.CPP < prev    next >
Text File  |  1995-03-15  |  8KB  |  245 lines
  1. /*************************************************************************
  2.   IBM C/C++ Tools Version 3.00 - Collection Class Library
  3.  (C) Copyright IBM Corporation 1992 ,1995, Licensed Program-Property of
  4.  IBM.  All Rights Reserved.  US Government Users Restricted Rights - Use,
  5.  duplication or disclosure restricted by GSA ADP Schedule Contract with
  6.  IBM Corp.
  7.  *************************************************************************/
  8.  
  9. /*----------------------------------------------------*\
  10. | nary.CPP  -  An example of using an N-ary Tree       |
  11. | Construct a tree for the following expression:       |
  12. |      (8+2) * (2+4) / (7-5) ==> result: 30            |
  13. | This is done explicitly for the following reasons:   |
  14. | - no parser is available                             |
  15. | - program demonstrates the use of some common        |
  16. |   functions for n-ary trees.                         |
  17. | This programm also calculates the result from the    |
  18. | expression. A subtree (with two operands and one     |
  19. | operator) is calculated and replaced by the result.  |
  20. | Note that the code does not respect                  |
  21. | precedence of "/" and "*" over "+" and "-".          |
  22. \*----------------------------------------------------*/
  23.  
  24. #include <itree.h>
  25. #if defined (_SUN)
  26. #include <istring.h>
  27. #else
  28. #include <istring.hpp>
  29. #endif
  30. #include <iostream.h>
  31.  
  32. ////////////////////////////////////////////////////////////
  33. // The tree for this expression looks like follows:       //
  34. //                                                        //
  35. //                              /                         //
  36. //                                                        //
  37. //                     *                -                 //
  38. //                                                        //
  39. //                +         +      7         5            //
  40. //                                                        //
  41. //              8   2     2   4                           //
  42. ////////////////////////////////////////////////////////////
  43.  
  44. typedef ITree <IString, 2> BinaryTree;
  45.  
  46. /*******************  functions  **************************/
  47.  
  48. IBoolean printNode(IString const& node, void* dummy)
  49. /**** prints one node of an n-ary tree ****/
  50.  {
  51.    cout << node << "|";
  52.    return  True;
  53.  }
  54.  
  55. void prefixedNotation(BinaryTree const& naryTree)
  56. /* prints an n-ary tree in prefixed notation */
  57.  {
  58.    naryTree.allElementsDo(printNode , IPreorder);
  59.    cout << endl;
  60.  }
  61.  
  62.  
  63. void identifyChildren  (IString &child1,
  64.                         IString &child2,
  65.                         BinaryTree &binTree,
  66.                         ITreeCursor &binTreeCursor)
  67. /********************************************************/
  68. /****     identifies the children of a node          ****/
  69. /********************************************************/
  70.  {
  71.  
  72.   binTree.setToNext(binTreeCursor, IPreorder);
  73.   child1 = binTree.elementAt(binTreeCursor);
  74.   binTree.setToNextExistingChild(binTreeCursor);
  75.   child2 = binTree.elementAt(binTreeCursor);
  76.   binTree.setToParent(binTreeCursor);
  77.  }
  78.  
  79.  
  80. IBoolean isNumber(IString child)
  81. /**********************************************************/
  82. /****  checks whether a node contains a number         ****/
  83. /**********************************************************/
  84. {
  85.   if ((child != '+') &&
  86.       (child != '-') &&
  87.       (child != '*') &&
  88.       (child != '/'))
  89.      { return True; }
  90.   else { return False; }
  91. }
  92.  
  93.  
  94. void lookForNextOperator(BinaryTree &binTree,
  95.                          ITreeCursor &binTreeCursor)
  96. /********************************************************/
  97. /****  looks for the next operator in the tree       ****/
  98. /********************************************************/
  99.  
  100.  {
  101.    IBoolean operatorFound = False;
  102.  
  103.    do
  104.    {
  105.     if (!isNumber(binTree.elementAt(binTreeCursor)))
  106.        {
  107.          operatorFound = True;
  108.        }
  109.     else
  110.        {
  111.          binTree.setToNext(binTreeCursor, IPreorder);
  112.        }
  113.    }
  114.    while (! operatorFound);
  115.  }
  116.  
  117.  
  118. void calculateSubtree(double &result, double &operand1,
  119.                       double &operand2, IString &operatorSign)
  120. /**********************************************************/
  121. /**** calculates the result from a subtree in the      ****/
  122. /****                complete tree                     ****/
  123. /**********************************************************/
  124.  {
  125.    switch (*(char*)operatorSign)
  126.      {
  127.        case '+':
  128.        result = operand1+operand2;
  129.        break;
  130.        case '-':
  131.        result = operand1-operand2;
  132.        break;
  133.        case '/':
  134.        result = operand1/operand2;
  135.        break;
  136.        case '*':
  137.        result = operand1*operand2;
  138.        break;
  139.      } /* endswitch */
  140.  }
  141.  
  142.  
  143. /************************ main ****************************/
  144. int main ()
  145.  
  146.  {
  147.  
  148.   //////////////////////////////////////////////////////////
  149.   // Constructing the tree:                               //
  150.   //////////////////////////////////////////////////////////
  151.  
  152.   BinaryTree  binTree;
  153.   BinaryTree::Cursor binTreeCursor(binTree);
  154.   BinaryTree::Cursor binTreeSaveCursor(binTree);
  155.  
  156.  
  157.   binTree.addAsRoot("/");
  158.   binTree.setToRoot(binTreeCursor);
  159.   binTree.addAsChild(binTreeCursor, 1, "*");
  160.   binTree.setToChild(1, binTreeCursor);
  161.   binTree.addAsChild(binTreeCursor, 1, "+");
  162.   binTree.setToChild(1, binTreeCursor);
  163.   binTree.addAsChild(binTreeCursor, 1, "8");
  164.   binTree.addAsChild(binTreeCursor, 2, "2");
  165.   binTree.setToParent(binTreeCursor);
  166.   binTree.addAsChild(binTreeCursor, 2, "+");
  167.   binTree.setToChild(2, binTreeCursor);
  168.   binTree.addAsChild(binTreeCursor, 1, "2");
  169.   binTree.addAsChild(binTreeCursor, 2, "4");
  170.   binTree.setToRoot(binTreeCursor);
  171.   binTree.addAsChild(binTreeCursor, 2, "-");
  172.   binTree.setToChild(2, binTreeCursor);
  173.   binTree.addAsChild(binTreeCursor, 1, "7");
  174.   binTree.addAsChild(binTreeCursor, 2, "5");
  175.  
  176.  
  177.   //////////////////////////////////////////////////////////
  178.   // print complete tree in prefix notation               //
  179.   //////////////////////////////////////////////////////////
  180.  
  181.   cout << "Printing the original tree in prefixed notation:"
  182.        << endl;
  183.   prefixedNotation(binTree);
  184.   cout << " " << endl;
  185.  
  186.   //////////////////////////////////////////////////////////
  187.   // Calculate tree                                       //
  188.   //////////////////////////////////////////////////////////
  189.  
  190.   double      operand1 = 0;
  191.   double      operand2 = 0;
  192.   double      result = 0;
  193.   INumber     replacePosition;
  194.   IString     operatorSign, child1, child2;
  195.  
  196.   binTree.setToRoot(binTreeCursor);
  197.   do
  198.   {
  199.    lookForNextOperator(binTree, binTreeCursor);
  200.    operatorSign = binTree.elementAt(binTreeCursor);
  201.    identifyChildren  (child1, child2, binTree, binTreeCursor);
  202.    if ((isNumber(child1)) && (isNumber(child2)))
  203.       {
  204.         operand1 = child1.asDouble();
  205.         operand2 = child2.asDouble();
  206.         calculateSubtree(result, operand1, operand2,
  207.                          operatorSign);
  208.         if (binTree.numberOfElements() > 3)
  209.         {
  210.         // if tree contains more than three elements, replace
  211.         // the calculated subtree by its result like follows:
  212.          //save the cursor, because it will become invalidated after
  213.          //removeSubtree
  214.          binTreeSaveCursor = binTreeCursor;
  215.          binTree.setToParent(binTreeSaveCursor);
  216.          replacePosition = binTree.position(binTreeCursor);
  217.          binTree.removeSubtree(binTreeCursor);
  218.          binTree.addAsChild(binTreeSaveCursor,
  219.                             replacePosition,
  220.                             (IString)result);
  221.         cout << "Tree with calculated subtree replaced: "
  222.              << endl;
  223.         prefixedNotation(binTree);
  224.         binTree.setToRoot(binTreeCursor);
  225.         }
  226.         else
  227.         {
  228.         // if tree contains root with two children only,replace
  229.         // this calculated subtree by its result like follows:
  230.          binTree.removeAll();
  231.          binTree.addAsRoot(IString(result));
  232.          cout << "Now the tree contains the result only:" << endl;
  233.          prefixedNotation(binTree);
  234.         }
  235.       }
  236.    else
  237.       {
  238.       binTree.setToNext(binTreeCursor, IPreorder);
  239.       }
  240.   }
  241.   while (binTree.numberOfElements() > 1);
  242.  
  243.   return 0;
  244.  }
  245.