Introduction to Data Structures and Algorithms
Assignment 5: General Tree
 Due 28 June , 7pm
Resources and links
 Download zip file containing the necessary code and data.
 Java Documentation
 Submit your answers
 Marks and feedback
What To Hand In

Position.java

OrganisationChart.java

CPNCalculator.java
 You are NOT allowed to change any code provided in Template, including the headers, the names or parameters of any existing methods. You can add new methods, but do not change the names/parameters of any existing methods.
 You are NOT allowed to delete any constructors in any classes. You are not allowed to change the headers of any existing constructors.
 Do NOT rename any file provided in the Template.
 Make sure the output of your program matches exactly the example given in the grey boxes below. Please note that the printed out message is compared with the model solutions. If you print out any debugging messages, your answer will not match with our model solutions. So please remember to comment out or delete any lines that print any extra information.
Part 1: OrganisationChart (Weight: 1/2)
Many organisations are structured in a hierarchy with a CEO at the top, and then all the other positions below in a management hierarchy. You are to complete theOrganisationChart
program which allows the
user to display and edit a chart of an organisation structure that
displays the structure as a tree of positions with the CEO at the root of the tree. The links in the tree represent the management structure.
The main data structure in the program is a general tree of Position
objects, where the tree structure is stored directly in the fields of the Position
objects.
Each Position
has fields for  information about the role
 an
Employee
(who has a name and an id) or null to show the Position is vacant.  a manager  the Position that this Position reports to (except for the root node, which has no manager)
 a team  a set of other Positions that report to this Position (possibly an empty set)
 Selecting a Position by clicking on it. The selected Position becomes highlighted.
 Renaming a Position, by selecting the Position then typing the new role in the "Change Role" textfield.
 Removing a Position, by dragging it to the "retirement" icon.
Only Positions that are vacant (no employee) and have no team members (child nodes) can be removed.  Moving an existing Position to be under a different manager by dragging it to the new manager.
All the Position's team members (ie, the whole subtree) will move with the Position.
(note, you shouldn't be able to move a Position to be managed by a Position in the subtree under the Position.)  Creating a new Position, by dragging the New Position icon to its new manager.
 Moving an existing Employee to a vacant Position in the chart by dragging the Employee (the oval within a Position) to their new Position.
An Employee can only be moved to a vacant Position.  Retiring an Employee by dragging them to the retirement icon.
 Adding a new Employee to the chart by selecting an vacant Position, then typing their initials in the "New Employee" textfield.
If the selected Position already has an Employee, it is not changed.  Changing the horizontal location of a Position, by dragging the Position to empty space.
doMouse
method, much of the Position
class, the entire Employee
class, and the code for repositioning a tree node. There is also a method to make a new tree to let you test your program. You should carefully read the Position
and Employee
classes, and the setupGUI
and doMouse
methods.
The user interface for an editor like this is not trivial. Here are two tables showing how the program should respond to mouse actions and to the textfields.
Mouse Pressed  Mouse Released  Action  Conditions 

on "new" icon  on a target Position  create a new Position and add it to target's team  none 
on a Position  same Position  select Position  none 
on empty space  move Pos (to the empty space)  none  
on a Position but not its Employee  another target Position  add Position to target's team  cannot move to within its own subtree 
on retirement icon  remove Position from tree  Position must be vacant and have no team  
on an Employee Emp in a Position 
another target Position  move Emp to the target  target must be vacant 
on retirement icon  remove Emp making Position vacant 
Textfield updated  Action  Conditions 

Role  Change the role of the selected Position  A Position must be selected 
Initials  Create new Employee and fill the vacant selected Position  A Position must be selected and must be vacant 
VP3
position moved to be under SEP
, and the employee BV
has retired leaving the position VP2
vacant. The position AS
has been selected.
Core
The Core involves completing the core functionality of drawing and editing the tree. You should do it in two steps. The relevant methods are listed; the documentation comments on the methods say what the methods should do.Step 1:
Adding Positions and drawing the tree.
addToTeam
(Position
class) 
drawTree
(OrganisationChart
class)
Step 2: adding, moving and removing positions and employees.

removeFromTeam
(Position
class) 
findPosition
(OrganisationChart
class) 
addNewPosition
(OrganisationChart
class) 
movePosition
(OrganisationChart
class) version a 
removePosition
(OrganisationChart
class) 
moveEmployee
(OrganisationChart
class) 
retireEmployee
(OrganisationChart
class)
Completion:
The Completion adds an important check on moving employees around: employees should not be moved into their own subtree!
inSubtree
(OrganisationChart
class) 
movePosition
(OrganisationChart
class) (version b)
findPosition
will return the top position, not the bottom one.
Challenge:
The Challenge involves extending the program in several useful ways: Extend the program to save the current hierarchy to a file and to load a hierarchy from a file.
Hint: You will need to work out a file format that will enable you to reconstruct the tree. Knowing how many positions are in a manager's team before attempting to read them is helpful.
 The current program makes sure that all positions are drawn at the right level on the window, but makes the user do the tricky part of the layout  specifying the horizontal layout of the members of each team.
Fix thedrawTree
method so that it spaces out all the positions nicely and evenly.
Hint: work out the correct offsets of all the positions, by doing a postorder depthfirst traversal of the tree, passing back the total width of each subtree.
 Animate the dragging so that the user can see what they are doing.
Part 2: CPN Calculator (Weight: 1/2)
The lectures demonstrated a program for a simple calculator that would read and evaluate expressions converted into a binary tree, where each operator (+, , *, /) had exactly two operands. For this program, you are to complete a more complex calculator that has a wider range of operators, and also allows some of the operators to have more than two operands (the values that the operator is applied to). It uses "Cambridge Polish Notation" which means that it puts the operator before the operands and puts round brackets around every operator and its operands. For example, 6+3+5 is written ( + 6 3 5 ). Expressions can be nested; for example, the expression ( * ( + 4 8 3 7 2 ) 7 ( / 20 2 5 ) 18 ) is a multiplication operator applied to four operands; the first operand is the sum of 4, 8, 3, 7 and 2; the second operand is 7; the third operand is 20 divided by 2 then divided by 5, and the fourth operand is 18. The value of ( * ( + 4 8 3 7 2 ) 7 ( / 20 2 5 ) 18 ), should be 6048 (which is 24 * 7 * 2 * 18). The operators that the calculator should know about are: +, which adds up all its operands.
 , which subtracts from the first operand all the remaining operands.
 *, which multiplies all its operands.
 /, which divides the first operand by all the remaining operands.

^
, which has two arguments, and computes the first to the power of the second. eg,( ^ 2 3 )
would compute 2 to the power of 3, which is 8. 
sqrt
, which computes the square root of its (one) operand 
log
andln
, which compute the log to base 10 and the natural log (base e) of the operand. If log has two operands, it computes the log of the first operand to base of the second operand. 
sin
,cos
, andtan
, which compute the standard trigonometric functions. 
dist
, which either has four operands (x1, y1, x2, y2) and computes the euclidean distance between the points (x1,y1) and (x2,y2), or it has six operands (x1, y1, z1, x2, y2, z2) and computes the euclidean distance between the points (x1,y1,z1) and (x2,y2,z2) 
avg
, which computes the average of all its arguments (any number of them, but at least one).
 PI, which has the value Math.PI (3.14159...)
 E, which has the value Math.E (2.71828..., the base of natural logarithms)
 The GUI set up,
 The top level REPL structure (a Read Evaluate, Print Loop that reads an expression, evaluates it, and prints it out).
 A method that reads an expression from the user and turns it into a general tree where the leaves have numbers (or constants), and the internal nodes have an operator and a list of child nodes that the operator is applied to.
evaluate
method which evaluates an expression tree.
Core:
Make the calculator work on expressions with the operators +, , *, and /, and the constants PI and E. You should test your code on a range of epressions. You can also run some automated tests by using Set input in the menu to get input from the testcore.txt file. This will enter 7 expressions for you (though you will need to enter a first expression manually). The expected output is given at the end of the assignment.Completion
Extend yourevaluate
method:  Handle the other operators above. You will find methods in the
Math
class to be useful.  Check for unknown operators  if an expression has an invalid operator,
evaluate
should report the error (eg, The operator $ is invalid) and return the special double valueDouble.NaN
.  Check that an operator has a valid number of operands, report any errors, and return
Double.NaN
 The arithmetic operators and
avg
allow any number of operands above 0. eg ( + 5 ) is OK and means just 5;

dist
allows four or six operands 
log
allows one or two operands  The other operators have a fixed number of arguments.
 The arithmetic operators and
Challenge
ExtendreadExpr
:  Check for empty brackets (ie ( ) ). Report the error and return the
null
tree.  Check for an invalid expression that has brackets that don't match,
 Add a
printExpr
method that will print the expression using normal infix for+
,
,*
, and/^
, using brackets only when necessary, and using normal brackets notation for the other functions. For example
( + 7 6 ( * 5 4 ) ( * 3 2 1 ) ( ^ 2 5 ) )
prints as7+6+5*4+3*2*1+2^5

( * 7 6 ( + 5 4 ) ( + 3 ( 2 5 ) 1 ) )
prints as7*6*(5+4)*(3+2^5+1)

( + 3 ( sin ( + 4 ( * 5 PI ) ) ) ( ln 6 ) )
prints as3+sin(4+5*PI)+ln(6)

Sample output for CPNCalculator on the testcore.txt file:
Make sure the output of your program exactly matches the given text.expr: 20 > 20.0 expr: ( + 7 6 ( * 5 4 ) ( * 3 2 1 ) ) > 39.0 expr: ( * 7 6 ( + 5 4 ) ( + 3 2 1 ) ) > 2268.0 expr: (  ( * 2 4 ) ( / 2 4 ) ) > 7.5 expr: (  24 2 3 4 ) > 15.0 expr: ( / 24 2 3 4 ) > 1.0 expr: ( * 2 PI 10 ) > 62.83185307179586
Sample output for CPNCalculator on the test.txt file:
Make sure the output of your program exactly matches the given text.expr: ( + 50 ( log ( * 125 8 ) ) ) > 53.0 expr: ( ^ 2.718282 ( ln 20 ) ) > 20.00000378099725 expr: ( ^ ( ^ 2 5 ) 2 ) > 1024.0 expr: ( ^ 10 ( log 38 ) ) > 37.99999999999999 expr: ( + ( sin ( / 3.14159 3 2 ) ) ( cos ( / 3.14159 3 ) ) ( tan ( / 3.14159 4 ) ) ) > 1.9999990562184347 expr: ( dist 0 0 3 4 ) > 5.0 expr: ( dist 0 0 0 3 4 12 ) > 13.0 expr: ( avg 1 2 3 4 5 6 7 8 9 10 ) > 5.5 expr: ( + 3 ( sin ( / PI 6 ) ) ( log ( * 125 8 ) ) ) > 6.5 expr: ( ^ E ( ln 20 ) ) > 19.999999999999993 expr: ( + ( sin ( / PI 3 2 ) ) ( cos ( / PI 3 ) ) ( tan ( / PI 4 ) ) ) > 2.0 expr: ( log 64 4 ) > 3.0 expr: ( The remaining examples should all be errors ) The is not a valid operator. > NaN expr: ( + 1 2 3 4 Missing closing bracket > NaN expr: ( log 64 2 2 ) Too many operands for log > NaN expr: ( dist 1 2 3 ) Wrong operands for dist > NaN expr: ( dist 1 2 3 4 5 ) Wrong operands for dist > NaN expr: ( dist 1 2 3 4 5 6 7 ) Wrong operands for dist > NaN expr: ( power 5 7 ) power is not a valid operator. > NaN