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