Description

CENG242
Programming Languages
Programming Exam 7

1 Problem Definition
In this exam, you are going to construct some n-ary trees and handle some operations on them.
1. The problem starts with the construction of the trees. For this, you are given some <parent-child> relationships in an unordered way, and you are expected to construct the corresponding tree(s) properly. For example:
addRelation(18, 35) The parent-child sequence given on the left
addRelation(20, 17) addRelation(10, 30) results in 3 independent trees:
addRelation(10, 44) tree-1: 20 tree-2: 65
addRelation(80, 100) / | /
addRelation(35, 43) 17 19 18 26 10
addRelation(20, 19) | / / |
addRelation(65, 26) 16 35 42 12 30 44
addRelation(48, 60) |
addRelation(10, 12) addRelation(65, 10) addRelation(48, 70) 43
addRelation(20, 18) tree-3: ____48____
addRelation(17, 16) / /
addRelation(48, 80) 60 70 80 90
addRelation(18, 42) |
addRelation(48, 90) 100
?
Node: [ int id ]
/ / ….
This class has some some basic methods like constructor, destructor, copy cons., operator overload, etc. Each one is explained in the header file in a detailed way.
3. NodeManager.cpp: NodeManager is the class carrying the independent tree pieces (i.e. independent Node objects). This class also has 3 important methods other than constructor/destructor:
• First, it provides to add new <parent-child> relationships via addRelation(int parent.id, int child.id) method. An illustration of sequential calls of this method is given above, at article 1.
• Second, it enables to convert the type of a Node object into DataNode object via setDataToNode(char data, int node.id) method in which you need to find the related method and replace it with a new node of DataNode.
• Third, it has getNode(int node.id) method which simply returns the corresponding node.
4. Action.cpp: Action is an abstract base class which inherits a single method named act(const Node& node) to its derivations. How the action becomes depends on the derivated class, yet we can say that it conducts some operations on the given node and returns the output tree.
CompleteAction class is illustrated:
100 [100,’G’]
___/ | ___ / |
20 [50,’A’] 10 [50,’A’] 20 [10,’H’]
/ / / /
3 7 1 90 [2,’C’] 90 [1,’I’] 3 7 [2,’C’]
/ | / | _ | / / |
[5,’B’] 4 8 30 40 [9,’F’] 8 4 5 9 [40,’K’] 30
/ /
6 [70,’D’] 6 70
/ /
[60,’E’] 80 60 [80,’J’]
(tree1) (tree2)
Assume that a CompleteAction object was constructed previously by calling CompleteAction(tree1). After act() method of CompleteAction class is called with the tree2 as its argument, it is expected to return tree3 below:
[100,’G’]
__/ | __
[50,’A’] 20 [10,’H’]
/ /
90 [1,’I’] 3 7 [2,’C’] _______
| / /
8
/
6 [70,’D’]
/
[60,’E’] [80,’J’] 4 [5,’B’] [9,’F’] [40,’K’] 30
(tree3)
(The ordering of the siblings is not important)
100 100
___/ | ___ __/ | _
20 50 10 20 50 10
/ / ===> / /
3 7 1 90 2 3 7 1 90 [2,’*’]
/ | / | __ / |
[5,’*’] 4 8 30 40 [9,’*’] [5,’*’] 4 [8,’*’]
/
6 [70,’*’] [242,’*’]
/
[60,’*’] [80,’*’]
(tree1) (tree2)
Assume that a CutAction object was constructed previously by calling
CutAction(’*’). After act() method of CutAction class is called with
the tree1 as its argument, it is expected to return the tree2.
(The ordering of the siblings is not important)
(c) CompositeAction.cpp: CompositeAction is a derivation of abstract Action class. This action is the composition of the other actions. It allows actions to be added using the
2 Regulations
1. Implementation and Submission: The template files ”*.h” and ”*.cpp” are available in the Virtual Programming Lab (VPL) activity called “PE7” on OdtuClass. At this point, you have two options:
• You can download the template files, complete the implementation and test it with the given sample I/O on your local machine. Then submit the same file through this activity. • You can directly use the editor of VPL environment by using the auto-evaluation feature of this activity interactively. Saving the code is equivalent to submit a file.
The second one is recommended. However, if you’re more comfortable with working on your local machine, feel free to do it. Just make sure that your implementation can be compiled and tested in the VPL environment after you submit it. ”*.h” and ”*.cpp” files are given to you so that you can work on your local machines. If you choose first option, you have to submit these files as well but they will not be included into evaluation process. There is no limitation on online trials or submitted files through OdtuClass. The last one you submitted will be graded.
2. Programming Language: You must code your program in C++. Your submission will be compiled with g++ on VPL. You are expected to make sure your code compiles successfully with g++ using the flags -ansi -pedantic.
4. Evaluation: Your program will be evaluated automatically using “black-box” technique so make sure to obey the specifications. No erroneous input will be used. Therefore, you don’t have to consider the invalid expressions.