An ExpressionTree in C++

I implemented an expression tree in Object Oriented Style and that was one of the homework i had for a class at school.I hated it a lot, but finally when completed I liked it a lot, ahhhhhh felt really like i have achieved something. By the way this is a good example of polymorphism and inheritence and the concept of virtual functions and abstract base classes (if you know what I mean ? ) Many of us do all this stuff in school and keep it to school. We never design types like that at work or someone else doesnt because we dont have the time to spend in design (at least nowhere i worked people had the time to design) but oh well !!

The logic is as Follows:

An Expression Tree consists of Nodes.Nodes can be of different types (Operators , Constants , Variables). All nodes can print themselves and allow their derivative to be taken which also is a expression tree . The derivative has to be taken with respect to a variable and the expression tree can be evaluated by plugging in a value of the variable from a look up table or symbol table … 

I am posting the code (of the header file and the driver program)  just in case it interests anyone. Your comments and feedback is welcome and you can get a working copy of code if you want. Leave your email address as a comment and i will send you the copy. This is not finished as i did not implement the destructors but you will get the idea.

#include  <iostream>
#include  <map>
#include  <string>
#include  <math.h>
using  namespace  std;

/******************************************************************************************
Muhammad Asad Siddiqi
Making an Expression Tree Representation, given an expression
This files contains the prototype for following classes
-GenericNode
-VariableNode
-BinaryOperatorNode
– AdditionNode
– SubtractionNode
– MultiplicationNode
– DivisonNode
-UnaryOperatorNode
– NegateNode
– SineNode
– CosNode*******************************************************************************************/

 

class 

 PoorManSymbolTable {
private:
std::map<std::string,
double> symbolTable;
public:
PoorManSymbolTable();
void       InitializeSymbolTable();
double  getSymbolTableEntry(std::string symbol);
};

//——————————————————————————————// This class represents a Generic Node
class GenericNode
{
public:
GenericNode();
virtual double EvaluateNode() = 0;
virtual void     PrintExpression() = 0;
virtual GenericNode *Clone()= 0;
virtual GenericNode* TakeDerivative(std::string variable) = 0;
};
//—————————————————————————————–// This is the node that represents a constant like 15
class ConstantNode : public GenericNode
{
private:
double value;
public:
ConstantNode(
doubleconstant);
double EvaluateNode();
voidPrintExpression();
ConstantNode *Clone();
GenericNode* TakeDerivative(std::string variable);
};

//————————————————————————————
// This node represents a Variable like ‘X’

class VariableNode : public GenericNode
{
private:
std::string symbol;
PoorManSymbolTable symbolTable;
public:
VariableNode(std::string variable);
double  EvaluateNode();
void       PrintExpression();
VariableNode *Clone();
GenericNode* TakeDerivative(std::string variable);
};
 

//—————————————————————————————–// This is the node that represents a binary Operator ( + , – , * )

class BinaryOperatorNode : public GenericNode
{
protected:
GenericNode *left;
GenericNode *right;
public:
BinaryOperatorNode(v
oid);
BinaryOperatorNode(GenericNode *leftOperand , GenericNode *rightOperand);
GenericNode* TakeDerivative(std::string variable);
};

//—————————————————————————————–// This is the node that represents a unary Operator ( + , – , * )

class UnaryOperatorNode : public GenericNode
{
protected:
GenericNode *childNode;
public:
UnaryOperatorNode(
void);
GenericNode* TakeDerivative(std::string variable);
};

//—————————————————————————————–// This is the class that represents a + operator 

class

AdditionNode : public BinaryOperatorNode
{
public:
AdditionNode(GenericNode *leftOperand , GenericNode *rightOperand);
// realize the pure virtual function
double EvaluateNode();
void PrintExpression();
AdditionNode *Clone();
GenericNode* TakeDerivative(std::string variable);
};

//—————————————————————————————–
// This is the class that represents a – operator

class SubtractionNode : public BinaryOperatorNode
{
public:
SubtractionNode(GenericNode *leftOperand , GenericNode *rightOperand);
// realize the pure virtual function
double EvaluateNode();
void PrintExpression();
SubtractionNode *Clone();
GenericNode* TakeDerivative(std::string variable);
};

//—————————————————————————————–// This is the class that represents a * operator
class MultiplicationNode : public BinaryOperatorNode
{
public:
MultiplicationNode(GenericNode *leftOperand , GenericNode *rightOperand);
// realize the pure virtual function
double EvaluateNode();
void     PrintExpression();
MultiplicationNode *Clone();
GenericNode* TakeDerivative(std::string variable);
};
//—————————————————————————————–// This is the class that represents a / operator
class DivisonNode : public BinaryOperatorNode
{
public:
DivisonNode(GenericNode *leftOperand , GenericNode *rightOperand);
// realize the pure virtual function
double EvaluateNode();
void      PrintExpression();
DivisonNode *Clone();
GenericNode* TakeDerivative(std::string variable);
};

//—————————————————————————————–// This would be used to negate a node
// Return a negative when evaluate is called

 

class NegateNode: public UnaryOperatorNode
{
public:
NegateNode(GenericNode *argChildNode);
double EvaluateNode();
NegateNode *Clone();
void PrintExpression();
GenericNode* TakeDerivative(std::string argSymbol);
};

// ————————————————————————————–
// This would be used to create a Sine Operator in the Expression Tree
// It is a unary operation and derivative is a cos Node
class SineNode : public UnaryOperatorNode
{
public:
SineNode(GenericNode *argChildNode);
double EvaluateNode();
void     PrintExpression();
SineNode *Clone();
GenericNode* TakeDerivative(std::string argSymbol);
};

//—————————————————————————————–// This would be used to create a Cos Operator in the Expression Tree// It is a unary operation and uses negation in derivative

class CosNode : public UnaryOperatorNode
{
public:
CosNode(GenericNode *argChildNode);
double EvaluateNode();
void      PrintExpression();
CosNode *Clone();
GenericNode* TakeDerivative(std::string argSymbol);
};

// The driver program

int

_tmain(int argc, _TCHAR* argv[])
{
GenericNode *objGenericNode , *cloneTest , *derivativeResult;
ConstantNode *var1 =
new ConstantNode(45);
ConstantNode *var2 =
new ConstantNode (25);
VariableNode *var3 =
new VariableNode(“Xray”);
VariableNode *var4 =
new VariableNode(“Yellow”);
objGenericNode =
new MultiplicationNode(new AdditionNode(var3,var4),new CosNode(var2));
cloneTest = objGenericNode->Clone();
cloneTest->PrintExpression();
cout << endl <<
“Printing Derivative of Expression Tree … “ << endl;
derivativeResult = cloneTest->TakeDerivative(
“Xray”);
derivativeResult->PrintExpression();
return 0;
}

Notely: This is not about parsing an expression by putting it on 2 stacks using Infix or Postfix notation . This is an implementation of an expression tree where the structure of the tree is known 🙂 . I could not post the implementation but would be provided on request .

Advertisements

3 Comments

Filed under 1

3 responses to “An ExpressionTree in C++

  1. lemon

    Would you please send me a working copy code of this ExpressionTree?Thanks 😀
    My email:Nguyendung_9000@yahoo.com

  2. Sara Masilela

    Could you please send me a copy of the implementation? I’m looking to integrate the program as part of my genetic algorithms code.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s