Due: 12:00 Noon Thu Oct 24
You are to create a number of files, as directed below, and then submit them electronically on host lectura.cs.arizona.edu using the command
Please follow the directions below carefully: submissions that don't follow directions will be penalized heavily.
Note: As before, your programs should compile with no errors or warnings when compiled with gcc -Wall. Moreover, each program should exit with a status of 0 if execution proceeds normally, and a status of -1 if any sort of error occurs.
In addition, your programs will be expected to follow the coding guidelines for this class.
Write a program, in a file mycalc.c, in accordance with the specification given below.
Behavior:
The program repeatedly reads in simple numerical expressions, one expression per line, from stdin; evaluates the expression so read in; and prints out the results on stdout.
Syntax of Expressions:
Expressions have the following syntax:
- an integer constant is an expression;
- if A and B are expressions, then so are: -A, A+B, A-B, A*B, A/B, (A).
An example of an expression would be (1 + 2) * - ( (6) - 4/2 ).
The operators have the same meaning, associativity, and precedence as in C.
Reading in and Processing Expressions:
You should use the myparse library to read in each expression. The readExpr() function provided in this library will return a tree reflecting the structure of the expression.The value of an expression can be computed by recursively compute the value of subexpressions (if any), then using the node type to compute the value of the expression. For example, if we have a tree node of type TN_PLUS and subexpressions A and B, then recursively compute the values of A and B, then use the node type (in this case, TN_PLUS) to figure out that these subexpression values should be added together to obtain the value of the expression.
Miscellaneous:
The executable file /home/cs352/FALL02/hw6_stuff/mycalc implements the functionality expected of your program.
Write a program, in a file called reachability.c, that behaves as follows: it reads in a description of the routes flown by an airline (first part of the input, see below), and then for each pair of cities specified in the third part of the input, indicates whether or not it is possible to travel between those cities on the given airline. The program exits when an end-of-file is encountered on stdin.
Input:
The input consists of three parts, in this order:
- A sequence of lines, where each line contains a pair of alphanumeric strings (i.e., strings consisting of a sequence of letters and digits) separated by whitespace (a sequence of one or more blanks and tabs). Each string represents a city; an input line with a pair of cities, e.g.:
str1 str2denotes that there is a flight between str1 and str2 on the airline we're considering. We'll assume flight routes to be symmetric, i.e., if there's a flight from A to B then there's also a flight from B to A. It is legal to have more than one flight between a pair of cities, and also to have a flight from a city back to itself.You may assume that the name of a city is at most 64 characters long.
- A delimiter, consisting of the two characters "%%" on a line by themselves.
- A sequence of queries, one per line. Each query consists of a pair of alphanumeric strings seperated by whitespace. These resemble the pairs specifying flight routes in the first part of the file, but are treated differently: a query specifying a pair of cities
str1 str2asks whether there is a path from str1 to str2 using the flights of the airline as specified in the first part of the input.
Behavior:
Your program should read in the specification of flights (the first part of the input), construct a representation for this, and then process the queries in the third part of the input in order. For each query, your program should print out, on stdout, one per line:
1 if the answer to the query is yes (i.e., if there is a path between the two cities in the query); 0 if the answer to the query is no
Note that the cities mentioned in a query need not have been mentioned in the first part of the input specifying flight routes. This is not an error: if a query contains a city not mentioned in the flight routes, we conclude that the city is not served by the airline, so the answer to the query is 0.
Example:
The inputand should generate the output
a b
a c
c b
d b
e f
g f
h f
%%
a d
a e
e g
p qspecifies the flight connections 1
0
1
0
Algorithm:
An algorithm for determining reachability relations is given here.
Restrictions:
Your program should satisfy the following restrictions:
- You may assume that the name of a city is at most 64 characters long. Other than this, there should not be any a priori hard limits on the number of cities, flight routes, or queries. In other words, it is not acceptable to use a fixed large array to hold the input.
- The amount of memory used by your program should be proportional to the total number of cities and flight routes specified in the input. In other words, if the input graph contains n cities and m flight routes, the amount of memory used should be proportional to n+m.
You should dynamically allocate memory via the malloc() system call as necessary. In particular, I do not want you to use realloc() to resize arrays.