Scientific Computing in C++
Assignment 05
Evaluation of Algebraic Expressions
The main goal of asignments 5 and 6 is to implement a program that wil take as input an algebraic
expression such as
“((3*5)+(4*(7+(8*5))*(7-(9*3)))”
represented as a C-style. string, and produce as output the result of evaluating such expression as a
floating point number. You wil have to implement a class named AlgebraicTreeNode, which together
with the folowing main() function wil compile in asignment 6 into a comand line program named
calc6. This program wil take an algebraic expresion such as the one shown above as the only
argument, and wil print the result of evaluating such expression. In future asignments, we will build an
interactive calculator by adding a user interface to this class.
// Calc6.cpp
#include
#include “AlgebraicTreeNode.hpp”
using namespace std;
int main(int argc, const char * argv[]) {
// error handling
if(argcisInvalid()) {
cout evaluate();
cout
#include “AlgebraicTreeNode.hpp”
using namespace std;
AlgebraicTreeNode* newExpr1() {
AlgebraicTreeNode* root = new AlgebraicTreeNode();
// construct data structure for expression “(8*5)"
return root;
}
AlgebraicTreeNode* newExpr2() {
AlgebraicTreeNode* root = new AlgebraicTreeNode();
// construct data structure for expression “(4*((8*5)+7))"
return root;
}
AlgebraicTreeNode* newExpr3() {
AlgebraicTreeNode* root = new AlgebraicTreeNode();
// construct data structure for expression "(((3*5)+(4*(7+(8*5))))*(7-(9*3)))"
return root;
}
int main(int argc, const char * argv[]) {
AlgebraicTreeNode* root = newExpr1();
// AlgebraicTreeNode* root = newExpr2();
// AlgebraicTreeNode* root = newExpr3();
if(root->isInvalid()) {
cout toString();
double value = root->evaluate();
cout
#include
enum AlgebraicTreeNodeType {
INVALID, NUMBER, ADD, SUBTRACT, MULTIPLY, DIVIDE
};
class AlgebraicTreeNode {
public:
// default constructor
AlgebraicTreeNode();
// destructor
~AlgebraicTreeNode();
// string representation
char* toString() const;
// evaluator
double evaluate() const;
private:
AlgebraicTreeNode* _parent;
AlgebraicTreeNodeType _type;
double _value;
AlgebraicTreeNode* _childLeft;
AlgebraicTreeNode* _childRight;
};
#endif // _AlgebraicTreeNode_hpp_
The same class wil be used to represent numbers as leaf nodes, and operations as regular nodes. In this
design, an instance of the clas has five private clas variables, and initially three public clas functions.
You wil have to add several aditional functions as described below. The value of the private field
AlgebraicTreeNode* _parent;
should be a pointer to the parent node of the curent node, if the curent node is not the rot node. For
the root node the value of this private field should be the nul pointer (AlgebraicTreeNode*)0. The
private field
AlgebraicTreeNodeType _type;
will be used to indicate what type of node the instance of the clas represents. The possible values are
defined by the enum
enum AlgebraicTreeNodeType {
INVALID, NUMBER, ADD, SUBTRACT, MULTIPLY, DIVIDE
};
Note that this enum is placed outside of the clas interface definition. It can also be placed inside the
class interface definition, either in the public or in the private interface sections. You should experiment
moving this enum to the various posible places to understand what the implications are. The value
NUMBER wil be used to represent leaf nodes. In this case the private field
double _value;
ENGN2912B 2017 Assignment 05 - 5
should contain the value of the number associated with the leaf node. In this case the value of the two
private fields
AlgebraicTreeNode* _childLeft;
AlgebraicTreeNode* _childRight;
should be equal to (AlgebraicTreeNode*)0. The _type values ADD, SUBTRACT, MULTIPLY, DIVIDE
wil be used to represent the corresponding arithmetic operations as regular nodes. In this case the
values of the private fields _childLeft and _childRight should be valid pointers to class instances
representing the left and right sub expresions, and the value of the private field _value should be 0.0.
The _type value INVALID wil be used to indicate erors encountered by other constructors, which you
wil implement later.
The default Constructor
You ned to implement the default constructor
AlgebraicTreeNode();
The default constructor should initialize the private fields as folows: _parent, _childLeft, and
_childRight to (AlgebraicTreeNode*)0; _type to INVALID; and _value to 0.0.
The Number Constructor
You ned to implement a second constructor with the folowing signature
AlgebraicTreeNode(const double value,
AlgebraicTreeNode* parent=(AlgebraicTreeNode*)0);
This constructor should initialize the private fields as folows: _parent to the value of the second
constructor parameter parent; _childLeft, and _childRight to (AlgebraicTreeNode*)0; _type to
NUMBER; and _value to the value of the first constructor parameter value. Since in this asignment we
want to construct the tre structure in the main() function, this constructor should be declared public.
The Operation Constructor
Since the left and right children nodes may not have been constructed at the time an operation node is
constructed, we wil not pass the pointers to the left and right children as parameters to the
constructor, and we wil set the values of the _childLeft and _childRight private fields later. You
need to implement a third constructor with the following signature
AlgebraicTreeNode(AlgebraicTreeNodeType operation,
AlgebraicTreeNode* parent=(AlgebraicTreeNode*)0);
This constructor should initialize the private fields as folows: _parent to the value of the second
constructor parameter parent; _childLeft, and _childRight to (AlgebraicTreeNode*)0; _type to
the value of the first constructor parameter operation if this value is ADD, SUBTRACT, MULTIPLY, or
DIVIDE, and otherwise to INVALID; and _value should be initialized to 0.0.
Conecting the tree nodes
ENGN2912B 2017 Assignment 05 - 6
Since in this asignment we want to construct the tre structure in the main() function, and _parent,
_childLeft and _childRight are private fields, you need to implement set functions with the folowing
signatures to interconect the nodes of the tree
void setParent(const AlgebraicTreeNode* parent);
void setChildLeft(const AlgebraicTreeNode* childLeft);
void setChildRight(const AlgebraicTreeNode* childRight);
In every directed tre there is a unique path from every node to the rot node. The function of the
_parent private field is to enable the construction of this path. We wil find uses for this field later.
Examples
The folowing code can be used to construct the data structure for the expresion “5.0”
AlgebraicTreeNode* root = new AlgebraicTreeNode(5.0);
The folowing code can be used to construct the data structure for the expresion “(5+6)”
AlgebraicTreeNode* root = new AlgebraicTreeNode(AlgebraicTreeNodeType::ADD);
AlgebraicTreeNode* rootLeft = new AlgebraicTreeNode(5.0, root);
root->setChildLeft(rootLeft);
AlgebraicTreeNode* rootRight = new AlgebraicTreeNode(6.0, root);
root->setChildRight(rootRight);
A more compact implementation
AlgebraicTreeNode* root = new AlgebraicTreeNode(AlgebraicTreeNodeType::ADD);
root->setChildLeft(new AlgebraicTreeNode(5.0, root));
root->setChildRight(new AlgebraicTreeNode(6.0, root));
The Destructor
You ned to implement the class destructor
~AlgebraicTreeNode();
The class destructor should not do anything if the node type is NUMBER or INVALID. Otherwise,
it should delete _childLeft and/or _childRight because these are pointers to instances
of the class created in the heap.
Add the following two statements to the main() function, before the last return statement, and make
sure that your program completes successfuly without crashing in the destructor.
delete [] str;
delete root;
Auxiliary functions
You ned to implement the folowing public auxiliary functions, which wil return true or false
depending on the value of the private variable _type.
ENGN2912B 2017 Assignment 05 - 7
bool isInvalid() const;
bool isNumber() const;
bool isOperation() const;
The evaluate() function
In this asignment you wil implement a recursive function to evaluate an expresion.
double evaluate() const;
If the node type is NUMBER, the function should return the value stored in the variable _value;
otherwise, the function should evaluate the left child and the right child and return the result of
applying the operation to those two values. In addition, if the node type is INVALID, the function should
return 0.
Depth-First traversal
Note that any recursive function, which returns from a leaf node, and cals itself on the left and right
children before returning from a regular node, results in a depth-first traversal of the tree. The
evaluate() function is a particular case. For example, the expression “(4*((8*5)+7))” should result
in a tre with 7 nodes with the following structure, where the numbering of the nodes reflects the
particular order of creation, which is not unique.
* node0
/ \ / \
4 + node2 node1
/ \ / \
* 7 node4 node3
/ \ / \
8 5 node6 node5
However, the depth-first traversal order of this tree is
node0,node2,node1,node4,node6,node5,node3
To verify that your tre is properly constructed and the implementation of the evaluate() function
performs the correct steps you should do this: 1) add a new private int variable named _id to the clas;
2) implement a mechanism to enumerate the nodes as they are constructed by the diferent
constructors, and assign consecutive _id values to new instances of the class; 3) add a print statement
before the return statement, showing the _id value, and to indicate what operation has been
performed. For a node of type NUMBER, such as node2 above, it should print
node2 : 4
For a node of type ADD, such as node1 above, it should print
node1 : (40+7)=47
where 40 is the result of evaluating the left child, and 7 is the result of evaluating the right child.
Although this case should never happen, for a node of type INVALID, it should print
node34 : INVALID
ENGN2912B 2017 Assignment 05 - 8
The toString() function
To further verify that your data structure is corect, you will implement the public method
char* toString() const;
which should return a C-style. (nul terminated) string alocated in the heap, with a string representation
of the expresion, reconstructed from the data structure. Let’s ignore for the moment that we would
not know before hand how long the string should be, and let’s assume that we have already allocated a
string of the proper length, and that we have initialized it to the value “”.
For a node of type NUMBER this function should concatenate a string representation of the _value field
to the string. For an operation type node such as AD, this function should apend “(“ to the string,
recursively cal itself on _childLeft with a pointer to the end of str as argument, append the operator
symbol “+” to str, recursively cal itself on _childRight with a pointer to the end of str as argument,
append “)” to str, and return.
Since we first need to alocate the string, and we need to recursively cal the function with the string as
an argument, we wil use this implementation of the function toString() :
char* AlgebraicTreeNode::toString() const {
unsigned N = this->_toStringLength();
char* str = new char[N];
memset(str,’\0’,N*sizeof(char));
_toString(str);
return str;
}
The default behavior. in C and C++ is not to initialize arrays of built-in data types. The library function
memset(), defined in the header file , can be used to initialize any aray to a constant value.
You ned to implement the folowing two aditional private functions
unsigned _toStringLength() const;
unsigned _toString(char* str) const;
Note that we defined the function _toString() as returning an unsigned value, which wil be ignored in
the cal to the toString() function. To prevent you from having to compute the length of the string
every time you have to concatenate something to it, this function should return the length of the string
printed within the function cal. You should use this value to figure out where to continue printing on
the string. For example, if the expression to be printed is ”(8*5)”, the initial value of the string pointed
to by str on the first cal to _toString wil be “”, the final value wil be “(8*5)”, and the returned value
wil be 5. The function _toString wil first concatenate “(“ to str. Since the string “(“ has
length 1, then the function wil cal itself on the left child of the current node with parameter str+1.
This call wil result in the string “8” writen on the string starting at the value of the pointer pased as
the argument, and the value 1 being returned. Then “*” wil be writen starting at str+2, another cal on
the left child of the current node with parameter str+3, which wil result in the string “5” writen starting
at that position and the value 1 returned. Finally the string “)” wil be writen starting at position str+4,
resulting in the desired string of length 5 written on the array. The function _toStringLength() can be
identical to the function , but with the statements where strings are written removed. To know the
length of the string resulting from printing a number, the _toStringLength() function could use a
static char aray of suficient length (say 1024). In fact, the _toString() function could use the same
proces, and then copy the printed string from the static aray onto the pointer received as argument.
To do this without making mistakes, it is a god idea to implement the method to write on the static
ENGN2912B 2017 Assignment 05 - 9
string as a separate function
unsigned _ftoa(const double value, char* str = (char*)0);
which should not be a clas function, since it doesn’t ned to have aces to clas variables. This function
should return the length of the writen string. If a non-null pointer is pased as the second argument,
the function should write the corresponding string starting at that location. If a nul pointer is pased as
argument, the function should use a static array as described above.
Include the signature in the clas header file as a global function, and the implementation in the class
implementation file. The static temporary aray should be defined inside the scope of this function, and
used only when a null pointer is pased as the second argument.
In the implementation of this function you could use the C library function sprintf(), which is defined
in the header file , and returns the length of the printed string. For example, the folowing
statement wil result in the value printed with four decimals
unsigned n = sprint(str,”%.4f”,_value);
Look for the definition of the sprintf() and printf() functions on-line and learn about formated
printing.