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
- 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 the
OrganisationChartprogram 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
Positionobjects, where the tree structure is stored directly in the fields of the
Positionhas fields for
- information about the role
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.
doMousemethod, much of the
Positionclass, the entire
Employeeclass, 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
Employeeclasses, and the
doMousemethods. 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
|another target Position||move Emp to the target||target must be vacant|
|on retirement icon||remove Emp making Position vacant|
|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|
VP3position moved to be under
SEP, and the employee
BVhas retired leaving the position
VP2vacant. The position
AShas been selected.
CoreThe 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.
Step 2: adding, moving and removing positions and employees.
OrganisationChartclass) version a
Completion:The Completion adds an important check on moving employees around: employees should not be moved into their own subtree!
OrganisationChartclass) (version b)
findPositionwill 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.
drawTreemethod so that it spaces out all the positions nicely and evenly.
Hint: work out the correct offsets of all the positions, by doing a post-order depth-first 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
ln, 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.
tan, 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.
evaluatemethod 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 test-core.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.
- Handle the other operators above. You will find methods in the
Mathclass to be useful.
- Check for unknown operators - if an expression has an invalid operator,
evaluateshould report the error (eg, The operator $ is invalid) and return the special double value
- Check that an operator has a valid number of operands, report any errors, and return
- The arithmetic operators and
avgallow any number of operands above 0. eg ( + 5 ) is OK and means just 5;
distallows four or six operands
logallows one or two operands
- The other operators have a fixed number of arguments.
- The arithmetic operators and
- Check for empty brackets (ie ( ) ). Report the error and return the
- Check for an invalid expression that has brackets that don't match,
- Add a
printExprmethod that will print the expression using normal infix for
/^, 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 as
( * 7 6 ( + 5 4 ) ( + 3 ( 2 5 ) 1 ) )prints as
( + 3 ( sin ( + 4 ( * 5 PI ) ) ) ( ln 6 ) )prints as
Sample output for CPNCalculator on the test-core.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