School of Engineering and Computer Science

XMUT103
Assignment 5: General Tree

Due 25 May , 19 pm

Download zip file of necessary code and data and extract it to an Assig5 folder (eg, in a COMP103 folder in your home folder). It should contain templates for the Java programs that will be marked.

Important note about the style of your code.

To submit

• OrganisationChart.java and Position.java
• CPNCalculator.java

Do not rename these files.

Remember to submit all of these files. When you have submitted them, check that you can read the files listed on the submission page, and complete the submission process.

Part 1: OrganisationChart (Weight: 50%)

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 OrganisationChart 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
• 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)

Note that each node in this tree not only has links to its child nodes, but also has a link to its parent node (the position's manager), which makes it easier to "move around", but makes modification more tricky because both upward and downward links may have to be modified.

The user can modify the organisation chart by

• Selecting a Position clicking on the Position. The selected Position becomes highlighted.
• Renaming a Position Selecting the Position then typing the new role name in the "Change Role" textfield.
• Removing a Position Dragging the Position to the "remove" icon.
  Only Positions that have no team members (child nodes) can be removed.
• Moving an existing Position to be under a different manager Dragging the Position to the new manager.
  All the Position's team members (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 Dragging the New Position icon to its new manager.
• Changing the horizontal location of a Position Dragging the Position to an empty space.

The following table and screenshot summarise the above actions and show how the program should respond to the mouse actions, you need to be aware that some actions have specific conditions.

Mouse Pressed	Mouse Released	Action	Conditions
on "new" icon	on a target Position (SEP)	create a new Position and add it to target's team	none
on a Position (VP2)	same Position (VP2)	select Position	none
on a Position (AL2)	another target Position (VP3)	add Position to target's team	cannot move to within its own subtree
on a Position (DPA)	on remove icon	remove Position from tree	Position must have no team
on a Position	on empty space	move Position left or right (to the empty space)	none

Core

The Core involves completing the core functionality of drawing and editing the tree. You should do it in two steps. Read the comments in the template code to know what the methods should do

Step 1:

Adding Positions and drawing the tree.

• addToTeam (Position class)
• drawTree (OrganisationChart class)

Now you should be able to load the test tree!

Step 2: adding, moving and removing positions

• removeFromTeam (Position class) Note: Only Positions that have no team members can be removed.
• findPosition (OrganisationChart class)
• addNewPosition (OrganisationChart class)
• movePosition (OrganisationChart class) [version a]
• removePosition (OrganisationChart class)

Completion:

The Completion adds an important check on moving positions around: a position should not be moved into its own subtree!

• inSubtree (OrganisationChart class)
• movePosition (OrganisationChart class) [version b]

Also, ensure that if one position is drawn on top of another, 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.
  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 the drawTree method so that it spaces out all the positions nicely and evenly.
  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: 50%)

For this program, you are to complete a calculator that has a 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 and 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.
• sin, cos, and tan, which compute the standard trigonometric functions.
• dist, which either has four operands (x1, y1, x2, y2) and computes the euclidean distance between the 2D points (x1,y1) and (x2,y2), or it has six operands (x1, y1, z1, x2, y2, z2) and computes the euclidean distance between the 3D 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).

The calculator should also know about two constants:

• PI, which has the value Math.PI (3.14159...)
• E, which has the value Math.E (2.71828..., the base of natural logarithms)

Some of the calculator program is written for you:

• 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.
• The GTNode class which defines the nodes of the tree that represents the expression.
• The ExpElem class which defines the expression objects (which have operators or values in them) that are stored in the GTNodes.

You have to complete the evaluate method which evaluates an expression tree.

Draw the tree structure for an expression such as ( + ( * 5 10) 100 ( / PI 2 ) ) showing the GTNode's and the ExpElem's.

Core:

Make the calculator work on expressions with the operators +, -, *, and /, and the constants PI and E.

You need to complete the evaluate(..) method to evaluate an expression and return the value:

• If the node is a number
  return the value of the number
• If it is a named constant
  return the appropriate value
• If is an operator node with children
  (recursively) evaluate all the children, and then apply the operator to their values, and return the answer.

Note: if the expression is invalid in some way, evaluate should return Double.NaN.

You should test your code on a range of expressions. You can also run some automated tests from the test-core.txt file (using the Set input option in the menu). 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 your evaluate 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 value Double.NaN.
• Check that an operator has a valid number of operands; if not report the 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 must have four or six operands
  • log must have one or two operands
  • The other operators have a fixed number of arguments.

You can run some automated tests from the test.txt file (using the Set Input option in the menu). This will enter 19 expressions for you (though you will need to enter a first expression manually). The expected output is given at the end of the assignment.

Challenge

Extend readExpr():

• 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 as 7+6+5*4+3*2*1+2^5
  • ( * 7 6 ( + 5 4 ) ( + 3 ( ^ 2 5 ) 1 ) ) prints as 7*6*(5+4)*(3+2^5+1)
  • ( + 3 ( sin ( + 4 ( * 5 PI ) ) ) ( ln 6 ) ) prints as 3+sin(4+5*PI)+ln(6)

---

Appendix.

Sample output for CPNCalculator on the test-core.txt file:

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:

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