Introduction to Pointers, Structures and Linked-Lists Part 11

Introduction to Pointers, Structures and Linked-Lists Part 11
Brief Introduction to Polymorphism
by Chris Bennett aka Dwarfsoft

So now that we have had an introduction to Inheritance, we can start to look at what this allows us to do. To explain this I will start using more abstract themes. The way this concept was taught to me was using math as an example in a reverse polish calculator (Feel free to look this up, as its interesting from a Finite State Machine and Scripting perspective).

So what we started with was an Equation was equal to some data (numbers) with operations used to transform them into a solution. Let us have a look at what we need from our base class of cExpression.

class cExpression
{
public: 
   virtual int Evaluate()=0;
};

Welcome to the virtual keyword. our cExpression class has become an abstract base class, so lets find out why. More importantly lets find out what is meant by an abstract base class.

Abstraction in this sense is not exactly the same as when I was talking about data abstraction. Here by abstraction we basically are saying cExpression is defining how its child classes will operate, but it itself does not actually do anything. Think of an abstract base class as a framework for future classes. Now, on to the inheritance.

class cConstant : public cExpression
{
public: 
   cConstant(int NewValue)
   {
      value = NewValue;
   }

   int Evaluate()
   {
      return value;
   } 
   void Set(int val)
   {
      value = val;
   }
private:
   int value;
};

Not coming together yet? Well, we are not yet halfway there.

class cAddition : public cExpression
{
public:
   cAddition(cExpression *left, cExpression *right) : Left(NULL), Right(NULL)
   {
      Left = left;
      Right = right;
   }
   cAddition(int left, int right) : Left(NULL), Right(NULL)
   {
      Left = new cConstant(left);
      Right = new cConstant(right);
   }
   ~cAddition()
   {
      if (Left) delete Left;
      if (Right) delete Right;
   }
   int Evaluate()
   {
      int Result = 0;
      if (Left) Result = Left->Evaluate();
      if (Right) Result += Right->Evaluate();
      return Result;
   } 
private: 
   cExpression * Left,* Right;
};

What we are setting up here is a method of being able to use each class (the base class tells us how to access each classes members) without having to know what kind of class we have. When looking at only two classes this is hard to appreciate as useful, but I will start explaining alternatives soon, and then it will become apparent as to how useful this method of using classes can actually be.

class cMultiplication : public cExpression
{
public:
   cMultiplication(cExpression *left, cExpression *right) : Left(NULL), Right(NULL)
   {
      Left = left;
      Right = right;
   }
   cMultiplication(int left, int right) : Left(NULL), Right(NULL)
   {
      Left = new cConstant(left);
      Right = new cConstant(right);
   }
   ~cMultiplication()
   {
      if (Left) delete Left;
      if (Right) delete Right;
   } 
   int Evaluate()
   {
      int Result = 0;
      if (Left) Result = Left->Evaluate();
      if (Right) Result *= Right->Evaluate();
      return Result;
   } 
private: 
   cExpression * Left,* Right;
};


class cDivision : public cExpression
{
public:
   cDivision(cExpression *left, cExpression *right) : Left(NULL), Right(NULL)
   {
      Left = left;
      Right = right;
   }
   cDivision(int left, int right) : Left(NULL), Right(NULL)
   {
      Left = new cConstant(left);
      Right = new cConstant(right);
   }
   ~cDivision()
   {
      if (Left) delete Left;
      if (Right) delete Right;
   } 
   int Evaluate()
   {
      int Result = 0;
      int temp = 0;
      int div = 0;
      if (Left) temp = Left->Evaluate();
      if (Right)
      {
         div = Right->Evaluate();
         // Calculate the integer Division
         while ((temp >= div) && div)
         { 
            temp-=div;
            ++Result;
         }
         // Round Up if we have to
         if (temp >= (div-temp))
            ++Result; 
      } else 
         Result = 0;
      return Result;
   } 
private: 
   cExpression * Left,* Right;
};


class cSubtraction : public cExpression
{
public:
   cSubtraction(cExpression *left, cExpression *right) : Left(NULL), Right(NULL)
   {
      Left = left;
      Right = right;
   }
   cSubtraction(int left, int right) : Left(NULL), Right(NULL)
   {
      Left = new cConstant(left);
      Right = new cConstant(right);
   }
   ~cSubtraction()
   {
      if (Left) delete Left;
      if (Right) delete Right;
   } 
   int Evaluate()
   {
      int Result = 0;
      if (Left) Result = Left->Evaluate();
      if (Right) Result -= Right->Evaluate();
      return Result;
   } 
private: 
   cExpression * Left,* Right;
};

That sets up our basic arithmetic operators. I actually went in and did hand division just to ensure that I have rounding up and it is proper integer division. Now lets see how we can use this.

int func()
{
   cExpression *exp1,*exp2,*exp3;
   exp1 = new cAddition(5,7);
   exp2 = new cMultiplication(3,9);
   exp3 = new cSubtraction(exp2,exp1);
   printf("%d", exp3->Evaluate());
   delete exp3;
};

Since I think we can get a much simpler solution out of the code so if I just add a couple more functions to cAddition for an example, you can do the copy paste work to get that working in the other classes.

 cAddition(cExpression *left, int right) : Left(NULL), Right(NULL)
{
   Left = left;
   Right = new cConstant(right);
}
cAddition(int left, cExpression *right) : Left(NULL), Right(NULL)
{
   Left = new cConstant(left);
   Right = right;
}

These are two additional constructor functions. Now that they are all through our classes we can do creation as easy as the following:

cExpression *exp = new cAddition(1, new cDivision(new cMultiplication(2,5),4));

This is all well and good, but what good is an equation if there is no way of expressing it before evaluating it?

char *ToString()
{
   char *tmp = new char[10];
   itoa(value, tmp, 10);
   return tmp;
}

char *ToString()
{
   char *l,*r,*tmp;
   l = Left->ToString();
   r = Right->ToString();
   tmp = new char [strlen(l)+strlen(r)+6];
   strcpy(tmp, "(");
   strcat(tmp, l);
   strcat(tmp, " + ");
   strcat(tmp, r);
   strcat(tmp, ")");
   if (l) delete [] l;
   if (r) delete [] r;
   return tmp;
}

The first block is for the cConstant class, and the second can be modified for all the classes (just by changing the strcat(tmp, " + "); to a more relevant arithmetic operator. Then we can change our printout to be:

   ...
   char *str = exp3->ToString();
   printf("%s = %d", str, exp3->Evaluate()); 
   delete [] str;
   ...

This gives us a functional calculator for evaluating expressions. For a little homework you might want to write a program that can read in expressions. As for the next article I will be reviewing those parentheses that we need to insert in our expression printout and how they can be avoided entirely by using a reverse polish calculator. Now here is some thinking material from my code:

exp3 = new cAddition(1, new cDivision(new cMultiplication(2,new cSubtraction(20,5)),4));

Which gives the output:

(1 + ((2 * (20 - 5)) / 4)) = 9
1 2 20 5 - * 4 / + = 9

Note: it is supposed to round up from 8.5 to 9.

Cheers, Chris.

Discuss this article in the forums

Date this article was posted to GameDev.net: 9/30/2004
(Note that this date does not necessarily correspond to the date the article was written)

See Also:
General