CS 200, Spring 2017
P5: Analyzing equations

Due and late dates and times

Overview

The object of this assignment is to analyze equations, and to define an evaluation order of these equations. Equations are of the same form as in P4. Driver (see below) reads lines, that are either empty or contain one equation, and creates a dependence graph of these equations, determining which definitions of previous equations are used in the current equation. For example, in:
a1 = true
b2 = false
c3 = a1 or b2
the third equation defining c3 uses definitions of a1 and b2.

Your Equation code now reads lines, and parses them as:

 lhs "=" (token)+ 
where lhs is an identifier and tokens are identifiers, truth values, or boolean operators. A dependence graph, a DepGraph object, contains an ArrayList of adjacency lists, AdjList objects. An AdjList contains a source, an inDegree, and an ArrayList of destinations.

For each identifier x in the right hand side, an edge x --> lhs is created in the dependence graph. So, for the 3 equations above, the dependence graph has 3 nodes: a1, b2 and c3, and 2 edges (a1 --> c3) and (b2 --> c3). It is implemented as an ArrayList of 3 adjacency lists, one for source a1, one for source b2, and one for source c3. The adjacency list for a1 contains c3, and the adjacency list for b2 contains c3. The inDegrees for a1 and b2 are both 0, while the inDegree for c3 is 2. Here is the DepGraph object for these three equations:

0: AdjList source: a1, inDegree: 0, destinations: [c3]
1: AdjList source: b2, inDegree: 0, destinations: [c3]
2: AdjList source: c3, inDegree: 2, destinations: []

After the input lines have been read, and the dependence graph has been created, the order of evaluation of the equations will be determined by a topological sort method, topoPrint(), in DepGraph. The topoPrint method implements the forward topological sort method, described in the Graph 2 lecture nodes. It is based on inDegrees, and prints lines containing all left hand sides of the equations that can be evaluated, ***in the order that the left hand sides were defined*** and thus entered into the dependence graph.

For each line, the identifiers are to be printed as an ArrayList of Strings: e.g. [a1, b2]

For example, when analyzing and topological sorting the input file with the equations given above, the following output is generated by EquationDriver:

next line: a1 = true
next line: b2 = false
next line: c3 = a1 or b2

Dependence Graph: 3 nodes, 2 edges
0: AdjList source: a1, inDegree: 0, destinations: [c3]
1: AdjList source: b2, inDegree: 0, destinations: [c3]
2: AdjList source: c3, inDegree: 2, destinations: []

Evaluation order of equations:
[a1, b2]
[c3]

Work with the following codes:

Testing and submitting your code

Use the Checkin webserver to exercise and submit your code. Submit a P5.jar file containing TokenIter.java, DepGraph.java, AdjList.java, Equation.java **ONLY**.

Make sure you put ***java** files in your jar (not class files).